You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
440 lines
9.4 KiB
440 lines
9.4 KiB
/*++=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
|
|
|
|
Copyright (c) 2000 Microsoft Corporation
|
|
|
|
Module Name:
|
|
|
|
hashtable.cxx
|
|
|
|
Abstract:
|
|
|
|
Simple hash table implementation.
|
|
|
|
|
|
Author:
|
|
|
|
Paul M Midgen (pmidge) 14-August-2000
|
|
|
|
|
|
Revision History:
|
|
|
|
14-August-2000 pmidge
|
|
Created
|
|
|
|
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--*/
|
|
|
|
#include <common.h>
|
|
|
|
/*++===========================================================================
|
|
|
|
An array is separated into N buckets that +---+
|
|
each contain a pointer to a binary search | 0 |------> O
|
|
tree. The tree's nodes are indexed by a +---+ / \
|
|
DWORD identifier to enable speedy traversals. | 1 | O O
|
|
The array buckets are indexed by the values +---+ / \ \
|
|
generated by the hashing function supplied | 2 | O O O
|
|
by a derived class. +---+
|
|
| N |
|
|
|
|
Clients derive a class from the hashtable ADT and specialize it for a
|
|
given data type. Any data type can be used. The only function the client
|
|
must implement is the GetHashAndBucket function, and their class must
|
|
provide the number of buckets the ADT needs to support. This is usually
|
|
some number that is modulo'd against the generated hashes to yield the
|
|
bucket number.
|
|
|
|
===========================================================================--*/
|
|
|
|
#define HT_COMPARE_LARGER 0x00000001
|
|
#define HT_COMPARE_SMALLER 0x00000002
|
|
#define HT_COMPARE_EQUAL 0x00000003
|
|
|
|
#define HT_TREE_ROOT 0x00000004
|
|
#define HT_TREE_RHSUBTREE 0x00000005
|
|
#define HT_TREE_LHSUBTREE 0x00000006
|
|
|
|
typedef struct _NODE
|
|
{
|
|
DWORD hash;
|
|
DWORD bucket;
|
|
LPVOID data;
|
|
_NODE* parent;
|
|
_NODE* rh_child;
|
|
_NODE* lh_child;
|
|
BOOL isLeft;
|
|
}
|
|
NODE, *PNODE;
|
|
|
|
typedef VOID (*PFNCLEARFUNC)(LPVOID* ppv);
|
|
|
|
template <class T> class CHashTable
|
|
{
|
|
public:
|
|
CHashTable(DWORD buckets)
|
|
{
|
|
pfnClear = NULL;
|
|
cBuckets = buckets;
|
|
arBuckets = new PNODE[buckets];
|
|
InitializeCriticalSection(&csTable);
|
|
}
|
|
|
|
~CHashTable()
|
|
{
|
|
SAFEDELETEBUF(arBuckets);
|
|
DeleteCriticalSection(&csTable);
|
|
}
|
|
|
|
virtual void GetHashAndBucket(T id, LPDWORD lpHash, LPDWORD lpBucket) =0;
|
|
|
|
DWORD Insert(T id, LPVOID pv);
|
|
DWORD Get(T id, LPVOID* ppv);
|
|
DWORD Delete(T id, LPVOID* ppv);
|
|
|
|
void Clear(void);
|
|
void SetClearFunction(PFNCLEARFUNC pfn) { pfnClear = pfn; }
|
|
|
|
private:
|
|
void _Get(DWORD hash, PNODE& proot, PNODE& pnode);
|
|
DWORD _Insert(PNODE& proot, PNODE pnew);
|
|
void _Remove(DWORD hash, PNODE& proot, PNODE& pnode);
|
|
|
|
PNODE _NewNode(T id, LPVOID pv);
|
|
DWORD _CompareNodes(DWORD hash_target, DWORD hash_tree);
|
|
|
|
BOOL _HasChildren(PNODE pnode);
|
|
void _PostTraverseAndDelete(PNODE proot);
|
|
void _Lock(void) { EnterCriticalSection(&csTable); }
|
|
void _Unlock(void) { LeaveCriticalSection(&csTable); }
|
|
|
|
PNODE* arBuckets;
|
|
DWORD cBuckets;
|
|
CRITSEC csTable;
|
|
PFNCLEARFUNC pfnClear;
|
|
};
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
|
|
template <class T> DWORD CHashTable<T>::Insert(T id, LPVOID pv)
|
|
{
|
|
DWORD ret = ERROR_SUCCESS;
|
|
PNODE pn = _NewNode(id, pv);
|
|
|
|
_Lock();
|
|
|
|
if( pn )
|
|
{
|
|
ret = _Insert(arBuckets[pn->bucket], pn);
|
|
}
|
|
else
|
|
{
|
|
ret = ERROR_OUTOFMEMORY;
|
|
}
|
|
|
|
_Unlock();
|
|
|
|
return ret;
|
|
}
|
|
|
|
template <class T> DWORD CHashTable<T>::Get(T id, LPVOID* ppv)
|
|
{
|
|
DWORD ret = ERROR_SUCCESS;
|
|
DWORD hash = 0L;
|
|
DWORD bucket = 0L;
|
|
PNODE pnode = NULL;
|
|
|
|
GetHashAndBucket(id, &hash, &bucket);
|
|
|
|
_Lock();
|
|
|
|
_Get(hash, arBuckets[bucket], pnode);
|
|
|
|
if( pnode )
|
|
{
|
|
*ppv = (void*) pnode->data;
|
|
}
|
|
else
|
|
{
|
|
*ppv = NULL;
|
|
ret = ERROR_NOT_FOUND;
|
|
}
|
|
|
|
_Unlock();
|
|
|
|
return ret;
|
|
}
|
|
|
|
template <class T> DWORD CHashTable<T>::Delete(T id, LPVOID* ppv)
|
|
{
|
|
DWORD ret = ERROR_SUCCESS;
|
|
DWORD hash = 0L;
|
|
DWORD bucket = 0L;
|
|
PNODE pnode = NULL;
|
|
|
|
GetHashAndBucket(id, &hash, &bucket);
|
|
|
|
_Lock();
|
|
|
|
_Remove(hash, arBuckets[bucket], pnode);
|
|
|
|
if( pnode )
|
|
{
|
|
if( ppv )
|
|
{
|
|
*ppv = pnode->data;
|
|
}
|
|
else
|
|
{
|
|
if( pfnClear )
|
|
{
|
|
pfnClear(&pnode->data);
|
|
}
|
|
}
|
|
|
|
delete pnode;
|
|
}
|
|
else
|
|
{
|
|
ret = ERROR_NOT_FOUND;
|
|
|
|
if( ppv )
|
|
{
|
|
*ppv = NULL;
|
|
}
|
|
}
|
|
|
|
_Unlock();
|
|
|
|
return ret;
|
|
}
|
|
|
|
template <class T> void CHashTable<T>::Clear(void)
|
|
{
|
|
_Lock();
|
|
|
|
for(DWORD n=0; n < cBuckets; n++)
|
|
{
|
|
if( arBuckets[n] )
|
|
{
|
|
_PostTraverseAndDelete(arBuckets[n]);
|
|
arBuckets[n] = NULL;
|
|
}
|
|
}
|
|
|
|
_Unlock();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
|
|
template <class T> DWORD CHashTable<T>::_Insert(PNODE& proot, PNODE pnew)
|
|
{
|
|
DWORD ret = ERROR_SUCCESS;
|
|
|
|
if( pnew )
|
|
{
|
|
if( !proot )
|
|
{
|
|
proot = pnew;
|
|
}
|
|
else
|
|
{
|
|
switch( _CompareNodes(pnew->hash, proot->hash) )
|
|
{
|
|
case HT_COMPARE_SMALLER :
|
|
{
|
|
pnew->isLeft = TRUE;
|
|
pnew->parent = proot;
|
|
ret = _Insert(proot->lh_child, pnew);
|
|
}
|
|
break;
|
|
|
|
case HT_COMPARE_LARGER :
|
|
{
|
|
pnew->isLeft = FALSE;
|
|
pnew->parent = proot;
|
|
ret = _Insert(proot->rh_child, pnew);
|
|
}
|
|
break;
|
|
|
|
case HT_COMPARE_EQUAL :
|
|
{
|
|
if( pfnClear )
|
|
{
|
|
pfnClear(&proot->data);
|
|
}
|
|
|
|
ret = ERROR_DUP_NAME;
|
|
proot->data = pnew->data;
|
|
delete pnew;
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
template <class T> void CHashTable<T>::_Get(DWORD hash, PNODE& proot, PNODE& pnode)
|
|
{
|
|
if( proot )
|
|
{
|
|
switch( _CompareNodes(hash, proot->hash) )
|
|
{
|
|
case HT_COMPARE_SMALLER :
|
|
{
|
|
_Get(hash, proot->lh_child, pnode);
|
|
}
|
|
break;
|
|
|
|
case HT_COMPARE_LARGER :
|
|
{
|
|
_Get(hash, proot->rh_child, pnode);
|
|
}
|
|
break;
|
|
|
|
case HT_COMPARE_EQUAL :
|
|
{
|
|
pnode = proot;
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
pnode = NULL;
|
|
}
|
|
}
|
|
|
|
template <class T> void CHashTable<T>::_Remove(DWORD hash, PNODE& proot, PNODE& pnode)
|
|
{
|
|
if( proot )
|
|
{
|
|
switch( _CompareNodes(hash, proot->hash) )
|
|
{
|
|
case HT_COMPARE_SMALLER :
|
|
{
|
|
_Remove(hash, proot->lh_child, pnode);
|
|
}
|
|
break;
|
|
|
|
case HT_COMPARE_LARGER :
|
|
{
|
|
_Remove(hash, proot->rh_child, pnode);
|
|
}
|
|
break;
|
|
|
|
case HT_COMPARE_EQUAL :
|
|
{
|
|
pnode = proot;
|
|
|
|
//
|
|
// if proot has no parent it is the tree's root node
|
|
//
|
|
// - if it has children, promote the left child to root
|
|
// and insert the right child in the new tree. after
|
|
// inserting, make sure the new root has no parent.
|
|
//
|
|
// - if it has no children the tree is empty, set the root
|
|
// to null
|
|
//
|
|
|
|
if( !proot->parent )
|
|
{
|
|
if( _HasChildren(proot) )
|
|
{
|
|
proot = proot->lh_child;
|
|
_Insert(proot, pnode->rh_child);
|
|
proot->parent = NULL;
|
|
}
|
|
else
|
|
{
|
|
proot = NULL;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if( proot->isLeft )
|
|
{
|
|
proot->parent->lh_child = NULL;
|
|
}
|
|
else
|
|
{
|
|
proot->parent->rh_child = NULL;
|
|
}
|
|
|
|
_Insert(pnode->parent, pnode->lh_child);
|
|
_Insert(pnode->parent, pnode->rh_child);
|
|
}
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
pnode = NULL;
|
|
}
|
|
}
|
|
|
|
template <class T> void CHashTable<T>::_PostTraverseAndDelete(PNODE proot)
|
|
{
|
|
if( proot )
|
|
{
|
|
_PostTraverseAndDelete(proot->lh_child);
|
|
_PostTraverseAndDelete(proot->rh_child);
|
|
|
|
if( pfnClear )
|
|
{
|
|
pfnClear(&proot->data);
|
|
}
|
|
|
|
delete proot;
|
|
proot = NULL;
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
|
|
template <class T> DWORD CHashTable<T>::_CompareNodes(DWORD hash_target, DWORD hash_tree)
|
|
{
|
|
if( hash_target == hash_tree )
|
|
{
|
|
return HT_COMPARE_EQUAL;
|
|
}
|
|
else if( hash_target < hash_tree )
|
|
{
|
|
return HT_COMPARE_SMALLER;
|
|
}
|
|
else
|
|
{
|
|
return HT_COMPARE_LARGER;
|
|
}
|
|
}
|
|
|
|
template <class T> PNODE CHashTable<T>::_NewNode(T id, LPVOID pv)
|
|
{
|
|
PNODE pn = new NODE;
|
|
|
|
if( pn )
|
|
{
|
|
GetHashAndBucket(id, &pn->hash, &pn->bucket);
|
|
pn->data = pv;
|
|
}
|
|
|
|
return pn;
|
|
}
|
|
|
|
template <class T> BOOL CHashTable<T>::_HasChildren(PNODE pnode)
|
|
{
|
|
if( pnode )
|
|
{
|
|
return (pnode->lh_child || pnode->rh_child);
|
|
}
|
|
else
|
|
{
|
|
return FALSE;
|
|
}
|
|
}
|
|
|