1 files changed, 263 insertions, 0 deletions
diff --git a/gnu/lib/libg++/g++-include/VHSet.ccP b/gnu/lib/libg++/g++-include/VHSet.ccP
new file mode 100644
index 000000000000..a78b319834c1
--- /dev/null
+++ b/gnu/lib/libg++/g++-include/VHSet.ccP
@@ -0,0 +1,263 @@
+// 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 the GNU C++ Library.  This library is free
+software; you can redistribute it and/or modify it under the terms of
+the GNU Library General Public License as published by the Free
+Software Foundation; either version 2 of the License, or (at your
+option) any later version.  This library is distributed in the hope
+that it will be useful, but WITHOUT ANY WARRANTY; without even the
+implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+PURPOSE.  See the GNU Library General Public License for more details.
+You should have received a copy of the GNU Library General Public
+License along with this library; if not, write to the Free Software
+Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#ifdef __GNUG__
+#pragma implementation
+#endif
+#include "<T>.VHSet.h"
+
+/* codes for status fields */
+
+#define EMPTYCELL   0
+#define VALIDCELL   1
+#define DELETEDCELL 2
+
+
+<T>VHSet::<T>VHSet(unsigned int sz)
+{
+  tab = new <T>[size = sz];
+  status = new char[size];
+  for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
+  count = 0;
+}
+
+<T>VHSet::<T>VHSet(<T>VHSet& a)
+{
+  tab = new <T>[size = a.size];
+  status = new char[size];
+  for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
+  count = 0;
+  for (Pix p = a.first(); p; a.next(p)) add(a(p));
+}
+
+
+/* 
+ * hashing method: double hash based on high bits of hash fct,
+ * followed by linear probe. Can't do too much better if table
+ * sizes not constrained to be prime.
+*/
+
+
+static inline unsigned int doublehashinc(unsigned int h, unsigned int s)
+{
+  unsigned int dh =  ((h / s) % s);
+  return (dh > 1)? dh : 1;
+}
+
+Pix <T>VHSet::seek(<T&> key)
+{
+  unsigned int hashval = <T>HASH(key);
+  unsigned int h = hashval % size;
+  for (unsigned int i = 0; i <= size; ++i)
+  {
+    if (status[h] == EMPTYCELL)
+      return 0;
+    else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
+      return Pix(&tab[h]);
+    if (i == 0)
+      h = (h + doublehashinc(hashval, size)) % size;
+    else if (++h >= size)
+      h -= size;
+  }
+  return 0;
+}
+
+
+Pix <T>VHSet::add(<T&> item)
+{
+  if (HASHTABLE_TOO_CROWDED(count, size))
+    resize();
+
+  unsigned int bestspot = size;
+  unsigned int hashval = <T>HASH(item);
+  unsigned int h = hashval % size;
+  for (unsigned int i = 0; i <= size; ++i)
+  {
+    if (status[h] == EMPTYCELL)
+    {
+      if (bestspot >= size) bestspot = h;
+      tab[bestspot] = item;
+      status[bestspot] = VALIDCELL;
+      ++count;
+      return Pix(&tab[bestspot]);
+    }
+    else if (status[h] == DELETEDCELL)
+    {
+      if (bestspot >= size) bestspot = h;
+    }
+    else if (<T>EQ(tab[h],item))
+      return Pix(&tab[h]);
+
+    if (i == 0)
+      h = (h + doublehashinc(hashval, size)) % size;
+    else if (++h >= size)
+      h -= size;
+  }
+  tab[bestspot] = item;
+  status[bestspot] = VALIDCELL;
+  ++count;
+  return Pix(&tab[bestspot]);
+
+}
+
+
+void <T>VHSet::del(<T&> key)
+{
+  unsigned int hashval = <T>HASH(key);
+  unsigned int h = hashval % size;
+  for (unsigned int i = 0; i <= size; ++i)
+  {
+    if (status[h] == EMPTYCELL)
+      return;
+    else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
+    {
+      status[h] = DELETEDCELL;
+      --count;
+      return;
+    }
+    if (i == 0)
+      h = (h + doublehashinc(hashval, size)) % size;
+    else if (++h >= size)
+      h -= size;
+  }
+}
+
+
+void <T>VHSet::clear()
+{
+  for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
+  count = 0;
+}
+
+void <T>VHSet::resize(unsigned int newsize)
+{
+  if (newsize <= count)
+  {
+    newsize = DEFAULT_INITIAL_CAPACITY;
+    while (HASHTABLE_TOO_CROWDED(count, newsize))  newsize <<= 1;
+  }
+  <T>* oldtab = tab;
+  char* oldstatus = status;
+  unsigned int oldsize = size;
+  tab = new <T>[size = newsize];
+  status = new char[size];
+  for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
+  count = 0;
+  for (i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]);
+  delete [] oldtab;
+  delete oldstatus;
+}
+
+Pix <T>VHSet::first()
+{
+  for (unsigned int pos = 0; pos < size; ++pos)
+    if (status[pos] == VALIDCELL) return Pix(&tab[pos]);
+  return 0;
+}
+
+void <T>VHSet::next(Pix& i)
+{
+  if (i == 0) return;
+  unsigned 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>VHSet:: operator == (<T>VHSet& b)
+{
+  if (count != b.count)
+    return 0;
+  else
+  {
+    for (unsigned 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>VHSet::operator <= (<T>VHSet& b)
+{
+  if (count > b.count)
+    return 0;
+  else
+  {
+    for (unsigned int i = 0; i < size; ++i)
+      if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
+          return 0;
+    return 1;
+  }
+}
+
+void <T>VHSet::operator |= (<T>VHSet& b)
+{
+  if (&b == this || b.count == 0)
+    return;
+  for (unsigned int i = 0; i < b.size; ++i)
+    if (b.status[i] == VALIDCELL) add(b.tab[i]);
+}
+
+void <T>VHSet::operator &= (<T>VHSet& b)
+{
+  if (&b == this || count == 0)
+    return;
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
+    {
+      status[i] = DELETEDCELL;
+      --count;
+    }
+  }
+}
+
+void <T>VHSet::operator -= (<T>VHSet& b)
+{
+  for (unsigned int i = 0; i < size; ++i)
+  {
+    if (status[i] == VALIDCELL && b.seek(tab[i]) != 0)
+    {
+      status[i] = DELETEDCELL;
+      --count;
+    }
+  }
+}
+
+int <T>VHSet::OK()
+{
+  int v = tab != 0;
+  v &= status != 0;
+  int n = 0;
+  for (unsigned 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;
+}