home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / gen / VHBag.ccP < prev    next >
Encoding:
Text File  |  1995-02-06  |  6.1 KB  |  265 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, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include "<T>.VHBag.h"
  23.  
  24. /* codes for status fields */
  25.  
  26. #define EMPTYCELL   0
  27. #define VALIDCELL   1
  28. #define DELETEDCELL 2
  29.  
  30.  
  31. <T>VHBag::<T>VHBag(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>VHBag::<T>VHBag(<T>VHBag& 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>VHBag::seek(<T&> key, Pix p)
  63. {
  64.   <T>* t = (<T>*) p;
  65.   if (t == 0 || !<T>EQ(*t, key))
  66.   {
  67.     unsigned int hashval = <T>HASH(key);
  68.     unsigned int h = hashval % size;
  69.     for (unsigned int i = 0; i <= size; ++i)
  70.     {
  71.       if (status[h] == EMPTYCELL)
  72.         return 0;
  73.       else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
  74.         return Pix(&tab[h]);
  75.       if (i == 0)
  76.         h = (h + doublehashinc(hashval, size)) % size;
  77.       else if (++h >= size)
  78.         h -= size;
  79.     }
  80.     return 0;
  81.   }
  82.   else
  83.   {
  84.     int seent = 0;
  85.     unsigned int hashval = <T>HASH(key);
  86.     unsigned int h = hashval % size;
  87.     for (unsigned int i = 0; i <= size; ++i)
  88.     {
  89.       if (status[h] == EMPTYCELL)
  90.         return 0;
  91.       else if (&tab[h] == t)
  92.         seent = 1;
  93.       else if (seent && status[h] == VALIDCELL && <T>EQ(key, tab[h]))
  94.         return Pix(&tab[h]);
  95.       if (i == 0)
  96.         h = (h + doublehashinc(hashval, size)) % size;
  97.       else if (++h >= size)
  98.         h -= size;
  99.     }
  100.     return 0;
  101.   }
  102. }
  103.  
  104. int <T>VHBag::nof(<T&> item)
  105. {
  106.   int n = 0;
  107.   unsigned int hashval = <T>HASH(item);
  108.   unsigned int h = hashval % size;
  109.   unsigned int firsth = size;
  110.   for (unsigned int i = 0; i <= size; ++i)
  111.   {
  112.     if (status[h] == EMPTYCELL)
  113.       return n;
  114.     else if (h != firsth && status[h] == VALIDCELL && <T>EQ(item, tab[h]))
  115.     {
  116.       ++n;
  117.       if (firsth >= size)
  118.         firsth = h;
  119.     }
  120.     if (i == 0)
  121.       h = (h + doublehashinc(hashval, size)) % size;
  122.     else if (++h >= size)
  123.       h -= size;
  124.   }
  125.   return n;
  126. }
  127.  
  128.  
  129. Pix <T>VHBag::add(<T&> item)
  130. {
  131.   if (HASHTABLE_TOO_CROWDED(count, size))
  132.     resize();
  133.   unsigned int bestspot = size;
  134.   unsigned int hashval = <T>HASH(item);
  135.   unsigned int h = hashval % size;
  136.   for (unsigned int i = 0; i <= size; ++i)
  137.   {
  138.     if (status[h] == EMPTYCELL)
  139.     {
  140.       if (bestspot >= size) bestspot = h;
  141.       tab[bestspot] = item;
  142.       status[bestspot] = VALIDCELL;
  143.       ++count;
  144.       return Pix(&tab[bestspot]);
  145.     }
  146.     else if (status[h] == DELETEDCELL)
  147.     {
  148.       if (bestspot >= size) bestspot = h;
  149.     }
  150.  
  151.     if (i == 0)
  152.       h = (h + doublehashinc(hashval, size)) % size;
  153.     else if (++h >= size)
  154.       h -= size;
  155.   }
  156.   tab[bestspot] = item;
  157.   status[bestspot] = VALIDCELL;
  158.   ++count;
  159.   return Pix(&tab[bestspot]);
  160. }
  161.  
  162.  
  163. void <T>VHBag::del(<T&> key)
  164. {
  165.   unsigned int hashval = <T>HASH(key);
  166.   unsigned int h = hashval % size;
  167.   for (unsigned int i = 0; i <= size; ++i)
  168.   {
  169.     if (status[h] == EMPTYCELL)
  170.       return;
  171.     else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
  172.     {
  173.       status[h] = DELETEDCELL;
  174.       --count;
  175.       return;
  176.     }
  177.     if (i == 0)
  178.       h = (h + doublehashinc(hashval, size)) % size;
  179.     else if (++h >= size)
  180.       h -= size;
  181.   }
  182. }
  183.  
  184. void <T>VHBag::remove(<T&> key)
  185. {
  186.   unsigned int hashval = <T>HASH(key);
  187.   unsigned int h = hashval % size;
  188.   for (unsigned int i = 0; i <= size; ++i)
  189.   {
  190.     if (status[h] == EMPTYCELL)
  191.       return;
  192.     else if (status[h] == VALIDCELL && <T>EQ(key, tab[h]))
  193.     {
  194.       status[h] = DELETEDCELL;
  195.       --count;
  196.     }
  197.     if (i == 0)
  198.       h = (h + doublehashinc(hashval, size)) % size;
  199.     else if (++h >= size)
  200.       h -= size;
  201.   }
  202. }
  203.  
  204. void <T>VHBag::clear()
  205. {
  206.   for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  207.   count = 0;
  208. }
  209.  
  210. void <T>VHBag::resize(unsigned int newsize)
  211. {
  212.   if (newsize <= count)
  213.   {
  214.     newsize = DEFAULT_INITIAL_CAPACITY;
  215.     while (HASHTABLE_TOO_CROWDED(count, newsize)) newsize <<= 1;
  216.   }
  217.   <T>* oldtab = tab;
  218.   char* oldstatus = status;
  219.   unsigned int oldsize = size;
  220.   tab = new <T>[size = newsize];
  221.   status = new char[size];
  222.   for (unsigned int i = 0; i < size; ++i) status[i] = EMPTYCELL;
  223.   count = 0;
  224.   for (i = 0; i < oldsize; ++i) if (oldstatus[i] == VALIDCELL) add(oldtab[i]);
  225.   delete [] oldtab;
  226.   delete oldstatus;
  227. }
  228.  
  229. Pix <T>VHBag::first()
  230. {
  231.   for (unsigned int pos = 0; pos < size; ++pos)
  232.     if (status[pos] == VALIDCELL) return Pix(&tab[pos]);
  233.   return 0;
  234. }
  235.  
  236. void <T>VHBag::next(Pix& i)
  237. {
  238.   if (i == 0) return;
  239.   unsigned int pos = ((unsigned)i - (unsigned)tab) / sizeof(<T>) + 1;
  240.   for (; pos < size; ++pos)
  241.     if (status[pos] == VALIDCELL)
  242.     {
  243.       i = Pix(&tab[pos]);
  244.       return;
  245.     }
  246.   i = 0;
  247. }
  248.  
  249.   
  250. int <T>VHBag::OK()
  251. {
  252.   int v = tab != 0;
  253.   v &= status != 0;
  254.   int n = 0;
  255.   for (unsigned int i = 0; i < size; ++i) 
  256.   {
  257.     if (status[i] == VALIDCELL) ++n;
  258.     else if (status[i] != DELETEDCELL && status[i] != EMPTYCELL)
  259.       v = 0;
  260.   }
  261.   v &= n == count;
  262.   if (!v) error("invariant failure");
  263.   return v;
  264. }
  265.