home *** CD-ROM | disk | FTP | other *** search
/ PC World 1998 October / PCWorld_1998-10_cd.bin / software / prehled / komix / DATA.Z / HashTbl.cxx < prev    next >
C/C++ Source or Header  |  1996-05-31  |  6KB  |  254 lines
  1. /*---------------------------------------------------------------------------
  2.  *
  3.  * Copyright (c) 1991 by Westmount Technology B.V., Delft, The Netherlands.
  4.  *
  5.  * This software is furnished under a license and may be used only in
  6.  * accordance with the terms of such license and with the inclusion of
  7.  * the above copyright notice. This software or any other copies thereof
  8.  * may not be provided or otherwise made available to any other person.
  9.  * No title to and ownership of the software is hereby transferred.
  10.  *
  11.  * The information in this software is subject to change without notice
  12.  * and should not be construed as a commitment by Westmount Technology B.V.
  13.  *
  14.  *---------------------------------------------------------------------------
  15.  *
  16.  *    File        : @(#)HashTbl.cxx    1.2    (1.5) (1.2)
  17.  *    Author        : sipi (original by K.E. Gorlen)
  18.  *    Original date    : Wed Apr 15 15:39:04 MET DST 1992
  19.  *    Description    : implementation of hash tables
  20.  *
  21.  *---------------------------------------------------------------------------
  22.  */
  23. static const char SccsId[]="@(#)HashTbl.cxx    1.2    (1.5) (1.2) 11 Nov 1993 Copyright 1991 Westmount Technology";
  24.  
  25. #ifndef HASHTBL_HXX
  26. #include <HashTbl.hxx>
  27. #endif
  28. #include <iostream.h>
  29. Hashable::~Hashable() {}
  30.  
  31. #if ! HAS_TEMPLATES
  32. implement(FlexArray,hashptr);
  33. #endif
  34.  
  35. unsigned HashTbl::DEFAULT_SIZE = 64;
  36. unsigned HashTbl::EXPANSION_FACTOR = 2;
  37.  
  38. HashTbl::HashTbl(unsigned size):
  39.     contents(setCapacity(size))
  40. {
  41.     contents.clear(0);
  42. }
  43.  
  44. HashTbl::HashTbl(const HashTbl& tbl):
  45.     count    (tbl.count),
  46.     nbits    (tbl.nbits),
  47.     mask    (tbl.mask),
  48.     current    (tbl.current),
  49.     contents    (tbl.contents)
  50. { /* empty */ }
  51.  
  52. HashTbl::~HashTbl()
  53. { /* empty */ }
  54.  
  55. HashTbl&
  56. HashTbl::operator=(const HashTbl& tbl)
  57. {
  58.     count = tbl.count;
  59.     nbits = tbl.nbits;
  60.     mask = tbl.mask;
  61.     current = tbl.current;
  62.     contents = tbl.contents;
  63.     return *this;
  64. }
  65.  
  66. Hashable*
  67. HashTbl::add(Hashable& object)
  68. {
  69.     register int i = findIndexOf(object);
  70.     if ( contents.at(i) ) return contents.at(i);
  71.     contents.at(i) = &object;
  72.     if (++count > capacity()) reSize(capacity()*HashTbl::EXPANSION_FACTOR);
  73.     return &object;
  74. }
  75.  
  76. void
  77. HashTbl::addAll(const HashTbl& tbl)
  78. {
  79.     register unsigned n = tbl.contents.capacity();
  80.     for (register int i = 0; i < n; i++)
  81.     if ( tbl.contents.at(i) ) add( *(tbl.contents.at(i)) );
  82. }
  83.  
  84. Hashable*
  85. HashTbl::remove(const Hashable& object)
  86.     /* Algorithm R, Knuth Vol. 3 p. 527 */
  87. {
  88.     register int i = findIndexOf(object);
  89.     Hashable* rob = contents.at(i);
  90.     if (!rob) /* object does not exist */ return 0;
  91.     register int j,r;
  92.     while (1) {
  93.     contents.at(j=i) = 0;
  94.     do {
  95.         i = (i-1)&mask;
  96.         if (contents.at(i)==0) {
  97.         count--;
  98.         return rob;
  99.         }
  100.         r = getIndex(contents.at(i)->hash());
  101.     } while ((i<=r&&r<j) || (r<j&&j<i) || (j<i&&i<=r));
  102.     contents.at(j) = contents.at(i);
  103.     }
  104. }
  105.  
  106. void
  107. HashTbl::removeAll()
  108. {
  109.     contents.clear(0);
  110.     count = 0;
  111. }
  112.  
  113. void
  114. HashTbl::removeAll(const HashTbl& tbl)
  115. {
  116.     register unsigned n = tbl.contents.capacity();
  117.     for (register int i = 0; i < n; i++)
  118.     if ( tbl.contents.at(i) ) remove( *(tbl.contents.at(i)) );
  119. }
  120.  
  121. void
  122. HashTbl::destructAll()
  123. {
  124.     register unsigned n = contents.capacity();
  125.     for (register int i = 0; i < n; i++)
  126.     if (contents.at(i)) {
  127.         hashptr tmp = contents.at(i);
  128.         delete tmp;
  129.     }
  130.     contents.clear(0);
  131.     count = 0;
  132. }
  133.  
  134. int
  135. HashTbl::operator==(const HashTbl& tbl) const
  136. {
  137.     if (count!=tbl.count) return 0;
  138.     register unsigned n = contents.capacity();
  139.     for (register int i=0; i<n; i++) {
  140.     if (contents.at(i) &&
  141.         tbl.contents.at(findIndexOf( *(contents.at(i)) )) == 0 )
  142.         return 0;
  143.     }
  144.     return 1;
  145. }
  146.  
  147. Hashable*
  148. HashTbl::first()
  149. {
  150.     if(count == 0) return 0;
  151.     register unsigned n = contents.capacity();
  152.     for (current=0; current<n; current++)
  153.     if (contents.at(current)) return contents.at(current);
  154.     return 0;
  155. }
  156.  
  157. Hashable*
  158. HashTbl::next()
  159. {
  160.     register unsigned n = contents.capacity();
  161.     for (++current;current<n; current++)
  162.     if (contents.at(current)) return contents.at(current);
  163.     return 0;
  164. }
  165.  
  166. unsigned
  167. HashTbl::setCapacity(unsigned size)
  168. {
  169.     if (size==0) /* error but ignore it */ size++;
  170.     current = 0;
  171.     count = 0;
  172.     nbits = 0;
  173.     for (register unsigned s=size; s!=0; s>>=1) nbits++;
  174.     if ((size&(size-1)) != 0) nbits++;    // round up if not power of 2
  175.     size = 1<<nbits;
  176.     mask = size-1;
  177.     return size;            // return hash table size
  178. }
  179.  
  180. int
  181. HashTbl::getIndex(unsigned long K) const
  182.     /* Knuth Vol. 3, Section 6.4, pp. 508-512 */
  183. {
  184.     const unsigned long Aw = 0x9E3779B9;
  185.     // const unsigned long Aw = 2654435769UL;
  186.     // const unsigned long Aw = 40503;        use for 16 bit machines? 
  187.     return ((Aw*K)>>((8*sizeof(unsigned))-nbits)) & mask;
  188. }
  189.  
  190. int
  191. HashTbl::findIndexOf(const Hashable& object) const
  192.     /* Algorithm L, Knuth Vol. 3, p. 519 */
  193. {
  194.     register int i;
  195.     for (i = getIndex(object.hash()); contents.at(i)!=0; i = (i-1)&mask)
  196.     if ((contents.at(i))->isEqual(object)) return i;
  197.     return i;
  198. }
  199.  
  200. void
  201. HashTbl::reSize(unsigned new_size)
  202. {
  203.     if (new_size <= count) return;
  204.     if (count > 0) {
  205.     hashList tmp = contents;
  206.     contents.reSize(setCapacity(new_size));
  207.     contents.clear(0);
  208.     unsigned n = tmp.capacity();
  209.     for (int i=0; i < n; i++) {
  210.         if (tmp.at(i)) add( *(tmp.at(i)) );
  211.     }
  212.     }
  213.     else contents.reSize(setCapacity(new_size));
  214. }
  215.  
  216. hash_iter::hash_iter(const HashTbl& t) :
  217.     tbl(t),
  218.     curr_idx(-1)
  219. {
  220.     rewind();
  221. }
  222.  
  223. hash_iter::~hash_iter()
  224. {
  225.     /* empty */
  226. }
  227.  
  228. void hash_iter::rewind(void)
  229. {
  230.     if (tbl.size() == 0) {
  231.        curr_idx = -1; 
  232.        return;
  233.     }
  234.     register unsigned n = tbl.contents.capacity();
  235.     for(curr_idx = 0; curr_idx < n; curr_idx++) {
  236.         if (tbl.at(curr_idx))
  237.             return; 
  238.     }
  239.     curr_idx = -1;
  240. }
  241.  
  242. void hash_iter::advance(void)
  243. {
  244.     if ( end_of_iteration() )
  245.         return;
  246.  
  247.     register unsigned n = tbl.contents.capacity();
  248.     for (++curr_idx; curr_idx < n; curr_idx++) {
  249.         if (tbl.at(curr_idx))
  250.             return; 
  251.     }
  252.     curr_idx = -1;
  253. }
  254.