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 >
Wrap
Text File
|
1991-03-06
|
11KB
|
337 lines
/******** 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
}