home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / ccp / VHSet < prev    next >
Text File  |  1995-06-16  |  6KB  |  264 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include "<T>.VHSet.h"
  23.  
  24. /* codes for status fields */
  25.  
  26. #define EMPTYCELL   0
  27. #define VALIDCELL   1
  28. #define DELETEDCELL 2
  29.  
  30.  
  31. <T>VHSet::<T>VHSet(unsigned int sz)
  32. {
  33.   tab = new <T>[size = sz];
  34.   status = new char[size];
  35.   for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  36.   count = 0;
  37. }
  38.  
  39. <T>VHSet::<T>VHSet(<T>VHSet& a)
  40. {
  41.   tab = new <T>[size = a.size];
  42.   status = new char[size];
  43.   for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  44.   count = 0;
  45.   for (Pix p = a.first(); p; a.next(p)) add(a(p));
  46. }
  47.  
  48.  
  49. /* 
  50.  * hashing method: double hash based on high bits of hash fct,
  51.  * followed by linear probe. Can't do too much better if table
  52.  * sizes not constrained to be prime.
  53. */
  54.  
  55.  
  56. static inline unsigned int doublehashinc(unsigned int h, unsigned int s)
  57. {
  58.   unsigned int dh =  ((h / s) % s);
  59.   return (dh > 1)? dh : 1;
  60. }
  61.  
  62. Pix <T>VHSet::seek(<T&> key)
  63. {
  64.   unsigned int hashval = <T>HASH(key);
  65.   unsigned int h = hashval % size;
  66.   for (unsigned int i = 0; i <= size; ++i)
  67.   {
  68.     if (status[h] == EMPTYCELL)
  69.       return 0;
  70.     else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
  71.       return Pix(&tab[h]);
  72.     if (i == 0)
  73.       h = (h + doublehashinc(hashval, size)) % size;
  74.     else if (++h >= size)
  75.       h -= size;
  76.   }
  77.   return 0;
  78. }
  79.  
  80.  
  81. Pix <T>VHSet::add(<T&> item)
  82. {
  83.   if (HASHTABLE_TOO_CROWDED(count, size))
  84.     resize();
  85.  
  86.   unsigned int bestspot = size;
  87.   unsigned int hashval = <T>HASH(item);
  88.   unsigned int h = hashval % size;
  89.   for (unsigned int i = 0; i <= size; ++i)
  90.   {
  91.     if (status[h] == EMPTYCELL)
  92.     {
  93.       if (bestspot >= size) bestspot = h;
  94.       tab[bestspot] = item;
  95.       status[bestspot] = VALIDCELL;
  96.       ++count;
  97.       return Pix(&tab[bestspot]);
  98.     }
  99.     else if (status[h] == DELETEDCELL)
  100.     {
  101.       if (bestspot >= size) bestspot = h;
  102.     }
  103.     else if (<T>EQ(tab[h],item))
  104.       return Pix(&tab[h]);
  105.  
  106.     if (i == 0)
  107.       h = (h + doublehashinc(hashval, size)) % size;
  108.     else if (++h >= size)
  109.       h -= size;
  110.   }
  111.   tab[bestspot] = item;
  112.   status[bestspot] = VALIDCELL;
  113.   ++count;
  114.   return Pix(&tab[bestspot]);
  115.  
  116. }
  117.  
  118.  
  119. void <T>VHSet::del(<T&> key)
  120. {
  121.   unsigned int hashval = <T>HASH(key);
  122.   unsigned int h = hashval % size;
  123.   for (unsigned int i = 0; i <= size; ++i)
  124.   {
  125.     if (status[h] == EMPTYCELL)
  126.       return;
  127.     else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
  128.     {
  129.       status[h] = DELETEDCELL;
  130.       --count;
  131.       return;
  132.     }
  133.     if (i == 0)
  134.       h = (h + doublehashinc(hashval, size)) % size;
  135.     else if (++h >= size)
  136.       h -= size;
  137.   }
  138. }
  139.  
  140.  
  141. void <T>VHSet::clear()
  142. {
  143.   for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  144.   count = 0;
  145. }
  146.  
  147. void <T>VHSet::resize(unsigned int newsize)
  148. {
  149.   if (newsize <= count)
  150.   {
  151.     newsize = DEFAULT_INITIAL_CAPACITY;
  152.     while (HASHTABLE_TOO_CROWDED(count, newsize))  newsize <<= 1;
  153.   }
  154.   <T>* oldtab = tab;
  155.   char* oldstatus = status;
  156.   unsigned int oldsize = size;
  157.   tab = new <T>[size = newsize];
  158.   status = new char[size];
  159.   for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  160.   count = 0;
  161.   for (unsigned int i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]);
  162.   delete [] oldtab;
  163.   delete oldstatus;
  164. }
  165.  
  166. Pix <T>VHSet::first()
  167. {
  168.   for (unsigned int pos = 0; pos < size; ++pos)
  169.     if (status[pos] == VALIDCELL) return Pix(&tab[pos]);
  170.   return 0;
  171. }
  172.  
  173. void <T>VHSet::next(Pix& i)
  174. {
  175.   if (i == 0) return;
  176.   unsigned int pos = ((unsigned)i - (unsigned)tab) / sizeof(<T>) + 1;
  177.   for (; pos < size; ++pos)
  178.     if (status[pos] == VALIDCELL)
  179.     {
  180.       i = Pix(&tab[pos]);
  181.       return;
  182.     }
  183.   i = 0;
  184. }
  185.   
  186. int <T>VHSet:: operator == (<T>VHSet& b)
  187. {
  188.   if (count != b.count)
  189.     return 0;
  190.   else
  191.   {
  192.     for (unsigned int i = 0; i < size; ++i)
  193.       if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
  194.           return 0;
  195.     for (unsigned int i = 0; i < b.size; ++i)
  196.       if (b.status[i] == VALIDCELL && seek(b.tab[i]) == 0)
  197.           return 0;
  198.     return 1;
  199.   }
  200. }
  201.  
  202. int <T>VHSet::operator <= (<T>VHSet& b)
  203. {
  204.   if (count > b.count)
  205.     return 0;
  206.   else
  207.   {
  208.     for (unsigned int i = 0; i < size; ++i)
  209.       if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
  210.           return 0;
  211.     return 1;
  212.   }
  213. }
  214.  
  215. void <T>VHSet::operator |= (<T>VHSet& b)
  216. {
  217.   if (&b == this || b.count == 0)
  218.     return;
  219.   for (unsigned int i = 0; i < b.size; ++i)
  220.     if (b.status[i] == VALIDCELL) add(b.tab[i]);
  221. }
  222.  
  223. void <T>VHSet::operator &= (<T>VHSet& b)
  224. {
  225.   if (&b == this || count == 0)
  226.     return;
  227.   for (unsigned int i = 0; i < size; ++i)
  228.   {
  229.     if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
  230.     {
  231.       status[i] = DELETEDCELL;
  232.       --count;
  233.     }
  234.   }
  235. }
  236.  
  237. void <T>VHSet::operator -= (<T>VHSet& b)
  238. {
  239.   for (unsigned int i = 0; i < size; ++i)
  240.   {
  241.     if (status[i] == VALIDCELL && b.seek(tab[i]) != 0)
  242.     {
  243.       status[i] = DELETEDCELL;
  244.       --count;
  245.     }
  246.   }
  247. }
  248.  
  249. int <T>VHSet::OK()
  250. {
  251.   int v = tab != 0;
  252.   v &= status != 0;
  253.   int n = 0;
  254.   for (unsigned int i = 0; i < size; ++i) 
  255.   {
  256.     if (status[i] == VALIDCELL) ++n;
  257.     else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL)
  258.       v = 0;
  259.   }
  260.   v &= n == count;
  261.   if (!v) error("invariant failure");
  262.   return v;
  263. }
  264.