home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / gen / VOHSet.ccP < prev    next >
Encoding:
Text File  |  1995-02-06  |  7.1 KB  |  306 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.      based on code by Doug Schmidt
  6.  
  7. This file is part of the GNU C++ Library.  This library is free
  8. software; you can redistribute it and/or modify it under the terms of
  9. the GNU Library General Public License as published by the Free
  10. Software Foundation; either version 2 of the License, or (at your
  11. option) any later version.  This library is distributed in the hope
  12. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  13. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14. PURPOSE.  See the GNU Library General Public License for more details.
  15. You should have received a copy of the GNU Library General Public
  16. License along with this library; if not, write to the Free Software
  17. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18. */
  19.  
  20. #ifdef __GNUG__
  21. #pragma implementation
  22. #endif
  23. #include <stream.h>
  24. #include "<T>.VOHSet.h"
  25.  
  26.  
  27. /* codes for status fields */
  28. #define EMPTYCELL   0
  29. #define VALIDCELL   1
  30. #define DELETEDCELL 2
  31.  
  32.  
  33. <T>VOHSet::<T>VOHSet(int sz)
  34. {
  35. // The size of the hash table is always the smallest power of 2 >= the size
  36. // indicated by the user.  This allows several optimizations, including
  37. // the use of actual double hashing and elimination of the mod instruction.
  38.  
  39.   size = 1;
  40.   while (size < sz) size <<= 1;
  41.   tab = new <T>[size];
  42.   status = new char[size];
  43.   for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  44.   count = cnt = 0;
  45. }
  46.  
  47. <T>VOHSet::<T>VOHSet(<T>VOHSet& a)
  48. {
  49.   tab = new <T>[size = a.size];
  50.   status = new char[size];
  51.   for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  52.   count = cnt = 0;
  53.   for (Pix p = a.first(); p; a.next(p)) add(a(p));
  54. }
  55.  
  56. Pix <T>VOHSet::seek(<T&> key)
  57. {
  58. // Uses ordered double hashing to perform a search of the table.
  59. // This greatly speeds up the average-case time for an unsuccessful search.
  60.  
  61.   unsigned hashval = <T>HASH(key);
  62.  
  63.   // We can avoid the mod operation since size is a power of 2.
  64.   unsigned h = hashval & (size - 1);
  65.  
  66.   // The increment must be odd, since all odd numbers are relatively
  67.   // prime to a power of 2!!
  68.   unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));
  69.   
  70.   // There is always at least 1 empty cell, so this loop is guaranteed to halt!
  71.   while (status[h] != EMPTYCELL)
  72.   {
  73.     int cmp = <T>CMP (key, tab[h]);
  74.     if (cmp == 0)
  75.     {
  76.       if (status[h] == VALIDCELL)
  77.         return Pix(&tab[h]);
  78.       else
  79.         return 0;
  80.     }
  81.     else if (cmp < 0)
  82.       return 0;
  83.     else
  84.       h = ((h + inc) & (size - 1));
  85.   }
  86.   return 0;
  87. }
  88.  
  89. // This adds an item if it doesn't already exist.  By performing the initial
  90. // comparison we assure that the table always contains at least 1 empty
  91. // spot.  This speeds up later searching by a constant factor.
  92. // The insertion algorithm uses ordered double hashing.  See Standish's
  93. // 1980 ``Data Structure's Techniques'' book for details.
  94.  
  95. Pix <T>VOHSet::add(<T&> x)
  96. {
  97.   if (size <= cnt+1) 
  98.     resize();
  99.   
  100.   unsigned hashval = <T>HASH(x);
  101.   unsigned h = hashval & (size - 1);
  102.  
  103.   if (status[h] != VALIDCELL)   // save some work if possible
  104.   {
  105.     if (status[h] == EMPTYCELL)
  106.       cnt++;
  107.     count++;
  108.     tab[h] = x;
  109.     status[h] = VALIDCELL; 
  110.     return Pix(&tab[h]);
  111.   }
  112.  
  113.   <T> item = x;
  114.   Pix mypix = 0;
  115.   unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));
  116.  
  117.   for (;;)
  118.   {
  119.     if (status[h] != VALIDCELL)
  120.     {
  121.       if (status[h] == EMPTYCELL)
  122.         cnt++;
  123.       count++;
  124.       tab[h] = item;
  125.       status[h] = VALIDCELL; 
  126.       return (mypix == 0)? Pix(&tab[h]) : mypix;
  127.     }
  128.     int cmp = <T>CMP(item, tab[h]);
  129.     if (cmp == 0)
  130.       return (mypix == 0)? Pix(&tab[h]) : mypix;
  131.     else if (cmp < 0)
  132.     {
  133.       <T> temp = tab[h];
  134.       tab[h] = item;
  135.       item = temp;
  136.       if (mypix == 0) mypix = Pix(&tab[h]);
  137.       hashval = <T>HASH(item);
  138.       h = hashval & (size - 1);
  139.       inc = ((((hashval / size) << 1) + 1) & (size - 1));
  140.     }
  141.     else
  142.       h = ((h + inc) & (size - 1));
  143.   }
  144. }
  145.  
  146.  
  147. void <T>VOHSet::del(<T&> key)
  148. {
  149. // This performs a deletion by marking the item's status field.
  150. // Note that we only decrease the count, *not* the cnt, since this
  151. // would cause trouble for subsequent steps in the algorithm.  See
  152. // Reingold and Hanson's ``Data Structure's'' book for a justification
  153. // of this approach.
  154.  
  155.   unsigned hashval = <T>HASH(key);
  156.   unsigned h   = hashval & (size - 1);
  157.   unsigned inc = ((((hashval / size) << 1) + 1) & (size - 1));
  158.   
  159.   while (status[h] != EMPTYCELL)
  160.   {
  161.     int cmp = <T>CMP(key, tab[h]);
  162.     if (cmp > 0)
  163.       h = ((h + inc) & (size - 1));
  164.     else if (status[h] == VALIDCELL && cmp == 0)
  165.     {
  166.       status[h] = DELETEDCELL;
  167.       count--;
  168.       return;
  169.     }
  170.     else 
  171.       return;
  172.   }
  173. }
  174.  
  175. void <T>VOHSet::clear()
  176. {
  177.   for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  178.   count = cnt = 0;
  179. }
  180.  
  181. void <T>VOHSet::resize(int newsize)
  182. {
  183.   if (newsize <= count)
  184.     newsize = count;
  185.   int s = 1;
  186.   while (s <= newsize) s <<= 1;
  187.   newsize = s;
  188.  
  189.   <T>* oldtab = tab;
  190.   char* oldstatus = status;
  191.   int oldsize = size;
  192.   tab = new <T>[size = newsize];
  193.   status = new char[size];
  194.   for (int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  195.   count = cnt = 0;
  196.   
  197.   for (i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]);
  198.   delete [] oldtab;
  199.   delete oldstatus;
  200. }
  201.  
  202. Pix <T>VOHSet::first()
  203. {
  204.   for (int pos = 0; pos < size; ++pos)
  205.     if (status[pos] == VALIDCELL) return Pix(&tab[pos]);
  206.   return 0;
  207. }
  208.  
  209. void <T>VOHSet::next(Pix& i)
  210. {
  211.   if (i == 0) return;
  212.   int pos = ((unsigned)i - (unsigned)tab) / sizeof(<T>) + 1;
  213.   for (; pos < size; ++pos)
  214.     if (status[pos] == VALIDCELL)
  215.     {
  216.       i = Pix(&tab[pos]);
  217.       return;
  218.     }
  219.   i = 0;
  220. }
  221.  
  222.  
  223. int <T>VOHSet:: operator == (<T>VOHSet& b)
  224. {
  225.   if (count != b.count)
  226.     return 0;
  227.   else
  228.   {
  229.     for (int i = 0; i < size; ++i)
  230.       if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
  231.           return 0;
  232.     for (i = 0; i < b.size; ++i)
  233.       if (b.status[i] == VALIDCELL && seek(b.tab[i]) == 0)
  234.           return 0;
  235.     return 1;
  236.   }
  237. }
  238.  
  239. int <T>VOHSet:: operator != (<T>VOHSet& b)
  240. {
  241.   return !(*this == b);
  242. }
  243.  
  244. int <T>VOHSet::operator <= (<T>VOHSet& b)
  245. {
  246.   if (count > b.count)
  247.     return 0;
  248.   else
  249.   {
  250.     for (int i = 0; i < size; ++i)
  251.       if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
  252.           return 0;
  253.     return 1;
  254.   }
  255. }
  256.  
  257. void <T>VOHSet::operator |= (<T>VOHSet& b)
  258. {
  259.   if (&b == this || b.count == 0)
  260.     return;
  261.   for (int i = 0; i < b.size; ++i)
  262.     if (b.status[i] == VALIDCELL) add(b.tab[i]);
  263. }
  264.  
  265. void <T>VOHSet::operator &= (<T>VOHSet& b)
  266. {
  267.   if (&b == this || count == 0)
  268.     return;
  269.   for (int i = 0; i < size; ++i)
  270.   {
  271.     if (status[i] == VALIDCELL && b.seek(tab[i]) == 0)
  272.     {
  273.       status[i] = DELETEDCELL;
  274.       --count;
  275.     }
  276.   }
  277. }
  278.  
  279. void <T>VOHSet::operator -= (<T>VOHSet& b)
  280. {
  281.   for (int i = 0; i < size; ++i)
  282.   {
  283.     if (status[i] == VALIDCELL && b.seek(tab[i]) != 0)
  284.     {
  285.       status[i] = DELETEDCELL;
  286.       --count;
  287.     }
  288.   }
  289. }
  290.  
  291. int <T>VOHSet::OK()
  292. {
  293.   int v = tab != 0;
  294.   v &= status != 0;
  295.   int n = 0;
  296.   for (int i = 0; i < size; ++i) 
  297.   {
  298.     if (status[i] == VALIDCELL) ++n;
  299.     else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL)
  300.       v = 0;
  301.   }
  302.   v &= n == count;
  303.   if (!v) error("invariant failure");
  304.   return v;
  305. }
  306.