278 lines
8.8 KiB
C++
278 lines
8.8 KiB
C++
//+--------------------------------------------------------------------------
|
|
//
|
|
// File: hash.hxx
|
|
//
|
|
// Contents: class for maintaining a GUID-based hash table.
|
|
//
|
|
// Classes: CHashTable
|
|
//
|
|
// History: 20-Feb-95 Rickhi Created
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
#ifndef _HASHTBL_HXX_
|
|
#define _HASHTBL_HXX_
|
|
|
|
#include <obase.h>
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Structure: SHashChain
|
|
//
|
|
// Synopsis: An element in the double link list. Used by S*HashNode and
|
|
// C*HashTable.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
typedef struct SHashChain
|
|
{
|
|
struct SHashChain *pNext; // ptr to next node in chain
|
|
struct SHashChain *pPrev; // ptr to prev node in chain
|
|
} SHashChain;
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Structure: SUUIDHashNode
|
|
//
|
|
// Synopsis: This is an element in a bucket in the UUID hash table.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
typedef struct SUUIDHashNode
|
|
{
|
|
SHashChain chain; // double linked list ptrs
|
|
UUID key; // node key (the value that is hashed)
|
|
} SUUIDHashNode;
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Structure: SStringHashNode
|
|
//
|
|
// Synopsis: This is an element in a bucket in the string hash table.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
typedef struct SStringHashNode
|
|
{
|
|
SHashChain chain; // double linked list ptrs
|
|
DWORD dwHash; // hash value of the key
|
|
DUALSTRINGARRAY *psaKey; // node key (the value that is hashed)
|
|
} SStringHashNode;
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Structure: SNameHashNode
|
|
//
|
|
// Synopsis: This is an element in a bucket in the name hash table.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
typedef struct SNameHashNode
|
|
{
|
|
SHashChain chain; // double linked list ptrs
|
|
DWORD dwHash; // hash value of the key
|
|
ULONG cRef; // count of references
|
|
IPID ipid; // ipid holding the reference
|
|
SECURITYBINDING sName; // user name
|
|
} SNameHashNode;
|
|
|
|
|
|
// ptr to cleanup function that gets called by Cleanup
|
|
typedef void (PFNCLEANUP)(SHashChain *pNode);
|
|
|
|
|
|
// number of buckets in the hash table array. It should be a prime
|
|
// number > 20.
|
|
|
|
#define NUM_HASH_BUCKETS 23
|
|
|
|
|
|
//---------------------------------------------------------------------------
|
|
// External definitions.
|
|
|
|
class CNameHashTable;
|
|
extern SHashChain SRFBuckets[23];
|
|
extern CNameHashTable gSRFTbl;
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Class: CHashTable
|
|
//
|
|
// Synopsis: Base hash table. The table uses any key
|
|
// and stores nodes in an array of circular double linked lists.
|
|
// The hash value of the key is the index in the array to the
|
|
// double linked list that the node is chained off.
|
|
//
|
|
// Nodes must be allocated with new. A cleanup function is
|
|
// optionally called for each node when the table is cleaned
|
|
// up.
|
|
//
|
|
// Inheritors of this class must supply the HashNode
|
|
// and Compare functions.
|
|
//
|
|
// Notes: All locking must be done outside the class via LOCK/UNLOCK.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
class CHashTable
|
|
{
|
|
public:
|
|
virtual void Initialize(SHashChain *pChain) { _buckets = pChain; }
|
|
virtual void Cleanup(PFNCLEANUP *pfn);
|
|
void Remove(SHashChain *pNode);
|
|
|
|
virtual BOOL Compare(const void *k, SHashChain *pNode, DWORD dwHash) = 0;
|
|
virtual DWORD HashNode(SHashChain *pNode) = 0;
|
|
|
|
protected:
|
|
SHashChain *Lookup(DWORD dwHash, const void *k);
|
|
void Add(DWORD dwHash, SHashChain *pNode);
|
|
|
|
private:
|
|
SHashChain *_buckets; // ptr to array of double linked lists
|
|
};
|
|
|
|
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Class: CUUIDHashTable
|
|
//
|
|
// Synopsis: This table inherits from CHashTable. It hashs based on a UUID.
|
|
//
|
|
// Nodes must be allocated with new. A cleanup function is
|
|
// optionally called for each node when the table is cleaned up.
|
|
//
|
|
// Notes: All locking must be done outside the class via LOCK/UNLOCK.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
class CUUIDHashTable : public CHashTable
|
|
{
|
|
public:
|
|
virtual BOOL Compare(const void *k, SHashChain *pNode, DWORD dwHash);
|
|
virtual DWORD HashNode(SHashChain *pNode);
|
|
|
|
DWORD Hash(REFGUID k);
|
|
SUUIDHashNode *Lookup(DWORD dwHash, REFGUID k);
|
|
void Add(DWORD dwHash, REFGUID k, SUUIDHashNode *pNode);
|
|
};
|
|
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Class: CStringHashTable
|
|
//
|
|
// Synopsis: String based hash table, uses a DUALSTRINGARRAY as the key,
|
|
//
|
|
// Nodes must be allocated with new. A cleanup function is
|
|
// optionally called for each node when the table is cleaned up.
|
|
//
|
|
// Notes: All locking must be done outside the class via LOCK/UNLOCK.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
class CStringHashTable : public CHashTable
|
|
{
|
|
public:
|
|
virtual BOOL Compare(const void *k, SHashChain *pNode, DWORD dwHash);
|
|
virtual DWORD HashNode(SHashChain *pNode);
|
|
|
|
DWORD Hash(DUALSTRINGARRAY *psaKey);
|
|
SStringHashNode *Lookup(DWORD dwHash, DUALSTRINGARRAY *psaKey);
|
|
void Add(DWORD dwHash, DUALSTRINGARRAY *psaKey, SStringHashNode *pNode);
|
|
};
|
|
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Class: CNameHashTable
|
|
//
|
|
// Synopsis: Name based hash table, uses a string as the key,
|
|
//
|
|
// Nodes must be allocated with new. A cleanup function is
|
|
// optionally called for each node when the table is cleaned up.
|
|
//
|
|
// Notes: All locking must be done outside the class via LOCK/UNLOCK.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
class CNameHashTable : public CHashTable
|
|
{
|
|
public:
|
|
virtual BOOL Compare(const void *k, SHashChain *pNode, DWORD dwHash);
|
|
virtual DWORD HashNode(SHashChain *pNode);
|
|
|
|
void Cleanup();
|
|
ULONG DecRef( ULONG cRefs, REFIPID ipid, SECURITYBINDING *pName );
|
|
DWORD Hash ( REFIPID ipid, SECURITYBINDING *pName );
|
|
HRESULT IncRef( ULONG cRefs, REFIPID ipid, SECURITYBINDING *pName );
|
|
void Initialize() { CHashTable::Initialize( SRFBuckets ); }
|
|
};
|
|
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CUUIDHashTable::Hash
|
|
//
|
|
// Synopsis: Computes the hash value for a given key.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
inline DWORD CUUIDHashTable::Hash(REFIID k)
|
|
{
|
|
const DWORD *tmp = (DWORD *) &k;
|
|
DWORD sum = tmp[0] + tmp[1] + tmp[2] + tmp[3];
|
|
return sum % NUM_HASH_BUCKETS;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CUUIDHashTable::Lookup
|
|
//
|
|
// Synopsis: Finds the node with the requested key.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
inline SUUIDHashNode *CUUIDHashTable::Lookup(DWORD iHash, REFGUID k)
|
|
{
|
|
return (SUUIDHashNode *) CHashTable::Lookup( iHash, (const void *) &k );
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CUUIDHashTable::Add
|
|
//
|
|
// Synopsis: Inserts the specified node.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
inline void CUUIDHashTable::Add(DWORD iHash, REFGUID k, SUUIDHashNode *pNode)
|
|
{
|
|
// set the key
|
|
pNode->key = k;
|
|
|
|
CHashTable::Add( iHash, (SHashChain *) pNode );
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CStringHashTable::Lookup
|
|
//
|
|
// Synopsis: Searches for a given key in the hash table.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
inline SStringHashNode *CStringHashTable::Lookup(DWORD dwHash, DUALSTRINGARRAY *psaKey)
|
|
{
|
|
return (SStringHashNode *) CHashTable::Lookup( dwHash, (const void *) psaKey);
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CStringHashTable::Add
|
|
//
|
|
// Synopsis: Adds an element to the hash table. The element must
|
|
// be allocated using new. The Cleanup method will call
|
|
// an optional Cleanup function, then will call delete on
|
|
// the element.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
inline void CStringHashTable::Add(DWORD dwHash, DUALSTRINGARRAY *psaKey, SStringHashNode *pNode)
|
|
{
|
|
// set the key and hash values
|
|
pNode->psaKey = psaKey;
|
|
pNode->dwHash = dwHash;
|
|
|
|
CHashTable::Add( dwHash, (SHashChain *) pNode );
|
|
}
|
|
|
|
#endif // _HASHTBL_HXX_
|