home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / CPROG / CGAZV5N3.ZIP / DYNHASH.CPP < prev    next >
Text File  |  1991-03-06  |  11KB  |  337 lines
  1. /******** Listing 4 **************************** DYNHASH.CPP ******
  2. *  dynhash.cpp  Copyright (C) 1990 by Tom Provenzano
  3. *  
  4. *  Implements a dynamic hashing scheme called Linear Hashing
  5. *  described in the article "Dynamic Hash Tables" by Per-Ake Larson,
  6. *  Communications of the ACM, v31 n4, April 1988, pp. 446-457.
  7. *******************************************************************/
  8.  
  9. #include <string.h>
  10. #include <stdlib.h>
  11. #include "dynarray.hpp"
  12. #include "dynhash.hpp"
  13.  
  14. /* hash table constructor */
  15.  
  16. dynhash::dynhash( int objsize ) : hashtable( 5 )
  17. {
  18.   N             = 5;            // number of buckets to start
  19.   splitp        = 0;            // init dynarray splitting index
  20.   maxp          = N;            // maxp = N * (2**L)
  21.   CurrentSize   = 0;            // hash table is empty
  22.   MinLoadFactor = 3;            // set minimum loading factor
  23.   MaxLoadFactor = 5;            // set maximum loading factor
  24.   Threshold     = 0;            // turn threshold check OFF
  25.   recsize       = objsize;      // bytes in hash table object (record)
  26.   err           = 0;        // clear error flag
  27. }
  28. /*------------------------------------------------------------------------*/
  29. /*
  30. ** Hash table destructor.  Returns all zSLists and table items to heap.
  31. ** Gets each object on list by calling Zortech Tools zSList class member
  32. ** function get().
  33. */
  34. dynhash::~dynhash()
  35. {
  36.   void *s;
  37.  
  38.   for ( int i = 0; i < hashtable.size(); i++ )
  39.     if ( hashtable[i] )
  40.       while ( (s=hashtable[i]->get()) != (void *) 0 )
  41.         delete s;
  42. }
  43. /*------------------------------------------------------------------------*/
  44. /*
  45. ** insert -- insert item in hash table.  Check if time for table expansion.
  46. */
  47. int dynhash::insert( void *item )
  48. {
  49.   int index;
  50.   int LoadFactor;
  51.  
  52.   if ( (index = insert_rec( item )) < 0 )       // insert it
  53.     err = index;                // set error flag
  54.   else
  55.   {
  56.     // check if time to expand hash table
  57.     if ( index >= 0 )
  58.     {
  59.       CurrentSize++;                       // increase # recs in hashtable
  60.       LoadFactor = CurrentSize / hashtable.size();
  61.       if ( LoadFactor >= MinLoadFactor )
  62.            Threshold = 1;                  // load factor threshold reached
  63.       if ( LoadFactor > MaxLoadFactor )
  64.            if ( ExpandTable() != OK )
  65.                 index = err = EXPAND_ERROR;  // couldn't expand hash table!
  66.     }
  67.   }
  68.   return index;
  69. }
  70. /* -----------------------------------------------------------------------
  71. ** insert_rec - insert record in hashtable
  72. */
  73. int dynhash::insert_rec( void *item )
  74. {
  75.   int index;
  76.   char *p = (char *)item, *new_item, *q;
  77.  
  78.   // look up item in hashtable, if already there don't put it in again
  79.   if ( lookup( item ) )
  80.     return NOT_INSERTED;
  81.  
  82.   // build copy of item
  83.   new_item = q = new char[ recsize ];   // get mem space for new item
  84.   if ( !new_item )
  85.     index = NO_MEMORY;          // memory allocation failure!
  86.   else
  87.   {
  88.     memcpy( new_item, p, recsize );     // copy entire record
  89.  
  90.     // hash record to table
  91.     index = hash( q );
  92.     if ( hashtable[index] == (pzSList) 0 ) // any items in bucket?
  93.       hashtable[index] = new zSList;   // store new zSList addr in hashtable
  94.  
  95.     hashtable[index]->insert( q );     // insert item in hash table
  96.   }
  97.   return index;
  98. }
  99. /*------------------------------------------------------------------------*/
  100. /* remove -- remove item from hash table. 
  101.  * Check if time for table contraction.
  102. */
  103. int dynhash::remove( void *item )
  104. {
  105.   int LoadFactor;
  106.   int index;
  107.  
  108.   if ( (index = remove_rec( item )) == NOT_FOUND )  // remove it
  109.     err = index;            // set our error flag
  110.   else
  111.   {
  112.     if ( index >= 0 )
  113.     {
  114.       CurrentSize--;                      // item removed from hashtable
  115.  
  116.       // check if time to contract hash table
  117.       // (don't contract table if it's only the original size!)
  118.  
  119.       if ( maxp > N )
  120.       {
  121.          LoadFactor = CurrentSize / hashtable.size();
  122.          if ( LoadFactor < MinLoadFactor && Threshold )
  123.               if ( ContractTable() != OK )
  124.                  err = index = NOT_REMOVED;
  125.       }
  126.     }
  127.   }
  128.   return index;
  129. }
  130. /* ----------------------------------------------------------------------- */
  131. /* remove_rec - remove record from hashtable
  132. */
  133. int dynhash::remove_rec( void *item )
  134. {
  135.   int index, Found=0, num_items=0;
  136.   zSList* sl;
  137.   char*  p;
  138.  
  139.   index = hash( (char *) item );    // get hash table array index
  140.   sl    = hashtable[index];     // get appropriate zSList
  141.   zSListIterator& sli   = *sl;      // make an zSList iterator
  142.  
  143.   // First, count the number of items on the list.
  144.   // NOTE: sli() overloads the "()" operator to return a pointer to the
  145.   // current item on the associated list followed by moving the pointer
  146.   // to the next item on the list.
  147.   while ( (p=(char *) sli()) != NULL )
  148.     num_items++;
  149.   for ( ; num_items > 0; num_items-- )
  150.   {
  151.     p = (char *) sl->get();     // check next item on list
  152.  
  153.     if ( !strcmp( p, (char *) item  ) )
  154.     {                                   // item found
  155.       Found = 1;            // item found & deleted
  156.       break;
  157.     }
  158.     else
  159.       sl->append( p );          // put it back at end of list!
  160.   }                     // search entire list
  161.   return (Found) ? index : NOT_FOUND;
  162. }
  163. /*------------------------------------------------------------------------*/
  164.  
  165. /* lookup -- lookup item in hashtable
  166. */
  167. void *dynhash::lookup( void *item )
  168. {
  169.   int index = -1, Found = 0;
  170.   char*  p;
  171.   zSList* sl;
  172.  
  173.   index = hash( (char *) item );    // hash key to table
  174.   sl    = hashtable[index];     // get zSList address
  175.   zSListIterator& sli = *sl;            // make a zSList iterator
  176.  
  177.   if ( sl )             // if zSList exists
  178.     do                  // see if item on list ...
  179.       // iterator overloads "()" - see comments in remove_rec()
  180.       if ( ( p = (char *) sli() ) != NULL )
  181.         if ( !strcmp( p, (char *) item ) )
  182.         {
  183.           Found = 1;            // found item!
  184.           break;
  185.         }
  186.     while ( p );
  187.   return ( Found ) ? (void *) p : (void *) NULL;
  188. }
  189. /*------------------------------------------------------------------------*/
  190. /*
  191. ** get_next -- get the next entry from the hashtable.  An internal
  192. **      record is kept of a particular hash table's the next
  193. **      entry to get via statuc var i.  Also zSListIterator sli
  194. **      is declared static in order to preserve its value for
  195. **      all calls necessary to get succeeding items from its list.
  196. **
  197. */
  198. void *dynhash::get_next( void )
  199. {
  200.   static zSList *sl = (zSList *) 0;
  201.   static zSListIterator& sli;
  202.   static char *p;
  203.   static int i=0;
  204.  
  205.   if ( i < hashtable.size() )
  206.   {
  207.     if ( sl == (zSList *) 0 )       // if don't have zSList
  208.     {
  209.       sl  = hashtable[i];
  210.       sli = *sl;            // initialize iterator
  211.     }
  212.  
  213.     // NOTE: Zortech Tools iterator class overloads the "()" operator,
  214.     // returning a pointer to the next item on list and adjusting the
  215.     // pointer to the following item on the list.
  216.     if ( (p=(char *) sli()) == NULL )   // hit end of zSList
  217.     {
  218.       i++;              // next hash table entry
  219.       sl = (zSList *) 0;
  220.     }
  221.   }
  222.   else
  223.   {
  224.     i   = 0;                    // reset
  225.     p   = (void *) NULL;        // denotes no more to GET
  226.     sl  = (zSList *) 0;
  227.   }
  228.   return (void *) p;            // return record pointer
  229. }
  230. /*------------------------------------------------------------------------*/
  231. /*
  232. ** hash -- compute hash function.  The prime number, 1048583, comes from
  233. ** "Dynamic Hash Tables", by Per-Ake Larson, Communications of the ACM,
  234. ** April, 1988, v31 n4, pg. 449.
  235. */
  236. int dynhash::hash( char *key )
  237. {
  238.   const long prime = 1048583;
  239.   int address, h;
  240.  
  241.   h = (int) ( (long) ConvertKey( key ) % prime );
  242.   address = h % maxp;
  243.   return ( address < splitp ) ? h % (2*maxp) : address;
  244. }
  245. /*------------------------------------------------------------------------*/
  246. /*
  247. ** ConvertKey -- convert a non-integer key to an integer value. This
  248. ** algorithm taken from "Dynamic Hash Tables", by Per-Ake Larson,
  249. ** Communications of the ACM, April, 1988, v31 n4, pg. 454.
  250. */
  251. int dynhash::ConvertKey( char *key )
  252. {
  253.   int convkey = 0;
  254.  
  255.   while ( *key )
  256.     convkey = 37 * convkey + *key++;
  257.   return ( abs( convkey ) );
  258. }
  259. /*------------------------------------------------------------------------*/
  260. /*
  261. ** ExpandTable -- expand hash table size. Relocates records if necessary.
  262. */
  263. int dynhash::ExpandTable()
  264. {
  265.   char *p;
  266.   zSList* sl;
  267.   int new_addr, q = splitp, num_items=0, err_stat;
  268.  
  269.   new_addr = maxp + splitp;
  270.  
  271.   // update dynamic hashtable variables
  272.   if ( ++splitp == maxp )
  273.   {
  274.     maxp *= 2;
  275.     splitp = 0;                 // reset hashtable array pointer
  276.   }
  277.  
  278.   // expand hashtable size by 1 bucket
  279.   int i = hashtable.size();
  280.   hashtable[i] = new zSList;     // store new zSList addr in hashtable
  281.   if ( (err_stat = hashtable.error()) != 0 )
  282.     return err_stat;
  283.  
  284.   zSListIterator& sli = *hashtable[q]; // make an iterator
  285.  
  286.   // First, count the number of objects on the list
  287.   while ( (p=(char *) sli()) != NULL )
  288.     num_items++;
  289.   for ( ; num_items > 0; num_items-- )
  290.   {
  291.     p = (char *) hashtable[q]->get();
  292.     if ( hash( p ) == new_addr )
  293.       hashtable[new_addr]->append( p ); // append to new bucket
  294.     else
  295.       hashtable[q]->append( p );    // re-install object at end of list
  296.   }
  297.   return OK;                            // expanded table
  298. }
  299. /*------------------------------------------------------------------------*/
  300. /*
  301. ** ContractTable -- contract hash table size. Relocates records if necessary.
  302. */
  303. int dynhash::ContractTable()
  304. {
  305.   char *p;
  306.  
  307.   zSList* sl;
  308.   int i, num_items=0;
  309.  
  310.   if ( --splitp < 0 )
  311.   {
  312.     splitp = maxp /= 2;
  313.     splitp--;
  314.   }
  315.  
  316.   i = hashtable.size();     // get hash table size
  317.   --i;              // make into zero-based index
  318.   sl = hashtable[i];            // move FROM
  319.  
  320.   if ( sl )                     // don't bother if nothing to move!
  321.   {
  322.     zSListIterator& sli = *sl;  // make an iterator
  323.     while ( (p=(char *) sli()) != NULL )  // first, count # items on list
  324.       num_items++;
  325.  
  326.     // move each item from last hash table entry to different bucket
  327.     for ( ; num_items > 0; num_items-- )
  328.     {
  329.       p = (char *) hashtable[i]->get();
  330.       hashtable[splitp]->append( p );   // move to another bucket
  331.     }
  332.   }
  333.   // contract hashtable size by 1 bucket (freeing last bucket in dynarray)
  334.   hashtable[-1] = (zSList *) 0;
  335.  
  336.   return OK;                            // contracted hash table
  337. }