home *** CD-ROM | disk | FTP | other *** search
- /******** Listing 4 **************************** DYNHASH.CPP ******
- * dynhash.cpp Copyright (C) 1990 by Tom Provenzano
- *
- * Implements a dynamic hashing scheme called Linear Hashing
- * described in the article "Dynamic Hash Tables" by Per-Ake Larson,
- * Communications of the ACM, v31 n4, April 1988, pp. 446-457.
- *******************************************************************/
-
- #include <string.h>
- #include <stdlib.h>
- #include "dynarray.hpp"
- #include "dynhash.hpp"
-
- /* hash table constructor */
-
- dynhash::dynhash( int objsize ) : hashtable( 5 )
- {
- N = 5; // number of buckets to start
- splitp = 0; // init dynarray splitting index
- maxp = N; // maxp = N * (2**L)
- CurrentSize = 0; // hash table is empty
- MinLoadFactor = 3; // set minimum loading factor
- MaxLoadFactor = 5; // set maximum loading factor
- Threshold = 0; // turn threshold check OFF
- recsize = objsize; // bytes in hash table object (record)
- err = 0; // clear error flag
- }
- /*------------------------------------------------------------------------*/
- /*
- ** Hash table destructor. Returns all zSLists and table items to heap.
- ** Gets each object on list by calling Zortech Tools zSList class member
- ** function get().
- */
- dynhash::~dynhash()
- {
- void *s;
-
- for ( int i = 0; i < hashtable.size(); i++ )
- if ( hashtable[i] )
- while ( (s=hashtable[i]->get()) != (void *) 0 )
- delete s;
- }
- /*------------------------------------------------------------------------*/
- /*
- ** insert -- insert item in hash table. Check if time for table expansion.
- */
- int dynhash::insert( void *item )
- {
- int index;
- int LoadFactor;
-
- if ( (index = insert_rec( item )) < 0 ) // insert it
- err = index; // set error flag
- else
- {
- // check if time to expand hash table
- if ( index >= 0 )
- {
- CurrentSize++; // increase # recs in hashtable
- LoadFactor = CurrentSize / hashtable.size();
- if ( LoadFactor >= MinLoadFactor )
- Threshold = 1; // load factor threshold reached
- if ( LoadFactor > MaxLoadFactor )
- if ( ExpandTable() != OK )
- index = err = EXPAND_ERROR; // couldn't expand hash table!
- }
- }
- return index;
- }
- /* -----------------------------------------------------------------------
- ** insert_rec - insert record in hashtable
- */
- int dynhash::insert_rec( void *item )
- {
- int index;
- char *p = (char *)item, *new_item, *q;
-
- // look up item in hashtable, if already there don't put it in again
- if ( lookup( item ) )
- return NOT_INSERTED;
-
- // build copy of item
- new_item = q = new char[ recsize ]; // get mem space for new item
- if ( !new_item )
- index = NO_MEMORY; // memory allocation failure!
- else
- {
- memcpy( new_item, p, recsize ); // copy entire record
-
- // hash record to table
- index = hash( q );
- if ( hashtable[index] == (pzSList) 0 ) // any items in bucket?
- hashtable[index] = new zSList; // store new zSList addr in hashtable
-
- hashtable[index]->insert( q ); // insert item in hash table
- }
- return index;
- }
- /*------------------------------------------------------------------------*/
- /* remove -- remove item from hash table.
- * Check if time for table contraction.
- */
- int dynhash::remove( void *item )
- {
- int LoadFactor;
- int index;
-
- if ( (index = remove_rec( item )) == NOT_FOUND ) // remove it
- err = index; // set our error flag
- else
- {
- if ( index >= 0 )
- {
- CurrentSize--; // item removed from hashtable
-
- // check if time to contract hash table
- // (don't contract table if it's only the original size!)
-
- if ( maxp > N )
- {
- LoadFactor = CurrentSize / hashtable.size();
- if ( LoadFactor < MinLoadFactor && Threshold )
- if ( ContractTable() != OK )
- err = index = NOT_REMOVED;
- }
- }
- }
- return index;
- }
- /* ----------------------------------------------------------------------- */
- /* remove_rec - remove record from hashtable
- */
- int dynhash::remove_rec( void *item )
- {
- int index, Found=0, num_items=0;
- zSList* sl;
- char* p;
-
- index = hash( (char *) item ); // get hash table array index
- sl = hashtable[index]; // get appropriate zSList
- zSListIterator& sli = *sl; // make an zSList iterator
-
- // First, count the number of items on the list.
- // NOTE: sli() overloads the "()" operator to return a pointer to the
- // current item on the associated list followed by moving the pointer
- // to the next item on the list.
- while ( (p=(char *) sli()) != NULL )
- num_items++;
- for ( ; num_items > 0; num_items-- )
- {
- p = (char *) sl->get(); // check next item on list
-
- if ( !strcmp( p, (char *) item ) )
- { // item found
- Found = 1; // item found & deleted
- break;
- }
- else
- sl->append( p ); // put it back at end of list!
- } // search entire list
- return (Found) ? index : NOT_FOUND;
- }
- /*------------------------------------------------------------------------*/
-
- /* lookup -- lookup item in hashtable
- */
- void *dynhash::lookup( void *item )
- {
- int index = -1, Found = 0;
- char* p;
- zSList* sl;
-
- index = hash( (char *) item ); // hash key to table
- sl = hashtable[index]; // get zSList address
- zSListIterator& sli = *sl; // make a zSList iterator
-
- if ( sl ) // if zSList exists
- do // see if item on list ...
- // iterator overloads "()" - see comments in remove_rec()
- if ( ( p = (char *) sli() ) != NULL )
- if ( !strcmp( p, (char *) item ) )
- {
- Found = 1; // found item!
- break;
- }
- while ( p );
- return ( Found ) ? (void *) p : (void *) NULL;
- }
- /*------------------------------------------------------------------------*/
- /*
- ** get_next -- get the next entry from the hashtable. An internal
- ** record is kept of a particular hash table's the next
- ** entry to get via statuc var i. Also zSListIterator sli
- ** is declared static in order to preserve its value for
- ** all calls necessary to get succeeding items from its list.
- **
- */
- void *dynhash::get_next( void )
- {
- static zSList *sl = (zSList *) 0;
- static zSListIterator& sli;
- static char *p;
- static int i=0;
-
- if ( i < hashtable.size() )
- {
- if ( sl == (zSList *) 0 ) // if don't have zSList
- {
- sl = hashtable[i];
- sli = *sl; // initialize iterator
- }
-
- // NOTE: Zortech Tools iterator class overloads the "()" operator,
- // returning a pointer to the next item on list and adjusting the
- // pointer to the following item on the list.
- if ( (p=(char *) sli()) == NULL ) // hit end of zSList
- {
- i++; // next hash table entry
- sl = (zSList *) 0;
- }
- }
- else
- {
- i = 0; // reset
- p = (void *) NULL; // denotes no more to GET
- sl = (zSList *) 0;
- }
- return (void *) p; // return record pointer
- }
- /*------------------------------------------------------------------------*/
- /*
- ** hash -- compute hash function. The prime number, 1048583, comes from
- ** "Dynamic Hash Tables", by Per-Ake Larson, Communications of the ACM,
- ** April, 1988, v31 n4, pg. 449.
- */
- int dynhash::hash( char *key )
- {
- const long prime = 1048583;
- int address, h;
-
- h = (int) ( (long) ConvertKey( key ) % prime );
- address = h % maxp;
- return ( address < splitp ) ? h % (2*maxp) : address;
- }
- /*------------------------------------------------------------------------*/
- /*
- ** ConvertKey -- convert a non-integer key to an integer value. This
- ** algorithm taken from "Dynamic Hash Tables", by Per-Ake Larson,
- ** Communications of the ACM, April, 1988, v31 n4, pg. 454.
- */
- int dynhash::ConvertKey( char *key )
- {
- int convkey = 0;
-
- while ( *key )
- convkey = 37 * convkey + *key++;
- return ( abs( convkey ) );
- }
- /*------------------------------------------------------------------------*/
- /*
- ** ExpandTable -- expand hash table size. Relocates records if necessary.
- */
- int dynhash::ExpandTable()
- {
- char *p;
- zSList* sl;
- int new_addr, q = splitp, num_items=0, err_stat;
-
- new_addr = maxp + splitp;
-
- // update dynamic hashtable variables
- if ( ++splitp == maxp )
- {
- maxp *= 2;
- splitp = 0; // reset hashtable array pointer
- }
-
- // expand hashtable size by 1 bucket
- int i = hashtable.size();
- hashtable[i] = new zSList; // store new zSList addr in hashtable
- if ( (err_stat = hashtable.error()) != 0 )
- return err_stat;
-
- zSListIterator& sli = *hashtable[q]; // make an iterator
-
- // First, count the number of objects on the list
- while ( (p=(char *) sli()) != NULL )
- num_items++;
- for ( ; num_items > 0; num_items-- )
- {
- p = (char *) hashtable[q]->get();
- if ( hash( p ) == new_addr )
- hashtable[new_addr]->append( p ); // append to new bucket
- else
- hashtable[q]->append( p ); // re-install object at end of list
- }
- return OK; // expanded table
- }
- /*------------------------------------------------------------------------*/
- /*
- ** ContractTable -- contract hash table size. Relocates records if necessary.
- */
- int dynhash::ContractTable()
- {
- char *p;
-
- zSList* sl;
- int i, num_items=0;
-
- if ( --splitp < 0 )
- {
- splitp = maxp /= 2;
- splitp--;
- }
-
- i = hashtable.size(); // get hash table size
- --i; // make into zero-based index
- sl = hashtable[i]; // move FROM
-
- if ( sl ) // don't bother if nothing to move!
- {
- zSListIterator& sli = *sl; // make an iterator
- while ( (p=(char *) sli()) != NULL ) // first, count # items on list
- num_items++;
-
- // move each item from last hash table entry to different bucket
- for ( ; num_items > 0; num_items-- )
- {
- p = (char *) hashtable[i]->get();
- hashtable[splitp]->append( p ); // move to another bucket
- }
- }
- // contract hashtable size by 1 bucket (freeing last bucket in dynarray)
- hashtable[-1] = (zSList *) 0;
-
- return OK; // contracted hash table
- }