262 lines
5.4 KiB
C++
262 lines
5.4 KiB
C++
/*++
|
|
FHash.h
|
|
|
|
This file contains a template class for a hash table.
|
|
The template has two arguments, the type of the Data Elements and the
|
|
type of the Key.
|
|
|
|
The Data type must support the following :
|
|
|
|
class Data {
|
|
Data* m_pNext ;
|
|
|
|
KEYREF GetKey( ) ;
|
|
|
|
int MatchKey( KEYREF otherkey) ; /* NOTE : MatchKey returns non-zero on equality
|
|
} ;
|
|
|
|
DWORD (* m_pfnHash)( KEYREF k ) ;
|
|
|
|
--*/
|
|
|
|
#ifndef _FHASHEX_H_
|
|
#define _FHASHEX_H_
|
|
|
|
//------------------------------------------------------------
|
|
template< class Data, /* This is the item that resides in the hashtable */
|
|
class Key, /* This is the type of the Key */
|
|
class KEYREF /* This is the type used to point or reference items in the cache*/
|
|
>
|
|
class TFHashEx {
|
|
//
|
|
// This class defines a Hash table which can grow dynamically to
|
|
// accomodate insertions into the table. The table only grows, and
|
|
// does not shrink.
|
|
//
|
|
public :
|
|
//
|
|
// Define the subtypes we need !
|
|
//
|
|
|
|
//
|
|
// This is a member pointer to a pointer to Data -
|
|
// i.e. this is the offset in the class Data where we
|
|
// will hold the next pointers for our hash buckets !
|
|
//
|
|
typedef Data* Data::*NEXTPTR ;
|
|
|
|
//
|
|
// This is a member function pointer to a function which
|
|
// will retrieve the key we are to use !
|
|
//
|
|
typedef KEYREF (Data::*GETKEY)( ) ;
|
|
|
|
//
|
|
// This is a member function pointer of the type that will
|
|
// compare keys for us !
|
|
//
|
|
typedef int (Data::*MATCHKEY)( KEYREF key ) ;
|
|
|
|
|
|
private :
|
|
|
|
|
|
//
|
|
// An array of pointer to buckets.
|
|
//
|
|
Data** m_ppBucket ;
|
|
|
|
//
|
|
// Member Pointer - points to where the pointer is that
|
|
// we should use for chaining buckets together !
|
|
//
|
|
NEXTPTR m_pNext ;
|
|
|
|
//
|
|
// Member Pointer - will get the key out of the object for us !
|
|
//
|
|
GETKEY m_pGetKey ;
|
|
|
|
//
|
|
// Member Pointer - will compare the key in the item for us !
|
|
//
|
|
MATCHKEY m_pMatchKey ;
|
|
|
|
//
|
|
// A counter that we use to determine when to grow the
|
|
// hash table. Each time we grow the table we set this
|
|
// to a large positive value, and decrement as we insert
|
|
// elements. When this hits 0 its time to grow the table !
|
|
//
|
|
long m_cInserts ;
|
|
|
|
//
|
|
// The function we use to compute hash values.
|
|
// (Provided by the Caller of Init())
|
|
//
|
|
DWORD (* m_pfnHash)( KEYREF k ) ;
|
|
|
|
//
|
|
// Number of Buckets used in index computation
|
|
//
|
|
int m_cBuckets ;
|
|
|
|
//
|
|
// Number of Buckets we are actually using
|
|
// Assert( m_cBuckets >= m_cActiveBuckets ) always true.
|
|
//
|
|
int m_cActiveBuckets ;
|
|
|
|
//
|
|
// Number of Buckets we have allocated
|
|
// Assert( m_cNumAlloced >= m_cActiveBuckets ) must
|
|
// always be true.
|
|
//
|
|
int m_cNumAlloced ;
|
|
|
|
//
|
|
// The amount we should grow the hash table when we
|
|
// decide to grow it.
|
|
//
|
|
int m_cIncrement ;
|
|
|
|
//
|
|
// The number of CBuckets we should allow in each
|
|
// collision chain (on average).
|
|
//
|
|
int m_load ;
|
|
|
|
//
|
|
// The function we use to compute the
|
|
// position of an element in the hash table given its
|
|
// Hash Value.
|
|
//
|
|
DWORD
|
|
ComputeIndex( DWORD dw ) ;
|
|
|
|
public :
|
|
TFHashEx( ) ;
|
|
~TFHashEx( ) ;
|
|
|
|
BOOL
|
|
Init( NEXTPTR pNext,
|
|
int cInitial,
|
|
int cIncrement,
|
|
DWORD (* pfnHash)( KEYREF ),
|
|
int,
|
|
GETKEY,
|
|
MATCHKEY
|
|
) ;
|
|
|
|
//
|
|
// Check that the hash table is in a valid state
|
|
// if fCheckHash == TRUE we will walk all the buckets and check that
|
|
// the data hashes to the correct value !
|
|
//
|
|
BOOL
|
|
IsValid( BOOL fCheckHash = FALSE ) ;
|
|
|
|
//
|
|
// Insert a piece of Data into the Hash Table
|
|
//
|
|
Data*
|
|
InsertDataHash( DWORD dw,
|
|
Data& d
|
|
) ;
|
|
|
|
//
|
|
// Insert a piece of Data into the Hash Table
|
|
// We take a pointer to the Data object.
|
|
//
|
|
Data*
|
|
InsertDataHash( DWORD dw,
|
|
Data* pd
|
|
) ;
|
|
|
|
//
|
|
// Insert a piece of Data into the Hash Table
|
|
//
|
|
Data*
|
|
InsertData( Data& d ) ;
|
|
|
|
//
|
|
// Search for a given Key in the Hash Table - return a pointer
|
|
// to the Data within our Bucket object
|
|
//
|
|
Data*
|
|
SearchKeyHash( DWORD dw,
|
|
KEYREF k
|
|
) ;
|
|
|
|
//
|
|
// Search for a given Key in the Hash Table - return a pointer
|
|
// to the Data within our Bucket object
|
|
//
|
|
Data*
|
|
SearchKey( KEYREF k ) ;
|
|
|
|
//
|
|
// Search for a given Key in the Hash Table and remove
|
|
// the item if found. We will return a pointer to the item.
|
|
//
|
|
Data*
|
|
DeleteData( KEYREF k,
|
|
Data* pd = 0
|
|
) ;
|
|
|
|
//
|
|
// Insert the given block of data into the hash table.
|
|
// We will make a copy of the Data Object and store it in one
|
|
// of our bucket objects.
|
|
//
|
|
BOOL
|
|
Insert( Data& d ) ;
|
|
|
|
//
|
|
// Insert the given block of data into the hash table.
|
|
// We take a pointer to the Data Object and store it in one
|
|
// of our bucket objects.
|
|
//
|
|
BOOL
|
|
Insert( Data* pd ) ;
|
|
|
|
//
|
|
// Find the given key in the table and copy the Data object into
|
|
// the out parameter 'd'
|
|
//
|
|
BOOL
|
|
Search( KEYREF k,
|
|
Data &d
|
|
) ;
|
|
|
|
//
|
|
// Delete the key and associated data from the table.
|
|
//
|
|
BOOL
|
|
Delete( KEYREF k ) ;
|
|
|
|
//
|
|
// Discards any memory we have allocated - after this, you must
|
|
// call Init() again!
|
|
//
|
|
void Clear( ) ;
|
|
|
|
//
|
|
// Removes all of the items in the hash table. Does not call "delete"
|
|
// on them.
|
|
//
|
|
void Empty( ) ;
|
|
|
|
//
|
|
// Function to compute hash value of a key for callers
|
|
// who don't keep track of the hash function
|
|
//
|
|
DWORD
|
|
ComputeHash( KEYREF k ) ;
|
|
|
|
} ;
|
|
|
|
#include "fhashex.inl"
|
|
|
|
#endif // _FHASHEX_H_
|