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

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 (file)
index 0000000..b7f97ec
--- /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 "<T>.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(<T>CHNode* t)
+{
+  return ((((unsigned)t) & 1) == 0);
+}
+
+static inline <T>CHNode* index_to_CHptr(int i)
+{
+  return (<T>CHNode*)((i << 1) + 1);
+}
+
+static inline int CHptr_to_index(<T>CHNode* t)
+{
+  return ( ((unsigned) t) >> 1);
+}
+
+<T>CHBag::<T>CHBag(unsigned int sz)
+{
+  tab = (<T>CHNode**)(new <T>CHNodePtr[size = sz]);
+  for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1);
+  count = 0;
+}
+
+<T>CHBag::<T>CHBag(<T>CHBag& a)
+{
+  tab = (<T>CHNode**)(new <T>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 <T>CHBag::seek(<T&> key, Pix i)
+{
+  <T>CHNode* p = (<T>CHNode*)i;
+  if (p == 0 || !<T>EQ(p->hd, key))
+  {
+    unsigned int h = <T>HASH(key) % size;
+    for (<T>CHNode* t = tab[h]; goodCHptr(t); t = t->tl)
+      if (<T>EQ(key, t->hd))
+        return Pix(t);
+  }
+  else
+  {
+    for (p = p->tl; goodCHptr(p); p = p->tl) 
+      if (<T>EQ(p->hd, key))
+        return Pix(p);
+  }
+  return 0;
+}
+
+int <T>CHBag::nof(<T&> key)
+{
+  int n = 0;
+  unsigned int h = <T>HASH(key) % size;
+  for (<T>CHNode* t = tab[h]; goodCHptr(t); t = t->tl) 
+    if (<T>EQ(key, t->hd)) ++n;
+  return n;
+}
+
+
+Pix <T>CHBag::add(<T&> item)
+{
+  unsigned int h = <T>HASH(item) % size;
+  <T>CHNode* t = new <T>CHNode(item);
+  t->tl = tab[h];
+  tab[h] = t;
+  ++count;
+  return Pix(t);
+}
+
+void <T>CHBag::del(<T&> key)
+{
+  unsigned int h = <T>HASH(key) % size;
+
+  <T>CHNode* t = tab[h]; 
+  <T>CHNode* trail = t;
+  while (goodCHptr(t))
+  {
+    if (<T>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 <T>CHBag::remove(<T&> key)
+{
+  unsigned int h = <T>HASH(key) % size;
+
+  <T>CHNode* t = tab[h]; 
+  <T>CHNode* trail = t;
+  while (goodCHptr(t))
+  {
+    if (<T>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 <T>CHBag::clear()
+{
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    <T>CHNode* p = tab[i];
+    tab[i] = index_to_CHptr(i+1);
+    while (goodCHptr(p))
+    {
+      <T>CHNode* nxt = p->tl;
+      delete(p);
+      p = nxt;
+    }
+  }
+  count = 0;
+}
+
+Pix <T>CHBag::first()
+{
+  for (unsigned int i = 0; i < size; ++i) if (goodCHptr(tab[i])) return Pix(tab[i]);
+  return 0;
+}
+
+void <T>CHBag::next(Pix& p)
+{
+  if (p == 0) return;
+  <T>CHNode* t = ((<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 <T>CHBag::OK()
+{
+  int v = tab != 0;
+  int n = 0;
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    for (<T>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 (file)
index 0000000..07c57d3
--- /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 "<T>.CHSet.h"
+
+// A CHSet is implemented as an array (tab) of buckets, each of which
+// contains a pointer to a list of <T>CHNodes.  Each node contains a
+// pointer to the next node in the list, and a pointer to the <T>.
+// 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(<T>CHNode* t)
+{
+  return ((((unsigned)t) & 1) == 0);
+}
+
+static inline <T>CHNode* index_to_CHptr(int i)
+{
+  return (<T>CHNode*)((i << 1) + 1);
+}
+
+static inline int CHptr_to_index(<T>CHNode* t)
+{
+  return ( ((unsigned) t) >> 1);
+}
+
+<T>CHSet::<T>CHSet(unsigned int sz)
+{
+  tab = (<T>CHNode**)(new <T>CHNodePtr[size = sz]);
+  for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1);
+  count = 0;
+}
+
+<T>CHSet::<T>CHSet(<T>CHSet& a)
+{
+  tab = (<T>CHNode**)(new <T>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 <T>CHSet::seek(<T&> key)
+{
+  unsigned int h = <T>HASH(key) % size;
+
+  for (<T>CHNode* t = tab[h]; goodCHptr(t); t = t->tl)
+    if (<T>EQ(key, t->hd))
+      return Pix(t);
+
+  return 0;
+}
+
+
+Pix <T>CHSet::add(<T&> item)
+{
+  unsigned int h = <T>HASH(item) % size;
+
+  for (<T>CHNode* t = tab[h]; goodCHptr(t); t = t->tl)
+    if (<T>EQ(item, t->hd))
+      return Pix(t);
+
+  ++count;
+  t = new <T>CHNode(item, tab[h]);
+  tab[h] = t;
+  return Pix(t);
+}
+
+
+void <T>CHSet::del(<T&> key)
+{
+  unsigned int h = <T>HASH(key) % size;
+
+  <T>CHNode* t = tab[h]; 
+  <T>CHNode* trail = t;
+  while (goodCHptr(t))
+  {
+    if (<T>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 <T>CHSet::clear()
+{
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    <T>CHNode* p = tab[i];
+    tab[i] = index_to_CHptr(i+1);
+    while (goodCHptr(p))
+    {
+      <T>CHNode* nxt = p->tl;
+      delete(p);
+      p = nxt;
+    }
+  }
+  count = 0;
+}
+
+Pix <T>CHSet::first()
+{
+  for (unsigned int i = 0; i < size; ++i) if (goodCHptr(tab[i])) return Pix(tab[i]);
+  return 0;
+}
+
+void <T>CHSet::next(Pix& p)
+{
+  if (p == 0) return;
+  <T>CHNode* t = ((<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 <T>CHSet::operator == (<T>CHSet& b)
+{
+  if (count != b.count)
+    return 0;
+  else
+  {
+    <T>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 <T>CHSet::operator <= (<T>CHSet& b)
+{
+  if (count > b.count)
+    return 0;
+  else
+  {
+    for (unsigned int i = 0; i < size; ++i)
+      for (<T>CHNode* p = tab[i]; goodCHptr(p); p = p->tl)
+        if (b.seek(p->hd) == 0)
+          return 0;
+    return 1;
+  }
+}
+
+void <T>CHSet::operator |= (<T>CHSet& b)
+{
+  if (&b == this || b.count == 0)
+    return;
+  for (unsigned int i = 0; i < b.size; ++i)
+    for (<T>CHNode* p = b.tab[i]; goodCHptr(p); p = p->tl)
+      add(p->hd);
+}
+
+void <T>CHSet::operator &= (<T>CHSet& b)
+{
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    <T>CHNode* t = tab[i]; 
+    <T>CHNode* trail = t;
+    while (goodCHptr(t))
+    {
+      <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 <T>CHSet::operator -= (<T>CHSet& b)
+{
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    <T>CHNode* t = tab[i]; 
+    <T>CHNode* trail = t;
+    while (goodCHptr(t))
+    {
+      <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 <T>CHSet::OK()
+{
+  int v = tab != 0;
+  int n = 0;
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    for (<T>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 (file)
index 0000000..235d290
--- /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 "<T>.FPlex.h"
+
+
+<T>FPlex:: <T>FPlex()
+{
+  lo = fnc = 0;
+  csize = DEFAULT_INITIAL_CAPACITY;
+  <T>* data = new <T>[csize];
+  hd = new <T>IChunk(data,  lo, lo, fnc, csize);
+}
+
+<T>FPlex:: <T>FPlex(int maxsize)
+{
+  if (maxsize == 0) error("invalid constructor specification");
+  lo = fnc = 0;
+  if (maxsize > 0)
+  {
+    csize = maxsize;
+    <T>* data = new <T>[csize];
+    hd = new <T>IChunk(data,  lo, lo, fnc, csize);
+  }
+  else
+  {
+    csize = -maxsize;
+    <T>* data = new <T>[csize];
+    hd = new <T>IChunk(data,  maxsize, lo, fnc, fnc);
+  }
+}
+
+
+<T>FPlex:: <T>FPlex(int l, int maxsize)
+{
+  if (maxsize == 0) error("invalid constructor specification");
+  lo = fnc = l;
+  if (maxsize > 0)
+  {
+    csize = maxsize;
+    <T>* data = new <T>[csize];
+    hd = new <T>IChunk(data,  lo, lo, fnc, csize+lo);
+  }
+  else
+  {
+    csize = -maxsize;
+    <T>* data = new <T>[csize];
+    hd = new <T>IChunk(data,  maxsize+lo, lo, fnc, fnc);
+  }
+}
+
+<T>FPlex:: <T>FPlex(int l, int hi, const <T&> initval, int maxsize)
+{
+  lo = l;
+  fnc = hi + 1;
+  if (maxsize >= 0)
+  {
+    csize = maxsize;
+    if (csize < fnc - lo)
+      csize = fnc - lo;
+    <T>* data = new <T>[csize];
+    hd = new <T>IChunk(data,  lo, lo, fnc, csize);
+  }
+  else
+  {
+    csize = -maxsize;
+    if (csize < fnc - lo)
+      csize = fnc - lo;
+    <T>* data = new <T>[csize];
+    hd = new <T>IChunk(data,  -csize, lo, fnc, fnc);
+  }
+  fill(initval);
+}
+
+<T>FPlex::<T>FPlex(const <T>FPlex& a)
+{
+  lo = a.lo;
+  fnc = a.fnc;
+  csize = fnc - lo;
+  if (csize < a.csize) csize = a.csize;
+  <T>* data = new <T> [csize];
+  hd = new <T>IChunk(data,  lo, lo, fnc, lo+csize);
+  for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
+}
+
+void <T>FPlex::operator= (const <T>FPlex& a)
+{
+  if (&a != this)
+  {
+    del_chunk(hd);
+    lo = a.lo;
+    fnc = a.fnc;
+    csize = fnc - lo;
+    if (csize < a.csize) csize = a.csize;
+    <T>* data = new <T> [csize];
+    hd = new <T>IChunk(data,  lo, lo, fnc, lo+csize);
+    for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
+  }
+}
+
+
+void <T>FPlex::append (const <T>FPlex& a)
+{
+  for (int i = a.low(); i < a.fence(); a.next(i)) add_high(a[i]);
+}
+
+void <T>FPlex::prepend (const <T>FPlex& a)
+{
+  for (int i = a.high(); i > a.ecnef(); a.prev(i)) add_low(a[i]);
+}
+
+void <T>FPlex::reverse()
+{
+  <T> 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 <T>FPlex::fill(const <T&> x)
+{
+  for (int i = lo; i < fnc; ++i) (*this)[i] = x;
+}
+
+void <T>FPlex::fill(const <T&> x, int lo, int hi)
+{
+  for (int i = lo; i <= hi; ++i) (*this)[i] = x;
+}
+
+void <T>FPlex::clear()
+{
+  if (fnc != lo)
+  {
+    hd->clear(lo);
+    fnc = lo;
+  }
+}
+
+int <T>FPlex::OK () const
+{
+  int v = hd != 0;                    // hd exists
+  v &= hd-><T>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 (file)
index 0000000..79c95cb
--- /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 "<T>.OSLBag.h"
+
+
+Pix <T>OSLBag::seek(<T&> item, Pix i)
+{
+  if (i == 0) i = p.first(); else next(i);
+  for (; i != 0; p.next(i))
+  {
+    int cmp = <T>CMP(item, p(i));
+    if (cmp == 0)
+      return i;
+    else if (cmp < 0)
+      return 0;
+  }
+  return 0;
+}
+
+int <T>OSLBag::nof(<T&> item)
+{
+  int n = 0;
+  for (Pix i = p.first(); i != 0; p.next(i))
+  {
+    int cmp = <T>CMP(item, p(i));
+    if (cmp == 0)
+      ++n;
+    else if (cmp < 0)
+      break;
+  }
+  return n;
+}
+
+Pix <T>OSLBag::add(<T&> item)
+{
+  Pix i = p.first();
+  if (i == 0) 
+  {
+    ++count;
+    return p.prepend(item);
+  }
+  int cmp = <T>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 = <T>CMP(item, p(i));
+      if (cmp <= 0)
+      {
+        ++count;
+        return p.ins_after(trail, item);
+      }
+      else
+      {
+        trail = i;
+        p.next(i);
+      }
+    }
+  }
+}
+
+void <T>OSLBag::del(<T&> item)
+{
+  Pix i = p.first();
+  if (i == 0)
+    return;
+  int cmp = <T>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 = <T>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 <T>OSLBag::remove(<T&> item)
+{
+  Pix i = p.first();
+  if (i == 0)
+    return;
+  int cmp = <T>CMP(item, p(i));
+  if (cmp < 0)
+    return;
+  else if (cmp == 0)
+  {
+    do
+    {
+      --count;
+      p.del_front();
+      i = p.first();
+    } while (i != 0 && <T>EQ(item, p(i)));
+  }
+  else
+  {
+    Pix trail = i;
+    p.next(i);
+    while (i != 0)
+    {
+      cmp = <T>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 && <T>EQ(item, p(i)));
+        return;
+      }
+      else
+      {
+        trail = i;
+        p.next(i);
+      }
+    }
+  }
+}
+        
+int <T>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 &= <T>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 (file)
index 0000000..2a39644
--- /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 "<T>.OXPBag.h"
+
+
+Pix <T>OXPBag::seek(<T&> item, Pix i)
+{
+  if (i == 0)
+  {
+    int l = p.low();
+    int h = p.high();
+    while (l <= h)
+    {
+      int mid = (l + h) / 2;
+      int cmp = <T>CMP(item, p[mid]);
+      if (cmp == 0)
+      {
+        while (mid > p.low() && <T>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 = <T>CMP(item, p(i));
+  if (cmp == 0)
+  {
+    next(i);
+    return (<T>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 = <T>CMP(item, p[mid]);
+      if (cmp == 0)
+      {
+        while (mid > ind && <T>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 <T>OXPBag::nof(<T&> item)
+{
+  int l = p.low();
+  int h = p.high();
+  while (l <= h)
+  {
+    int mid = (l + h) / 2;
+    int cmp = <T>CMP(item, p[mid]);
+    if (cmp == 0)
+    {
+      l = h = mid;
+      while (l > p.low() && <T>EQ(item, p[l - 1])) --l;
+      while (h < p.high() && <T>EQ(item, p[h + 1])) ++h;
+      return h - l + 1;
+    }
+    else if (cmp < 0)
+      h = mid - 1;
+    else
+      l = mid + 1;
+  }
+  return 0;
+}
+
+Pix <T>OXPBag::add(<T&> 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 = <T>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 <T>OXPBag::del(<T&> item)
+{
+  int l = p.low();
+  int h = p.high();
+  while (l <= h)
+  {
+    int mid = (l + h) / 2;
+    int cmp = <T>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 <T>OXPBag::remove(<T&> item)
+{
+  int l = p.low();
+  int h = p.high();
+  while (l <= h)
+  {
+    int mid = (l + h) / 2;
+    int cmp = <T>CMP(item, p[mid]);
+    if (cmp == 0)
+    {
+      l = h = mid;
+      while (l > p.low() && <T>EQ(item, p[l - 1])) --l;
+      while (h < p.high() && <T>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 <T>OXPBag::OK()
+{
+  int v = p.OK();
+  v &= count == p.length();
+  for (int i = p.low(); i < p.high(); ++i) v &= <T>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 (file)
index 0000000..cc68873
--- /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 <values.h>
+#include "<T>.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.
+//
+//
+
+<T>PHPQ::<T>PHPQ(int sz)
+{
+  storage = 0;
+  root = 0;
+  count = 0;
+  size = 0;
+  prealloc(sz);
+}
+
+<T>PHPQ::<T>PHPQ(<T>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 <T>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
+  <T>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 <T>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
+  {
+    <T>PHPQNode* newstor = new <T>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 <T>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 <T>PHPQ::enq(<T&> 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 (<T>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 <T>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 (<T>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 <T>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 <T>PHPQ::seek(<T&> key)
+{
+  for (int i = 1; i < size; ++i)
+    if (storage[i].valid && <T>EQ(storage[i].item, key))
+      return Pix(i);
+  return 0;
+}
+
+Pix <T>PHPQ::first()
+{
+  for (int i = 1; i < size; ++i)
+    if (storage[i].valid)
+      return Pix(i);
+  return 0;
+}
+
+
+void <T>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 <T>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 <T>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 (file)
index 0000000..172a652
--- /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 "<T>.SLBag.h"
+
+int <T>SLBag::OK()
+{
+  int v = p.OK();
+  v &= count == p.length();
+  if (!v) error("invariant failure");
+  return v;
+}
+
+Pix <T>SLBag::seek(<T&> item, Pix i)
+{
+  if (i == 0) i = first(); else next(i);
+  for (; i != 0 && (!(<T>EQ(p(i), item))); p.next(i));
+  return i;
+}
+
+int <T>SLBag::nof(<T&> item)
+{
+  int n = 0;
+  for (Pix p = first(); p; next(p)) if (<T>EQ((*this)(p), item)) ++n;
+  return n;
+}
+
+
+void <T>SLBag::del(<T&> item)
+{
+  Pix i = p.first();
+  if (i == 0) 
+    return;
+  else if (<T>EQ(p(i), item))
+  {
+    --count;
+    p.del_front();
+  }
+  else
+  {
+    Pix trail = i;
+    p.next(i);
+    while (i != 0)
+    {
+      if (<T>EQ(p(i), item))
+      {
+        --count;
+        p.del_after(trail);
+        return;
+      }
+      trail = i;
+      p.next(i);
+    }
+  }
+}    
+
+void <T>SLBag::remove(<T&> item)
+{
+  Pix i = p.first();
+  while (i != 0 && <T>EQ(p(i), item))
+  {
+    --count;
+    p.del_front();
+    i = p.first();
+  }
+  if (i != 0)
+  {
+    Pix trail = i;
+    p.next(i);
+    while (i != 0)
+    {
+      if (<T>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 (file)
index 0000000..1e16a7e
--- /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 <stream.h>
+#include <assert.h>
+#include "<T>.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
+{
+  <T>SplayNode*    lt;
+  <T>SplayNode*    rt;
+  <T>SplayNode*    par;
+} _dummy_null;
+
+
+/*
+ traversal primitives
+*/
+
+
+<T>SplayNode* <T>SplayBag::leftmost()
+{
+  <T>SplayNode* t = root;
+  if (t != 0) while (t->lt != 0) t = t->lt;
+  return t;
+}
+
+<T>SplayNode* <T>SplayBag::rightmost()
+{
+  <T>SplayNode* t = root;
+  if (t != 0) while (t->rt != 0) t = t->rt;
+  return t;
+}
+
+<T>SplayNode* <T>SplayBag::succ(<T>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;
+    }
+  }
+}
+
+<T>SplayNode* <T>SplayBag::pred(<T>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 <T>SplayBag::seek(<T&> key, Pix i)
+{
+  if (root == 0) return 0;
+
+  <T>SplayNode* t = (<T>SplayNode*) i;
+  if (t != 0)
+  {
+    int cmp = <T>CMP(key, t->item);
+    if (cmp == 0)
+    {
+      t = succ(t);
+      if (t != 0 && <T>EQ(key, t->item))
+        return Pix(t);
+      else
+        return 0;
+    }
+    else if (cmp < 0)
+      return 0;
+  }
+
+  t = root;
+  int comp = <T>CMP(key, t->item);
+  if (comp == 0)
+    return Pix(t);
+
+  <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
+  <T>SplayNode* l = dummy;
+  <T>SplayNode* r = dummy;
+  dummy->rt = dummy->lt = dummy->par = 0;
+
+  while (comp != 0)
+  {
+    if (comp > 0)
+    {
+      <T>SplayNode* tr = t->rt;
+      if (tr == 0)
+        break;
+      else
+      {
+        comp = <T>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 = <T>CMP(key, t->item);
+        }
+      }
+    }
+    else
+    {
+      <T>SplayNode* tl = t->lt;
+      if (tl == 0)
+        break;
+      else
+      {
+        comp = <T>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 = <T>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 && <T>EQ(l->item, key)) { t = l; l = pred(l); }
+    return Pix(t);
+  }
+}
+
+int <T>SplayBag::nof(<T&> item)
+{
+  int n = 0;
+  <T>SplayNode* t = (<T>SplayNode*)(seek(item));
+  if (t != 0)
+  {
+    do
+    {
+      ++n;
+      t = succ(t);
+    } while (t != 0 && <T>EQ(item, t->item));
+  }
+  return n;
+}
+
+Pix <T>SplayBag::add(<T&> item)
+{
+  ++count;
+  <T>SplayNode* newnode = new <T>SplayNode(item);
+  <T>SplayNode* t = root;
+  if (t == 0)
+  {
+    root = newnode;
+    return Pix(root);
+  }
+
+  int comp = <T>CMP(item, t->item);
+
+  <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
+  <T>SplayNode* l = dummy;
+  <T>SplayNode* r = dummy;
+  dummy->rt = dummy->lt = dummy->par = 0;
+  
+  int done = 0;
+  while (!done)
+  {
+    if (comp >= 0)
+    {
+      <T>SplayNode* tr = t->rt;
+      if (tr == 0)
+      {
+        tr = newnode;
+        comp = 0; done = 1;
+      }
+      else
+        comp = <T>CMP(item, tr->item);
+        
+      if (comp <= 0)
+      {
+        l->rt = t; t->par = l;
+        l = t;
+        t = tr;
+      }
+      else 
+      {
+        <T>SplayNode* trr = tr->rt;
+        if (trr == 0)
+        {
+          trr =  newnode;
+          comp = 0; done = 1;
+        }
+        else
+          comp = <T>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
+    {
+      <T>SplayNode* tl = t->lt;
+      if (tl == 0)
+      {
+        tl = newnode;
+        comp = 0; done = 1;
+      }
+      else
+        comp = <T>CMP(item, tl->item);
+
+      if (comp >= 0)
+      {
+        r->lt = t; t->par = r;
+        r = t;
+        t = tl;
+      }
+      else
+      {
+        <T>SplayNode* tll = tl->lt;
+        if (tll == 0)
+        {
+          tll = newnode;
+          comp = 0; done = 1;
+        }
+        else
+          comp = <T>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 <T>SplayBag::_del(<T>SplayNode* t)
+{
+  if (t == 0) return;
+
+  <T>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
+  {
+    <T>SplayNode* r = t->rt;
+    <T>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 <T>SplayBag::remove(<T&> key)
+{
+  <T>SplayNode* t = (<T>SplayNode*)(seek(key));
+  while (t != 0)
+  {
+    _del(t);
+    t = (<T>SplayNode*)(seek(key));
+  }
+}
+
+
+void <T>SplayBag::_kill(<T>SplayNode* t)
+{
+  if (t != 0)
+  {
+    _kill(t->lt);
+    _kill(t->rt);
+    delete t;
+  }
+}
+
+
+<T>SplayNode* <T>SplayBag::_copy(<T>SplayNode* t)
+{
+  if (t != 0)
+  {
+    <T>SplayNode* l = _copy(t->lt);
+    <T>SplayNode* r = _copy(t->rt);
+    <T>SplayNode* x = new <T>SplayNode(t->item, l, r);
+    if (l != 0) l->par = x;
+    if (r != 0) r->par = x;
+    return x;
+  }
+  else 
+    return 0;
+}
+
+int <T>SplayBag::OK()
+{
+  int v = 1;
+  if (root == 0) 
+    v = count == 0;
+  else
+  {
+    int n = 1;
+    <T>SplayNode* trail = leftmost();
+    <T>SplayNode* t = succ(trail);
+    while (t != 0)
+    {
+      ++n;
+      v &= <T>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 (file)
index 0000000..382e1e9
--- /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 <stream.h>
+#include "<T>.VOHSet.h"
+
+
+/* codes for status fields */
+#define EMPTYCELL   0
+#define VALIDCELL   1
+#define DELETEDCELL 2
+
+
+<T>VOHSet::<T>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 <T>[size];
+  status = new char[size];
+  for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
+  count = cnt = 0;
+}
+
+<T>VOHSet::<T>VOHSet(<T>VOHSet& a)
+{
+  tab = new <T>[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 <T>VOHSet::seek(<T&> 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 = <T>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 = <T>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 <T>VOHSet::add(<T&> x)
+{
+  if (size <= cnt+1) 
+    resize();
+  
+  unsigned hashval = <T>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 = <T>CMP(x, tab[h]);
+  if (cmp == 0)
+    return Pix(&tab[h]);
+
+  <T> item = x;
+  Pix mypix = 0;
+  unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));
+
+  for (;;)
+  {
+    if (cmp < 0)
+    {
+      <T> temp = tab[h];
+      tab[h] = item;
+      item = temp;
+      if (mypix == 0) mypix = Pix(&tab[h]);
+      inc = ((((<T>HASH(item) / size) << 1) + 1) & (size - 1));
+      h = ((h + inc) & (size - 1));
+      cmp = <T>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 <T>VOHSet::del(<T&> 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 = <T>HASH(key);
+  unsigned h   = hashval & (size - 1);
+  unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));
+  
+  while (status[h] != EMPTYCELL)
+  {
+    int cmp = <T>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 <T>VOHSet::clear()
+{
+  for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
+  count = cnt = 0;
+}
+
+void <T>VOHSet::resize(int newsize)
+{
+  if (newsize <= count)
+    newsize = count;
+  int s = 1;
+  while (s <= newsize) s <<= 1;
+  newsize = s;
+
+  <T>* oldtab = tab;
+  char* oldstatus = status;
+  int oldsize = size;
+  tab = new <T>[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 <T>VOHSet::first()
+{
+  for (int pos = 0; pos < size; ++pos)
+    if (status[pos] == VALIDCELL) return Pix(&tab[pos]);
+  return 0;
+}
+
+void <T>VOHSet::next(Pix& i)
+{
+  if (i == 0) return;
+  int pos = ((unsigned)i - (unsigned)tab) / sizeof(<T>) + 1;
+  for (; pos < size; ++pos)
+    if (status[pos] == VALIDCELL)
+    {
+      i = Pix(&tab[pos]);
+      return;
+    }
+  i = 0;
+}
+
+
+int <T>VOHSet:: operator == (<T>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 <T>VOHSet:: operator != (<T>VOHSet& b)
+{
+  return !(*this == b);
+}
+
+int <T>VOHSet::operator <= (<T>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 <T>VOHSet::operator |= (<T>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 <T>VOHSet::operator &= (<T>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 <T>VOHSet::operator -= (<T>VOHSet& b)
+{
+  for (int i = 0; i < size; ++i)
+  {
+    if (status[i] == VALIDCELL && b.seek(tab[i]) != 0)
+    {
+      status[i] = DELETEDCELL;
+      --count;
+    }
+  }
+}
+
+int <T>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 (file)
index 0000000..59fa706
--- /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 "<T>.XPBag.h"
+
+int <T>XPBag::OK()
+{
+  int v = p.OK();
+  v &= count == p.length();
+  if (!v) error("invariant failure");
+  return v;
+}
+
+Pix <T>XPBag::seek(<T&> item, Pix i)
+{
+  if (i == 0) i = p.first(); else next(i);
+  for (; i != 0; p.next(i)) if (<T>EQ(p(i), item)) return i;
+  return 0;
+}
+
+int <T>XPBag::nof(<T&> item)
+{
+  int n = 0;
+  for (int i = p.low(); i < p.fence(); p.next(i)) if (<T>EQ(p[i], item)) ++n;
+  return n;
+}
+
+void <T>XPBag::del(<T&> item)
+{
+  for (int i = p.low(); i < p.fence(); p.next(i))
+  {
+    if (<T>EQ(p[i], item))
+    {
+      --count;
+      p[i] = p.low_element();
+      p.del_low();
+      return;
+    }
+  }
+}
+
+void <T>XPBag::remove(<T&> item)
+{
+  for (int i = p.low(); i < p.fence(); p.next(i))
+  {
+    if (<T>EQ(p[i], item))
+    {
+      --count;
+      p[i] = p.low_element();
+      p.del_low();
+    }
+  }
+}
+