From 4118e89cdcf4e635285d0b97f09a16176b94a6fd Mon Sep 17 00:00:00 2001 From: CSRG Date: Thu, 7 Jun 1990 14:36:47 -0800 Subject: [PATCH] BSD 4_3_Net_2 development Work on file usr/src/lib/libg++/g++-include/gen/XPBag.ccP Work on file usr/src/lib/libg++/g++-include/gen/VOHSet.ccP Work on file usr/src/lib/libg++/g++-include/gen/SplayBag.ccP Work on file usr/src/lib/libg++/g++-include/gen/SLBag.ccP Work on file usr/src/lib/libg++/g++-include/gen/PHPQ.ccP Work on file usr/src/lib/libg++/g++-include/gen/OXPBag.ccP Work on file usr/src/lib/libg++/g++-include/gen/OSLBag.ccP Work on file usr/src/lib/libg++/g++-include/gen/FPlex.ccP Work on file usr/src/lib/libg++/g++-include/gen/CHSet.ccP Work on file usr/src/lib/libg++/g++-include/gen/CHBag.ccP Synthesized-from: CSRG/cd2/net.2 --- usr/src/lib/libg++/g++-include/gen/CHBag.ccP | 214 +++++++++ usr/src/lib/libg++/g++-include/gen/CHSet.ccP | 276 +++++++++++ usr/src/lib/libg++/g++-include/gen/FPlex.ccP | 182 +++++++ usr/src/lib/libg++/g++-include/gen/OSLBag.ccP | 201 ++++++++ usr/src/lib/libg++/g++-include/gen/OXPBag.ccP | 226 +++++++++ usr/src/lib/libg++/g++-include/gen/PHPQ.ccP | 342 +++++++++++++ usr/src/lib/libg++/g++-include/gen/SLBag.ccP | 110 +++++ .../lib/libg++/g++-include/gen/SplayBag.ccP | 451 ++++++++++++++++++ usr/src/lib/libg++/g++-include/gen/VOHSet.ccP | 313 ++++++++++++ usr/src/lib/libg++/g++-include/gen/XPBag.ccP | 77 +++ 10 files changed, 2392 insertions(+) create mode 100644 usr/src/lib/libg++/g++-include/gen/CHBag.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/CHSet.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/FPlex.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/OSLBag.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/OXPBag.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/PHPQ.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/SLBag.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/SplayBag.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/VOHSet.ccP create mode 100644 usr/src/lib/libg++/g++-include/gen/XPBag.ccP diff --git a/usr/src/lib/libg++/g++-include/gen/CHBag.ccP b/usr/src/lib/libg++/g++-include/gen/CHBag.ccP new file mode 100644 index 0000000000..b7f97ec938 --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/CHBag.ccP @@ -0,0 +1,214 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include ".CHBag.h" + +// The nodes are linked together serially via a version +// of a trick used in some vtables: odd pointers are +// actually links to the next table entry. +// Not terrible, but not wonderful either + +static inline int goodCHptr(CHNode* t) +{ + return ((((unsigned)t) & 1) == 0); +} + +static inline CHNode* index_to_CHptr(int i) +{ + return (CHNode*)((i << 1) + 1); +} + +static inline int CHptr_to_index(CHNode* t) +{ + return ( ((unsigned) t) >> 1); +} + +CHBag::CHBag(unsigned int sz) +{ + tab = (CHNode**)(new CHNodePtr[size = sz]); + for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); + count = 0; +} + +CHBag::CHBag(CHBag& a) +{ + tab = (CHNode**)(new CHNodePtr[size = a.size]); + for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); + count = 0; + for (Pix p = a.first(); p; a.next(p)) add(a(p)); +} + + +Pix CHBag::seek( key, Pix i) +{ + CHNode* p = (CHNode*)i; + if (p == 0 || !EQ(p->hd, key)) + { + unsigned int h = HASH(key) % size; + for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl) + if (EQ(key, t->hd)) + return Pix(t); + } + else + { + for (p = p->tl; goodCHptr(p); p = p->tl) + if (EQ(p->hd, key)) + return Pix(p); + } + return 0; +} + +int CHBag::nof( key) +{ + int n = 0; + unsigned int h = HASH(key) % size; + for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl) + if (EQ(key, t->hd)) ++n; + return n; +} + + +Pix CHBag::add( item) +{ + unsigned int h = HASH(item) % size; + CHNode* t = new CHNode(item); + t->tl = tab[h]; + tab[h] = t; + ++count; + return Pix(t); +} + +void CHBag::del( key) +{ + unsigned int h = HASH(key) % size; + + CHNode* t = tab[h]; + CHNode* trail = t; + while (goodCHptr(t)) + { + if (EQ(key, t->hd)) + { + if (trail == t) + tab[h] = t->tl; + else + trail->tl = t->tl; + delete t; + --count; + return; + } + trail = t; + t = t->tl; + } +} + +void CHBag::remove( key) +{ + unsigned int h = HASH(key) % size; + + CHNode* t = tab[h]; + CHNode* trail = t; + while (goodCHptr(t)) + { + if (EQ(key, t->hd)) + { + --count; + if (trail == t) + { + tab[h] = t->tl; + delete t; + t = trail = tab[h]; + } + else + { + trail->tl = t->tl; + delete t; + t = trail->tl; + } + } + else + { + trail = t; + t = t->tl; + } + } +} + + +void CHBag::clear() +{ + for (unsigned int i = 0; i < size; ++i) + { + CHNode* p = tab[i]; + tab[i] = index_to_CHptr(i+1); + while (goodCHptr(p)) + { + CHNode* nxt = p->tl; + delete(p); + p = nxt; + } + } + count = 0; +} + +Pix CHBag::first() +{ + for (unsigned int i = 0; i < size; ++i) if (goodCHptr(tab[i])) return Pix(tab[i]); + return 0; +} + +void CHBag::next(Pix& p) +{ + if (p == 0) return; + CHNode* t = ((CHNode*)p)->tl; + if (goodCHptr(t)) + p = Pix(t); + else + { + for (unsigned int i = CHptr_to_index(t); i < size; ++i) + { + if (goodCHptr(tab[i])) + { + p = Pix(tab[i]); + return; + } + } + p = 0; + } +} + +int CHBag::OK() +{ + int v = tab != 0; + int n = 0; + for (unsigned int i = 0; i < size; ++i) + { + for (CHNode* p = tab[i]; goodCHptr(p); p = p->tl) ++n; + v &= CHptr_to_index(p) == i + 1; + } + v &= count == n; + if (!v) error("invariant failure"); + return v; +} diff --git a/usr/src/lib/libg++/g++-include/gen/CHSet.ccP b/usr/src/lib/libg++/g++-include/gen/CHSet.ccP new file mode 100644 index 0000000000..07c57d3462 --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/CHSet.ccP @@ -0,0 +1,276 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include ".CHSet.h" + +// A CHSet is implemented as an array (tab) of buckets, each of which +// contains a pointer to a list of CHNodes. Each node contains a +// pointer to the next node in the list, and a pointer to the . +// The end of the list is marked by a next node pointer which is odd +// when considered as an integer (least significant bit = 1). The +// assumption is that CHNodes will all begin on even addresses. If +// the odd pointer is right-shifted by one bit, it becomes the index +// within the tab array of the next bucket (that is, bucket i has +// next bucket pointer 2*(i+1)+1). + +// The bucket pointers are initialized by the constructor and +// used to support the next(Pix&) method. + +// This implementation is not portable to machines with different +// pointer and integer sizes, or on which CHNodes might be aligned on +// odd byte boundaries, but allows the same pointer to be used for +// chaining within a bucket and to the next bucket. + + +static inline int goodCHptr(CHNode* t) +{ + return ((((unsigned)t) & 1) == 0); +} + +static inline CHNode* index_to_CHptr(int i) +{ + return (CHNode*)((i << 1) + 1); +} + +static inline int CHptr_to_index(CHNode* t) +{ + return ( ((unsigned) t) >> 1); +} + +CHSet::CHSet(unsigned int sz) +{ + tab = (CHNode**)(new CHNodePtr[size = sz]); + for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); + count = 0; +} + +CHSet::CHSet(CHSet& a) +{ + tab = (CHNode**)(new CHNodePtr[size = a.size]); + for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); + count = 0; + for (Pix p = a.first(); p; a.next(p)) add(a(p)); +} + + +Pix CHSet::seek( key) +{ + unsigned int h = HASH(key) % size; + + for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl) + if (EQ(key, t->hd)) + return Pix(t); + + return 0; +} + + +Pix CHSet::add( item) +{ + unsigned int h = HASH(item) % size; + + for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl) + if (EQ(item, t->hd)) + return Pix(t); + + ++count; + t = new CHNode(item, tab[h]); + tab[h] = t; + return Pix(t); +} + + +void CHSet::del( key) +{ + unsigned int h = HASH(key) % size; + + CHNode* t = tab[h]; + CHNode* trail = t; + while (goodCHptr(t)) + { + if (EQ(key, t->hd)) + { + if (trail == t) + tab[h] = t->tl; + else + trail->tl = t->tl; + delete t; + --count; + return; + } + trail = t; + t = t->tl; + } +} + + +void CHSet::clear() +{ + for (unsigned int i = 0; i < size; ++i) + { + CHNode* p = tab[i]; + tab[i] = index_to_CHptr(i+1); + while (goodCHptr(p)) + { + CHNode* nxt = p->tl; + delete(p); + p = nxt; + } + } + count = 0; +} + +Pix CHSet::first() +{ + for (unsigned int i = 0; i < size; ++i) if (goodCHptr(tab[i])) return Pix(tab[i]); + return 0; +} + +void CHSet::next(Pix& p) +{ + if (p == 0) return; + CHNode* t = ((CHNode*)p)->tl; + if (goodCHptr(t)) + p = Pix(t); + else + { + for (unsigned int i = CHptr_to_index(t); i < size; ++i) + { + if (goodCHptr(tab[i])) + { + p = Pix(tab[i]); + return; + } + } + p = 0; + } +} + +int CHSet::operator == (CHSet& b) +{ + if (count != b.count) + return 0; + else + { + CHNode* p; + for (unsigned int i = 0; i < size; ++i) + for (p = tab[i]; goodCHptr(p); p = p->tl) + if (b.seek(p->hd) == 0) + return 0; + for (i = 0; i < b.size; ++i) + for (p = b.tab[i]; goodCHptr(p); p = p->tl) + if (seek(p->hd) == 0) + return 0; + return 1; + } +} + +int CHSet::operator <= (CHSet& b) +{ + if (count > b.count) + return 0; + else + { + for (unsigned int i = 0; i < size; ++i) + for (CHNode* p = tab[i]; goodCHptr(p); p = p->tl) + if (b.seek(p->hd) == 0) + return 0; + return 1; + } +} + +void CHSet::operator |= (CHSet& b) +{ + if (&b == this || b.count == 0) + return; + for (unsigned int i = 0; i < b.size; ++i) + for (CHNode* p = b.tab[i]; goodCHptr(p); p = p->tl) + add(p->hd); +} + +void CHSet::operator &= (CHSet& b) +{ + for (unsigned int i = 0; i < size; ++i) + { + CHNode* t = tab[i]; + CHNode* trail = t; + while (goodCHptr(t)) + { + CHNode* nxt = t->tl; + if (b.seek(t->hd) == 0) + { + if (trail == tab[i]) + trail = tab[i] = nxt; + else + trail->tl = nxt; + delete t; + --count; + } + else + trail = t; + t = nxt; + } + } +} + +void CHSet::operator -= (CHSet& b) +{ + for (unsigned int i = 0; i < size; ++i) + { + CHNode* t = tab[i]; + CHNode* trail = t; + while (goodCHptr(t)) + { + CHNode* nxt = t->tl; + if (b.seek(t->hd) != 0) + { + if (trail == tab[i]) + trail = tab[i] = nxt; + else + trail->tl = nxt; + delete t; + --count; + } + else + trail = t; + t = nxt; + } + } +} + +int CHSet::OK() +{ + int v = tab != 0; + int n = 0; + for (unsigned int i = 0; i < size; ++i) + { + for (CHNode* p = tab[i]; goodCHptr(p); p = p->tl) ++n; + v &= CHptr_to_index(p) == i + 1; + } + v &= count == n; + if (!v) error("invariant failure"); + return v; +} diff --git a/usr/src/lib/libg++/g++-include/gen/FPlex.ccP b/usr/src/lib/libg++/g++-include/gen/FPlex.ccP new file mode 100644 index 0000000000..235d290875 --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/FPlex.ccP @@ -0,0 +1,182 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + based on code by Marc Shapiro (shapiro@sor.inria.fr) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include ".FPlex.h" + + +FPlex:: FPlex() +{ + lo = fnc = 0; + csize = DEFAULT_INITIAL_CAPACITY; + * data = new [csize]; + hd = new IChunk(data, lo, lo, fnc, csize); +} + +FPlex:: FPlex(int maxsize) +{ + if (maxsize == 0) error("invalid constructor specification"); + lo = fnc = 0; + if (maxsize > 0) + { + csize = maxsize; + * data = new [csize]; + hd = new IChunk(data, lo, lo, fnc, csize); + } + else + { + csize = -maxsize; + * data = new [csize]; + hd = new IChunk(data, maxsize, lo, fnc, fnc); + } +} + + +FPlex:: FPlex(int l, int maxsize) +{ + if (maxsize == 0) error("invalid constructor specification"); + lo = fnc = l; + if (maxsize > 0) + { + csize = maxsize; + * data = new [csize]; + hd = new IChunk(data, lo, lo, fnc, csize+lo); + } + else + { + csize = -maxsize; + * data = new [csize]; + hd = new IChunk(data, maxsize+lo, lo, fnc, fnc); + } +} + +FPlex:: FPlex(int l, int hi, const initval, int maxsize) +{ + lo = l; + fnc = hi + 1; + if (maxsize >= 0) + { + csize = maxsize; + if (csize < fnc - lo) + csize = fnc - lo; + * data = new [csize]; + hd = new IChunk(data, lo, lo, fnc, csize); + } + else + { + csize = -maxsize; + if (csize < fnc - lo) + csize = fnc - lo; + * data = new [csize]; + hd = new IChunk(data, -csize, lo, fnc, fnc); + } + fill(initval); +} + +FPlex::FPlex(const FPlex& a) +{ + lo = a.lo; + fnc = a.fnc; + csize = fnc - lo; + if (csize < a.csize) csize = a.csize; + * data = new [csize]; + hd = new IChunk(data, lo, lo, fnc, lo+csize); + for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i]; +} + +void FPlex::operator= (const FPlex& a) +{ + if (&a != this) + { + del_chunk(hd); + lo = a.lo; + fnc = a.fnc; + csize = fnc - lo; + if (csize < a.csize) csize = a.csize; + * data = new [csize]; + hd = new IChunk(data, lo, lo, fnc, lo+csize); + for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i]; + } +} + + +void FPlex::append (const FPlex& a) +{ + for (int i = a.low(); i < a.fence(); a.next(i)) add_high(a[i]); +} + +void FPlex::prepend (const FPlex& a) +{ + for (int i = a.high(); i > a.ecnef(); a.prev(i)) add_low(a[i]); +} + +void FPlex::reverse() +{ + tmp; + int l = lo; + int h = fnc - 1; + while (l < h) + { + tmp = (*this)[l]; + (*this)[l] = (*this)[h]; + (*this)[h] = tmp; + next(l); + prev(h); + } +} + +void FPlex::fill(const x) +{ + for (int i = lo; i < fnc; ++i) (*this)[i] = x; +} + +void FPlex::fill(const x, int lo, int hi) +{ + for (int i = lo; i <= hi; ++i) (*this)[i] = x; +} + +void FPlex::clear() +{ + if (fnc != lo) + { + hd->clear(lo); + fnc = lo; + } +} + +int FPlex::OK () const +{ + int v = hd != 0; // hd exists + v &= hd->IChunk::OK(); // and is OK + v &= fnc - lo <= hd->size(); // and has enough space + v &= lo <= fnc; // plex indices consistent + v &= lo == hd->low_index(); // and match those + v &= fnc == hd->fence_index(); // of chunk + v &= one_chunk(); // and only one chunk + if (!v) error("invariant failure"); + return v; +} + diff --git a/usr/src/lib/libg++/g++-include/gen/OSLBag.ccP b/usr/src/lib/libg++/g++-include/gen/OSLBag.ccP new file mode 100644 index 0000000000..79c95cbe51 --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/OSLBag.ccP @@ -0,0 +1,201 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include ".OSLBag.h" + + +Pix OSLBag::seek( item, Pix i) +{ + if (i == 0) i = p.first(); else next(i); + for (; i != 0; p.next(i)) + { + int cmp = CMP(item, p(i)); + if (cmp == 0) + return i; + else if (cmp < 0) + return 0; + } + return 0; +} + +int OSLBag::nof( item) +{ + int n = 0; + for (Pix i = p.first(); i != 0; p.next(i)) + { + int cmp = CMP(item, p(i)); + if (cmp == 0) + ++n; + else if (cmp < 0) + break; + } + return n; +} + +Pix OSLBag::add( item) +{ + Pix i = p.first(); + if (i == 0) + { + ++count; + return p.prepend(item); + } + int cmp = CMP(item, p(i)); + if (cmp <= 0) + { + ++count; + return p.prepend(item); + } + else + { + Pix trail = i; + p.next(i); + for (;;) + { + if (i == 0) + { + ++count; + return p.append(item); + } + cmp = CMP(item, p(i)); + if (cmp <= 0) + { + ++count; + return p.ins_after(trail, item); + } + else + { + trail = i; + p.next(i); + } + } + } +} + +void OSLBag::del( item) +{ + Pix i = p.first(); + if (i == 0) + return; + int cmp = CMP(item, p(i)); + if (cmp < 0) + return; + else if (cmp == 0) + { + --count; + p.del_front(); + } + else + { + Pix trail = i; + p.next(i); + while (i != 0) + { + cmp = CMP(item, p(i)); + if (cmp < 0) + return; + else if (cmp == 0) + { + --count; + p.del_after(trail); + return; + } + else + { + trail = i; + p.next(i); + } + } + } +} + +void OSLBag::remove( item) +{ + Pix i = p.first(); + if (i == 0) + return; + int cmp = CMP(item, p(i)); + if (cmp < 0) + return; + else if (cmp == 0) + { + do + { + --count; + p.del_front(); + i = p.first(); + } while (i != 0 && EQ(item, p(i))); + } + else + { + Pix trail = i; + p.next(i); + while (i != 0) + { + cmp = CMP(item, p(i)); + if (cmp < 0) + return; + else if (cmp == 0) + { + do + { + --count; + p.del_after(trail); + i = trail; + next(i); + } while (i != 0 && EQ(item, p(i))); + return; + } + else + { + trail = i; + p.next(i); + } + } + } +} + +int OSLBag::OK() +{ + int v = p.OK(); + v &= count == p.length(); + Pix trail = p.first(); + if (trail == 0) + v &= count == 0; + else + { + Pix i = trail; next(i); + while (i != 0) + { + v &= CMP(p(trail), p(i)) <= 0; + trail = i; + next(i); + } + } + if (!v) error("invariant failure"); + return v; +} + diff --git a/usr/src/lib/libg++/g++-include/gen/OXPBag.ccP b/usr/src/lib/libg++/g++-include/gen/OXPBag.ccP new file mode 100644 index 0000000000..2a396441c0 --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/OXPBag.ccP @@ -0,0 +1,226 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include ".OXPBag.h" + + +Pix OXPBag::seek( item, Pix i) +{ + if (i == 0) + { + int l = p.low(); + int h = p.high(); + while (l <= h) + { + int mid = (l + h) / 2; + int cmp = CMP(item, p[mid]); + if (cmp == 0) + { + while (mid > p.low() && EQ(item, p[mid - 1])) --mid; + return p.index_to_Pix(mid); + } + else if (cmp < 0) + h = mid - 1; + else + l = mid + 1; + } + return 0; + } + int cmp = CMP(item, p(i)); + if (cmp == 0) + { + next(i); + return (EQ(item, p(i)))? i : 0; + } + else if (cmp < 0) + { + int ind = p.Pix_to_index(i); + int l = ind; + int h = p.high(); + while (l <= h) + { + int mid = (l + h) / 2; + cmp = CMP(item, p[mid]); + if (cmp == 0) + { + while (mid > ind && EQ(item, p[mid - 1])) --mid; + return p.index_to_Pix(mid); + } + else if (cmp < 0) + h = mid - 1; + else + l = mid + 1; + } + return 0; + } + else + return 0; +} + +int OXPBag::nof( item) +{ + int l = p.low(); + int h = p.high(); + while (l <= h) + { + int mid = (l + h) / 2; + int cmp = CMP(item, p[mid]); + if (cmp == 0) + { + l = h = mid; + while (l > p.low() && EQ(item, p[l - 1])) --l; + while (h < p.high() && EQ(item, p[h + 1])) ++h; + return h - l + 1; + } + else if (cmp < 0) + h = mid - 1; + else + l = mid + 1; + } + return 0; +} + +Pix OXPBag::add( item) +{ + if (count == 0) + { + ++count; + return p.index_to_Pix(p.add_high(item)); + } + int l = p.low(); + int h = p.high(); + while (l <= h) + { + int mid = (l + h) / 2; + int cmp = CMP(item, p[mid]); + if (cmp == 0) + { + l = mid; + break; + } + else if (cmp < 0) + h = mid - 1; + else + l = mid + 1; + } + // add on whichever side is shortest + ++count; + if (l == p.fence()) + return p.index_to_Pix(p.add_high(item)); + else if (l == p.low()) + return p.index_to_Pix(p.add_low(item)); + else + { + if (p.high() - l < l - p.low()) + { + h = p.add_high(p.high_element()); + for (int i = h - 1; i > l; --i) p[i] = p[i-1]; + } + else + { + --l; + h = p.add_low(p.low_element()); + for (int i = h + 1; i < l; ++i) p[i] = p[i+1]; + } + p[l] = item; + return p.index_to_Pix(l); + } +} + +void OXPBag::del( item) +{ + int l = p.low(); + int h = p.high(); + while (l <= h) + { + int mid = (l + h) / 2; + int cmp = CMP(item, p[mid]); + if (cmp == 0) + { + --count; + if (p.high() - mid < mid - p.low()) + { + for (int i = mid; i < p.high(); ++i) p[i] = p[i+1]; + p.del_high(); + } + else + { + for (int i = mid; i > p.low(); --i) p[i] = p[i-1]; + p.del_low(); + } + return; + } + else if (cmp < 0) + h = mid - 1; + else + l = mid + 1; + } +} + +void OXPBag::remove( item) +{ + int l = p.low(); + int h = p.high(); + while (l <= h) + { + int mid = (l + h) / 2; + int cmp = CMP(item, p[mid]); + if (cmp == 0) + { + l = h = mid; + while (l > p.low() && EQ(item, p[l - 1])) --l; + while (h < p.high() && EQ(item, p[h + 1])) ++h; + int n = h - l + 1; + count -= n; + if (p.high() - h < l - p.low()) + { + h = p.high() - n; + for (int i = l; i <= h; ++i) p[i] = p[i+n]; + while (n-- > 0) p.del_high(); + } + else + { + l = p.low() + n; + for (int i = h; i >= l; --i) p[i] = p[i-n]; + while (n-- > 0) p.del_low(); + } + return; + } + else if (cmp < 0) + h = mid - 1; + else + l = mid + 1; + } +} + +int OXPBag::OK() +{ + int v = p.OK(); + v &= count == p.length(); + for (int i = p.low(); i < p.high(); ++i) v &= CMP(p[i], p[i+1]) <= 0; + if (!v) error("invariant failure"); + return v; +} diff --git a/usr/src/lib/libg++/g++-include/gen/PHPQ.ccP b/usr/src/lib/libg++/g++-include/gen/PHPQ.ccP new file mode 100644 index 0000000000..cc688732c3 --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/PHPQ.ccP @@ -0,0 +1,342 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Dirk Grunwald (grunwald@cs.uiuc.edu) + adapted for libg++ by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + + +#ifdef __GNUG__ +#pragma implementation +#endif +#include +#include ".PHPQ.h" + +// +// This defines a Pairing Heap structure +// +// See ``The Pairing Heap: A New Form of Self-Adjusting Heap'' +// Fredman, Segdewick et al, +// Algorithmica (1986) 1:111-129 +// +// In particular, this implements the pairing heap using the circular +// list. +// +// + +PHPQ::PHPQ(int sz) +{ + storage = 0; + root = 0; + count = 0; + size = 0; + prealloc(sz); +} + +PHPQ::PHPQ(PHPQ& a) +{ + storage = 0; + root = 0; + count = 0; + size = 0; + prealloc(a.size); + for (Pix i = a.first(); i != 0; a.next(i)) enq(a(i)); +} + + +void PHPQ::prealloc(int newsize) +{ + ++newsize; // leave a spot for freelist + if (size != 0) + { + int news = size; + while (news <= newsize) news = (news * 3) / 2; + newsize = news; + } + // see if indices are OK + PHPQNode test; + test.sibling = 0; + test.sibling = ~test.sibling; + if ((unsigned long)newsize > (unsigned long)(test.sibling)) + error("storage size exceeds index range"); + + if (storage == 0) + { + storage = new PHPQNode[size = newsize]; + for (int i = 0; i < size; ++i) + { + storage[i].sibling = i + 1; + storage[i].valid = 0; + } + storage[size-1].sibling = 0; + } + else + { + PHPQNode* newstor = new PHPQNode[newsize]; + for (int i = 1; i < size; ++i) + newstor[i] = storage[i]; + delete [size] storage; + storage = newstor; + for (i = size; i < newsize; ++i) + { + storage[i].sibling = i + 1; + storage[i].valid = 0; + } + storage[newsize-1].sibling = 0; + storage[0].sibling = size; + size = newsize; + } +} + + +void PHPQ::clear() +{ + for (int i = 0; i < size; ++i) + { + storage[i].sibling = i + 1; + storage[i].valid = 0; + } + storage[size-1].sibling = 0; + root = 0; + count = 0; +} + +Pix PHPQ::enq( item) +{ + ++count; + if (storage[0].sibling == 0) + prealloc(count); + + int cell = storage[0].sibling; + storage[0].sibling = storage[cell].sibling; + storage[cell].sibling = 0; + storage[cell].children = 0; + storage[cell].item = item; + storage[cell].valid = 1; + + if (root == 0) + { + root = cell; + return Pix(root); + } + else + { + int parent; + int child; + + if (LE(storage[root].item, storage[cell].item)) + { + parent = root; child = cell; + } + else + { + parent = cell; child = root; + } + int popsKid = storage[parent].children; + + if (popsKid == 0) + { + storage[parent].children = child; + storage[child].sibling = child; + } + else + { + int temp = storage[popsKid].sibling; + storage[popsKid].sibling = child; + storage[child].sibling = temp; + storage[parent].children = child; + } + root = parent; + return Pix(cell); + } +} + +// +// Item removal is the most complicated routine. +// +// We remove the root (should there be one) and then select a new +// root. The siblings of the root are in a circular list. We continue +// to pair elements in this list until there is a single element. +// This element will be the new root. + +void PHPQ::del_front() +{ + int valid = 0; + do + { + if (root == 0) return; + if (valid = storage[root].valid) + --count; + storage[root].valid = 0; + int child = storage[root].children; + storage[root].sibling = storage[0].sibling; + storage[0].sibling = root; + + if (child == 0) + { + root = 0; + return; + } + else + { + while(storage[child].sibling != child) + { + // We have at least two kids, but we may only have + // two kids. So, oneChild != child, but it is possible + // that twoChild == child. + + int oneChild = storage[child].sibling; + int twoChild = storage[oneChild].sibling; + + // Remove the two from the sibling list + + storage[child].sibling = storage[twoChild].sibling; + storage[oneChild].sibling = 0; + storage[twoChild].sibling = 0; + + int bestChild; + int worstChild; + + if (LE(storage[oneChild].item, storage[twoChild].item)) + { + bestChild = oneChild; worstChild = twoChild; + } + else + { + bestChild = twoChild; worstChild = oneChild; + } + int popsKid = storage[bestChild].children; + + if (popsKid == 0) + { + storage[bestChild].children = worstChild; + storage[worstChild].sibling = worstChild; + } + else + { + int temp = storage[popsKid].sibling; + storage[popsKid].sibling = worstChild; + storage[worstChild].sibling = temp; + storage[bestChild].children = worstChild; + } + if (twoChild == child) + { + // We have reduced the two to one, so we'll be exiting. + child = bestChild; + storage[child].sibling = child; + } + else + { + // We've removed two siblings, now we need to insert + // the better of the two + storage[bestChild].sibling = storage[child].sibling; + storage[child].sibling = bestChild; + child = storage[bestChild].sibling; + } + } + root = child; + } + } while ( !valid ); +} + +void PHPQ::del(Pix p) +{ + if (p == 0) error("null Pix"); + int i = int(p); + if (storage[i].valid) + { + if (i == root) + del_front(); + else + { + storage[i].valid = 0; + --count; + } + } +} + + +Pix PHPQ::seek( key) +{ + for (int i = 1; i < size; ++i) + if (storage[i].valid && EQ(storage[i].item, key)) + return Pix(i); + return 0; +} + +Pix PHPQ::first() +{ + for (int i = 1; i < size; ++i) + if (storage[i].valid) + return Pix(i); + return 0; +} + + +void PHPQ::next(Pix& p) +{ + if (p == 0) return; + for (int i = int(p)+1; i < size; ++i) + if (storage[i].valid) + { + p = Pix(i); + return; + } + p = 0; +} + +int PHPQ::OK() +{ + int v = storage != 0; + int n = check_sibling_list(root, 0); + v &= n == count; + int ct = MAXLONG; + n = 0; + int f = storage[0].sibling; + while (f != 0 && ct-- > 0) + { + f = storage[f].sibling; + ++n; + } + v &= ct > 0; + v &= n <= size - count; + if (!v) error("invariant failure"); + return v; +} + + +int PHPQ::check_sibling_list(int t, int cnt) +{ + if (t != 0) + { + int s = t; + long ct = MAXLONG; // Lots of chances to find self! + do + { + if (storage[s].valid) cnt++; + cnt += check_sibling_list(storage[s].children, cnt); + s = storage[s].sibling; + } while (ct-- > 0 && s != t && s != 0); + if (ct <= 0) return -1; + } + return cnt; +} + + diff --git a/usr/src/lib/libg++/g++-include/gen/SLBag.ccP b/usr/src/lib/libg++/g++-include/gen/SLBag.ccP new file mode 100644 index 0000000000..172a652da3 --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/SLBag.ccP @@ -0,0 +1,110 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include ".SLBag.h" + +int SLBag::OK() +{ + int v = p.OK(); + v &= count == p.length(); + if (!v) error("invariant failure"); + return v; +} + +Pix SLBag::seek( item, Pix i) +{ + if (i == 0) i = first(); else next(i); + for (; i != 0 && (!(EQ(p(i), item))); p.next(i)); + return i; +} + +int SLBag::nof( item) +{ + int n = 0; + for (Pix p = first(); p; next(p)) if (EQ((*this)(p), item)) ++n; + return n; +} + + +void SLBag::del( item) +{ + Pix i = p.first(); + if (i == 0) + return; + else if (EQ(p(i), item)) + { + --count; + p.del_front(); + } + else + { + Pix trail = i; + p.next(i); + while (i != 0) + { + if (EQ(p(i), item)) + { + --count; + p.del_after(trail); + return; + } + trail = i; + p.next(i); + } + } +} + +void SLBag::remove( item) +{ + Pix i = p.first(); + while (i != 0 && EQ(p(i), item)) + { + --count; + p.del_front(); + i = p.first(); + } + if (i != 0) + { + Pix trail = i; + p.next(i); + while (i != 0) + { + if (EQ(p(i), item)) + { + --count; + p.del_after(trail); + i = trail; + p.next(i); + } + else + { + trail = i; + p.next(i); + } + } + } +} + diff --git a/usr/src/lib/libg++/g++-include/gen/SplayBag.ccP b/usr/src/lib/libg++/g++-include/gen/SplayBag.ccP new file mode 100644 index 0000000000..1e16a7e45d --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/SplayBag.ccP @@ -0,0 +1,451 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include +#include +#include ".SplayBag.h" + + +/* + + struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985 + splay tree algorithms + + All routines use a version of their `simple top-down' splay alg. (p 669) + +*/ + +struct _dummySplayNode +{ + SplayNode* lt; + SplayNode* rt; + SplayNode* par; +} _dummy_null; + + +/* + traversal primitives +*/ + + +SplayNode* SplayBag::leftmost() +{ + SplayNode* t = root; + if (t != 0) while (t->lt != 0) t = t->lt; + return t; +} + +SplayNode* SplayBag::rightmost() +{ + SplayNode* t = root; + if (t != 0) while (t->rt != 0) t = t->rt; + return t; +} + +SplayNode* SplayBag::succ(SplayNode* t) +{ + if (t == 0) + return 0; + if (t->rt != 0) + { + t = t->rt; + while (t->lt != 0) t = t->lt; + return t; + } + else + { + for (;;) + { + if (t->par == 0 || t == t->par->lt) + return t->par; + else + t = t->par; + } + } +} + +SplayNode* SplayBag::pred(SplayNode* t) +{ + if (t == 0) + return 0; + else if (t->lt != 0) + { + t = t->lt; + while (t->rt != 0) t = t->rt; + return t; + } + else + { + for (;;) + { + if (t->par == 0 || t == t->par->rt) + return t->par; + else + t = t->par; + } + } +} + + + +Pix SplayBag::seek( key, Pix i) +{ + if (root == 0) return 0; + + SplayNode* t = (SplayNode*) i; + if (t != 0) + { + int cmp = CMP(key, t->item); + if (cmp == 0) + { + t = succ(t); + if (t != 0 && EQ(key, t->item)) + return Pix(t); + else + return 0; + } + else if (cmp < 0) + return 0; + } + + t = root; + int comp = CMP(key, t->item); + if (comp == 0) + return Pix(t); + + SplayNode* dummy = (SplayNode*)(&_dummy_null); + SplayNode* l = dummy; + SplayNode* r = dummy; + dummy->rt = dummy->lt = dummy->par = 0; + + while (comp != 0) + { + if (comp > 0) + { + SplayNode* tr = t->rt; + if (tr == 0) + break; + else + { + comp = CMP(key, tr->item); + if (comp <= 0 || tr->rt == 0) + { + l->rt = t; t->par = l; + l = t; + t = tr; + if (comp >= 0) + break; + } + else + { + if ((t->rt = tr->lt) != 0) t->rt->par = t; + tr->lt = t; t->par = tr; + l->rt = tr; tr->par = l; + l = tr; + t = tr->rt; + comp = CMP(key, t->item); + } + } + } + else + { + SplayNode* tl = t->lt; + if (tl == 0) + break; + else + { + comp = CMP(key, tl->item); + if (comp >= 0 || tl->lt == 0) + { + r->lt = t; t->par = r; + r = t; + t = tl; + if (comp <= 0) + break; + } + else + { + if ((t->lt = tl->rt) != 0) t->lt->par = t; + tl->rt = t; t->par = tl; + r->lt = tl; tl->par = r; + r = tl; + t = tl->lt; + comp = CMP(key, t->item); + } + } + } + } + if ((r->lt = t->rt) != 0) r->lt->par = r; + if ((l->rt = t->lt) != 0) l->rt->par = l; + if ((t->lt = dummy->rt) != 0) t->lt->par = t; + if ((t->rt = dummy->lt) != 0) t->rt->par = t; + t->par = 0; + root = t; + if (comp != 0) + return 0; + else + { + l = pred(t); + while (l != 0 && EQ(l->item, key)) { t = l; l = pred(l); } + return Pix(t); + } +} + +int SplayBag::nof( item) +{ + int n = 0; + SplayNode* t = (SplayNode*)(seek(item)); + if (t != 0) + { + do + { + ++n; + t = succ(t); + } while (t != 0 && EQ(item, t->item)); + } + return n; +} + +Pix SplayBag::add( item) +{ + ++count; + SplayNode* newnode = new SplayNode(item); + SplayNode* t = root; + if (t == 0) + { + root = newnode; + return Pix(root); + } + + int comp = CMP(item, t->item); + + SplayNode* dummy = (SplayNode*)(&_dummy_null); + SplayNode* l = dummy; + SplayNode* r = dummy; + dummy->rt = dummy->lt = dummy->par = 0; + + int done = 0; + while (!done) + { + if (comp >= 0) + { + SplayNode* tr = t->rt; + if (tr == 0) + { + tr = newnode; + comp = 0; done = 1; + } + else + comp = CMP(item, tr->item); + + if (comp <= 0) + { + l->rt = t; t->par = l; + l = t; + t = tr; + } + else + { + SplayNode* trr = tr->rt; + if (trr == 0) + { + trr = newnode; + comp = 0; done = 1; + } + else + comp = CMP(item, trr->item); + + if ((t->rt = tr->lt) != 0) t->rt->par = t; + tr->lt = t; t->par = tr; + l->rt = tr; tr->par = l; + l = tr; + t = trr; + } + } + else + { + SplayNode* tl = t->lt; + if (tl == 0) + { + tl = newnode; + comp = 0; done = 1; + } + else + comp = CMP(item, tl->item); + + if (comp >= 0) + { + r->lt = t; t->par = r; + r = t; + t = tl; + } + else + { + SplayNode* tll = tl->lt; + if (tll == 0) + { + tll = newnode; + comp = 0; done = 1; + } + else + comp = CMP(item, tll->item); + + if ((t->lt = tl->rt) != 0) t->lt->par = t; + tl->rt = t; t->par = tl; + r->lt = tl; tl->par = r; + r = tl; + t = tll; + } + } + } + if ((r->lt = t->rt) != 0) r->lt->par = r; + if ((l->rt = t->lt) != 0) l->rt->par = l; + if ((t->lt = dummy->rt) != 0) t->lt->par = t; + if ((t->rt = dummy->lt) != 0) t->rt->par = t; + t->par = 0; + root = t; + return Pix(root); +} + +void SplayBag::_del(SplayNode* t) +{ + if (t == 0) return; + + SplayNode* p = t->par; + + --count; + if (t->rt == 0) + { + if (t == root) + { + if ((root = t->lt) != 0) root->par = 0; + } + else if (t == p->lt) + { + if ((p->lt = t->lt) != 0) p->lt->par = p; + } + else + if ((p->rt = t->lt) != 0) p->rt->par = p; + } + else + { + SplayNode* r = t->rt; + SplayNode* l = r->lt; + for(;;) + { + if (l == 0) + { + if (t == root) + { + root = r; + r->par = 0; + } + else if (t == p->lt) + { + p->lt = r; + r->par = p; + } + else + { + p->rt = r; + r->par = p; + } + if ((r->lt = t->lt) != 0) r->lt->par = r; + break; + } + else + { + if ((r->lt = l->rt) != 0) r->lt->par = r; + l->rt = r; r->par = l; + r = l; + l = l->lt; + } + } + } + delete t; +} + + +void SplayBag::remove( key) +{ + SplayNode* t = (SplayNode*)(seek(key)); + while (t != 0) + { + _del(t); + t = (SplayNode*)(seek(key)); + } +} + + +void SplayBag::_kill(SplayNode* t) +{ + if (t != 0) + { + _kill(t->lt); + _kill(t->rt); + delete t; + } +} + + +SplayNode* SplayBag::_copy(SplayNode* t) +{ + if (t != 0) + { + SplayNode* l = _copy(t->lt); + SplayNode* r = _copy(t->rt); + SplayNode* x = new SplayNode(t->item, l, r); + if (l != 0) l->par = x; + if (r != 0) r->par = x; + return x; + } + else + return 0; +} + +int SplayBag::OK() +{ + int v = 1; + if (root == 0) + v = count == 0; + else + { + int n = 1; + SplayNode* trail = leftmost(); + SplayNode* t = succ(trail); + while (t != 0) + { + ++n; + v &= CMP(trail->item, t->item) <= 0; + trail = t; + t = succ(t); + } + v &= n == count; + } + if (!v) error("invariant failure"); + return v; +} + diff --git a/usr/src/lib/libg++/g++-include/gen/VOHSet.ccP b/usr/src/lib/libg++/g++-include/gen/VOHSet.ccP new file mode 100644 index 0000000000..382e1e96fc --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/VOHSet.ccP @@ -0,0 +1,313 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + based on code by Doug Schmidt + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include +#include ".VOHSet.h" + + +/* codes for status fields */ +#define EMPTYCELL 0 +#define VALIDCELL 1 +#define DELETEDCELL 2 + + +VOHSet::VOHSet(int sz) +{ +// The size of the hash table is always the smallest power of 2 >= the size +// indicated by the user. This allows several optimizations, including +// the use of actual double hashing and elimination of the mod instruction. + + size = 1; + while (size < sz) size <<= 1; + tab = new [size]; + status = new char[size]; + for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; + count = cnt = 0; +} + +VOHSet::VOHSet(VOHSet& a) +{ + tab = new [size = a.size]; + status = new char[size]; + for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; + count = cnt = 0; + for (Pix p = a.first(); p; a.next(p)) add(a(p)); +} + +Pix VOHSet::seek( key) +{ +// Uses ordered double hashing to perform a search of the table. +// This greatly speeds up the average-case time for an unsuccessful search. + + unsigned hashval = HASH(key); + + // We can avoid the mod operation since size is a power of 2. + unsigned h = hashval & (size - 1); + + // The increment must be odd, since all odd numbers are relatively + // prime to a power of 2!! + unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1)); + + // There is always at least 1 empty cell, so this loop is guaranteed to halt! + while (status[h] != EMPTYCELL) + { + int cmp = CMP (key, tab[h]); + if (cmp == 0) + { + if (status[h] == VALIDCELL) + return Pix(&tab[h]); + else + return 0; + } + else if (cmp > 0) + return 0; + else + h = ((h + inc) & (size - 1)); + } + return 0; +} + +// This adds an item if it doesn't already exist. By performing the initial +// comparison we assure that the table always contains at least 1 empty +// spot. This speeds up later searching by a constant factor. +// The insertion algorithm uses ordered double hashing. See Standish's +// 1980 ``Data Structure's Techniques'' book for details. + +Pix VOHSet::add( x) +{ + if (size <= cnt+1) + resize(); + + unsigned hashval = HASH(x); + unsigned h = hashval & (size - 1); + + if (status[h] != VALIDCELL) // save some work if possible + { + if (status[h] == EMPTYCELL) + cnt++; + count++; + tab[h] = x; + status[h] = VALIDCELL; + return Pix(&tab[h]); + } + int cmp = CMP(x, tab[h]); + if (cmp == 0) + return Pix(&tab[h]); + + item = x; + Pix mypix = 0; + unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1)); + + for (;;) + { + if (cmp < 0) + { + temp = tab[h]; + tab[h] = item; + item = temp; + if (mypix == 0) mypix = Pix(&tab[h]); + inc = ((((HASH(item) / size) << 1) + 1) & (size - 1)); + h = ((h + inc) & (size - 1)); + cmp = CMP(item, tab[h]); + } + else + h = ((h + inc) & (size - 1)); + if (status[h] != VALIDCELL) + { + if (status[h] == EMPTYCELL) + cnt++; + count++; + tab[h] = item; + status[h] = VALIDCELL; + return (mypix == 0)? Pix(&tab[h]) : mypix; + } + } +} + + +void VOHSet::del( key) +{ +// This performs a deletion by marking the item's status field. +// Note that we only decrease the count, *not* the cnt, since this +// would cause trouble for subsequent steps in the algorithm. See +// Reingold and Hanson's ``Data Structure's'' book for a justification +// of this approach. + + unsigned hashval = HASH(key); + unsigned h = hashval & (size - 1); + unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1)); + + while (status[h] != EMPTYCELL) + { + int cmp = CMP(key, tab[h]); + if (cmp < 0) + h = ((h + inc) & (size - 1)); + else if (status[h] == VALIDCELL && cmp == 0) + { + status[h] = DELETEDCELL; + count--; + return; + } + else + return; + } +} + +void VOHSet::clear() +{ + for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; + count = cnt = 0; +} + +void VOHSet::resize(int newsize) +{ + if (newsize <= count) + newsize = count; + int s = 1; + while (s <= newsize) s <<= 1; + newsize = s; + + * oldtab = tab; + char* oldstatus = status; + int oldsize = size; + tab = new [size = newsize]; + status = new char[size]; + for (int i = 0; i < size; ++i) status[i] = EMPTYCELL; + count = cnt = 0; + + for (i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]); + delete [oldsize] oldtab; + delete oldstatus; +} + +Pix VOHSet::first() +{ + for (int pos = 0; pos < size; ++pos) + if (status[pos] == VALIDCELL) return Pix(&tab[pos]); + return 0; +} + +void VOHSet::next(Pix& i) +{ + if (i == 0) return; + int pos = ((unsigned)i - (unsigned)tab) / sizeof() + 1; + for (; pos < size; ++pos) + if (status[pos] == VALIDCELL) + { + i = Pix(&tab[pos]); + return; + } + i = 0; +} + + +int VOHSet:: operator == (VOHSet& b) +{ + if (count != b.count) + return 0; + else + { + for (int i = 0; i < size; ++i) + if (status[i] == VALIDCELL && b.seek(tab[i]) == 0) + return 0; + for (i = 0; i < b.size; ++i) + if (b.status[i] == VALIDCELL && seek(b.tab[i]) == 0) + return 0; + return 1; + } +} + +int VOHSet:: operator != (VOHSet& b) +{ + return !(*this == b); +} + +int VOHSet::operator <= (VOHSet& b) +{ + if (count > b.count) + return 0; + else + { + for (int i = 0; i < size; ++i) + if (status[i] == VALIDCELL && b.seek(tab[i]) == 0) + return 0; + return 1; + } +} + +void VOHSet::operator |= (VOHSet& b) +{ + if (&b == this || b.count == 0) + return; + for (int i = 0; i < b.size; ++i) + if (b.status[i] == VALIDCELL) add(b.tab[i]); +} + +void VOHSet::operator &= (VOHSet& b) +{ + if (&b == this || count == 0) + return; + for (int i = 0; i < size; ++i) + { + if (status[i] == VALIDCELL && b.seek(tab[i]) == 0) + { + status[i] = DELETEDCELL; + --count; + } + } +} + +void VOHSet::operator -= (VOHSet& b) +{ + for (int i = 0; i < size; ++i) + { + if (status[i] == VALIDCELL && b.seek(tab[i]) != 0) + { + status[i] = DELETEDCELL; + --count; + } + } +} + +int VOHSet::OK() +{ + int v = tab != 0; + v &= status != 0; + int n = 0; + for (int i = 0; i < size; ++i) + { + if (status[i] == VALIDCELL) ++n; + else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL) + v = 0; + } + v &= n == count; + if (!v) error("invariant failure"); + return v; +} + + + diff --git a/usr/src/lib/libg++/g++-include/gen/XPBag.ccP b/usr/src/lib/libg++/g++-include/gen/XPBag.ccP new file mode 100644 index 0000000000..59fa706b7a --- /dev/null +++ b/usr/src/lib/libg++/g++-include/gen/XPBag.ccP @@ -0,0 +1,77 @@ +// This may look like C code, but it is really -*- C++ -*- +/* +Copyright (C) 1988 Free Software Foundation + written by Doug Lea (dl@rocky.oswego.edu) + +This file is part of GNU CC. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY. No author or distributor +accepts responsibility to anyone for the consequences of using it +or for whether it serves any particular purpose or works at all, +unless he says so in writing. Refer to the GNU CC General Public +License for full details. + +Everyone is granted permission to copy, modify and redistribute +GNU CC, but only under the conditions described in the +GNU CC General Public License. A copy of this license is +supposed to have been given to you along with GNU CC so you +can know your rights and responsibilities. It should be in a +file named COPYING. Among other things, the copyright notice +and this notice must be preserved on all copies. +*/ + +#ifdef __GNUG__ +#pragma implementation +#endif +#include ".XPBag.h" + +int XPBag::OK() +{ + int v = p.OK(); + v &= count == p.length(); + if (!v) error("invariant failure"); + return v; +} + +Pix XPBag::seek( item, Pix i) +{ + if (i == 0) i = p.first(); else next(i); + for (; i != 0; p.next(i)) if (EQ(p(i), item)) return i; + return 0; +} + +int XPBag::nof( item) +{ + int n = 0; + for (int i = p.low(); i < p.fence(); p.next(i)) if (EQ(p[i], item)) ++n; + return n; +} + +void XPBag::del( item) +{ + for (int i = p.low(); i < p.fence(); p.next(i)) + { + if (EQ(p[i], item)) + { + --count; + p[i] = p.low_element(); + p.del_low(); + return; + } + } +} + +void XPBag::remove( item) +{ + for (int i = p.low(); i < p.fence(); p.next(i)) + { + if (EQ(p[i], item)) + { + --count; + p[i] = p.low_element(); + p.del_low(); + } + } +} + -- 2.20.1