mirror of https://github.com/lianthony/NT4.0
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.
432 lines
12 KiB
432 lines
12 KiB
//+--------------------------------------------------------------------------
|
|
//
|
|
// File: hash.cxx
|
|
//
|
|
// Contents: class for maintaining a hash table.
|
|
//
|
|
// Classes: CUUIDHashTable
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
#include <ole2int.h>
|
|
#include <hash.hxx> // CUUIDHashTable
|
|
#include <locks.hxx> // ASSERT_LOCK_HELD
|
|
#include <service.hxx> // SASIZE
|
|
|
|
|
|
//+------------------------------------------------------------------------
|
|
// Type definitions
|
|
|
|
typedef struct
|
|
{
|
|
const IPID *pIpid;
|
|
SECURITYBINDING *pName;
|
|
} SNameKey;
|
|
|
|
//+------------------------------------------------------------------------
|
|
//
|
|
// Secure references hash table buckets. This is defined as a global
|
|
// so that we dont have to run any code to initialize the hash table.
|
|
//
|
|
//+------------------------------------------------------------------------
|
|
SHashChain SRFBuckets[23] =
|
|
{
|
|
{&SRFBuckets[0], &SRFBuckets[0]},
|
|
{&SRFBuckets[1], &SRFBuckets[1]},
|
|
{&SRFBuckets[2], &SRFBuckets[2]},
|
|
{&SRFBuckets[3], &SRFBuckets[3]},
|
|
{&SRFBuckets[4], &SRFBuckets[4]},
|
|
{&SRFBuckets[5], &SRFBuckets[5]},
|
|
{&SRFBuckets[6], &SRFBuckets[6]},
|
|
{&SRFBuckets[7], &SRFBuckets[7]},
|
|
{&SRFBuckets[8], &SRFBuckets[8]},
|
|
{&SRFBuckets[9], &SRFBuckets[9]},
|
|
{&SRFBuckets[10], &SRFBuckets[10]},
|
|
{&SRFBuckets[11], &SRFBuckets[11]},
|
|
{&SRFBuckets[12], &SRFBuckets[12]},
|
|
{&SRFBuckets[13], &SRFBuckets[13]},
|
|
{&SRFBuckets[14], &SRFBuckets[14]},
|
|
{&SRFBuckets[15], &SRFBuckets[15]},
|
|
{&SRFBuckets[16], &SRFBuckets[16]},
|
|
{&SRFBuckets[17], &SRFBuckets[17]},
|
|
{&SRFBuckets[18], &SRFBuckets[18]},
|
|
{&SRFBuckets[19], &SRFBuckets[19]},
|
|
{&SRFBuckets[20], &SRFBuckets[20]},
|
|
{&SRFBuckets[21], &SRFBuckets[21]},
|
|
{&SRFBuckets[22], &SRFBuckets[22]}
|
|
};
|
|
|
|
CNameHashTable gSRFTbl;
|
|
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Function: DummyCleanup
|
|
//
|
|
// Synopsis: Callback for CHashTable::Cleanup that does nothing.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
void DummyCleanup( SHashChain *pIgnore )
|
|
{
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CHashTable::Cleanup
|
|
//
|
|
// Synopsis: Cleans up the hash table by deleteing leftover entries.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
void CHashTable::Cleanup(PFNCLEANUP *pfnCleanup)
|
|
{
|
|
Win4Assert(pfnCleanup);
|
|
ASSERT_LOCK_HELD
|
|
|
|
for (ULONG iHash=0; iHash < NUM_HASH_BUCKETS; iHash++)
|
|
{
|
|
// the ptrs could be NULL if the hash table was never initialized.
|
|
|
|
while (_buckets[iHash].pNext != NULL &&
|
|
_buckets[iHash].pNext != &_buckets[iHash])
|
|
{
|
|
// remove the entry from the list and call it's cleanup function
|
|
SHashChain *pNode = _buckets[iHash].pNext;
|
|
|
|
Remove(pNode);
|
|
(pfnCleanup)(pNode);
|
|
}
|
|
}
|
|
|
|
#if DBG==1
|
|
// Verify that the hash table is empty or uninitialized.
|
|
for (iHash = 0; iHash < NUM_HASH_BUCKETS; iHash++)
|
|
{
|
|
Win4Assert( _buckets[iHash].pNext == &_buckets[iHash] ||
|
|
_buckets[iHash].pNext == NULL);
|
|
Win4Assert( _buckets[iHash].pPrev == &_buckets[iHash] ||
|
|
_buckets[iHash].pPrev == NULL);
|
|
}
|
|
#endif
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CHashTable::Lookup
|
|
//
|
|
// Synopsis: Searches for a given key in the hash table.
|
|
//
|
|
// Note: iHash is between 0 and -1, not 0 and NUM_HASH_BUCKETS
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
SHashChain *CHashTable::Lookup(DWORD dwHash, const void *k)
|
|
{
|
|
ASSERT_LOCK_HELD
|
|
|
|
// compute the index to the hash chain (it's the hash value of the key
|
|
// mod the number of buckets in the hash table)
|
|
|
|
DWORD iHash = dwHash % NUM_HASH_BUCKETS;
|
|
|
|
SHashChain *pNode = _buckets[iHash].pNext;
|
|
|
|
// Search the destination bucket for the key.
|
|
while (pNode != &_buckets[iHash])
|
|
{
|
|
if (Compare( k, pNode, dwHash ))
|
|
return pNode;
|
|
|
|
pNode = pNode->pNext;
|
|
}
|
|
|
|
return NULL;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CHashTable::Add
|
|
//
|
|
// Synopsis: Adds an element to the hash table. The Cleanup method will
|
|
// call a Cleanup function that can be used to delete the
|
|
// element.
|
|
//
|
|
// Note: iHash is between 0 and -1, not 0 and NUM_HASH_BUCKETS
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
void CHashTable::Add(DWORD dwHash, SHashChain *pNode)
|
|
{
|
|
ASSERT_LOCK_HELD
|
|
|
|
// Add the node to the bucket chain.
|
|
SHashChain *pHead = &_buckets[dwHash % NUM_HASH_BUCKETS];
|
|
SHashChain *pNew = pNode;
|
|
|
|
pNew->pPrev = pHead;
|
|
pHead->pNext->pPrev = pNew;
|
|
pNew->pNext = pHead->pNext;
|
|
pHead->pNext = pNew;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CUUIDHashTable::Remove
|
|
//
|
|
// Synopsis: Removes an element from the hash table.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
void CHashTable::Remove(SHashChain *pNode)
|
|
{
|
|
ASSERT_LOCK_HELD
|
|
|
|
pNode->pPrev->pNext = pNode->pNext;
|
|
pNode->pNext->pPrev = pNode->pPrev;
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CUUIDHashTable::HashNode
|
|
//
|
|
// Synopsis: Computes the hash value for a given node.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
DWORD CUUIDHashTable::HashNode(SHashChain *pNode)
|
|
{
|
|
return Hash( ((SUUIDHashNode *) pNode)->key );
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CUUIDHashTable::Compare
|
|
//
|
|
// Synopsis: Compares a node and a key.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
BOOL CUUIDHashTable::Compare(const void *k, SHashChain *pNode, DWORD dwHash )
|
|
{
|
|
return InlineIsEqualGUID(*(const UUID *)k,
|
|
((SUUIDHashNode *)pNode)->key);
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CStringHashTable::Hash
|
|
//
|
|
// Synopsis: Computes the hash value for a given key.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
DWORD CStringHashTable::Hash(DUALSTRINGARRAY *psaKey)
|
|
{
|
|
DWORD dwHash = 0;
|
|
DWORD *pdw = (DWORD *) &psaKey->aStringArray[0];
|
|
|
|
for (USHORT i=0; i< (psaKey->wNumEntries/2); i++)
|
|
{
|
|
dwHash = (dwHash << 8) ^ *pdw++;
|
|
}
|
|
|
|
return dwHash;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CStringHashTable::HashNode
|
|
//
|
|
// Synopsis: Computes the hash value for a given node.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
DWORD CStringHashTable::HashNode(SHashChain *pNode)
|
|
{
|
|
return Hash( ((SStringHashNode *) pNode)->psaKey );
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CStringHashTable::Compare
|
|
//
|
|
// Synopsis: Compares a node and a key.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
BOOL CStringHashTable::Compare(const void *k, SHashChain *pNode, DWORD dwHash )
|
|
{
|
|
SStringHashNode *pSNode = (SStringHashNode *) pNode;
|
|
const DUALSTRINGARRAY *psaKey = (const DUALSTRINGARRAY *) k;
|
|
|
|
if (dwHash == pSNode->dwHash)
|
|
{
|
|
// a quick compare of the hash values found a match, now do
|
|
// a full compare of the key (Note: if the sizes of the two
|
|
// Keys are different, we exit the memcmp on the first dword,
|
|
// so we dont have to worry about walking off the endo of one
|
|
// of the Keys during the memcmp).
|
|
|
|
return !memcmp(psaKey, pSNode->psaKey, SASIZE(psaKey->wNumEntries));
|
|
}
|
|
return FALSE;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CNameHashTable::Cleanup
|
|
//
|
|
// Synopsis: Call the base cleanup routine with a dummy callback function
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
void CNameHashTable::Cleanup()
|
|
{
|
|
CHashTable::Cleanup( DummyCleanup );
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CNameHashTable::Hash
|
|
//
|
|
// Synopsis: Computes the hash value for a given key.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
DWORD CNameHashTable::Hash( REFIPID ipid, SECURITYBINDING *pName )
|
|
{
|
|
DWORD dwHash = 0;
|
|
DWORD *pdw = (DWORD *) &ipid;
|
|
DWORD dwLen = lstrlenW( (WCHAR *) pName ) >> 1;
|
|
ULONG i;
|
|
|
|
// First hash the IPID.
|
|
for (i=0; i < 4; i++)
|
|
{
|
|
dwHash = (dwHash << 8) ^ *pdw++;
|
|
}
|
|
|
|
// Then hash the name.
|
|
pdw = (DWORD *) pName;
|
|
for (i=0; i < dwLen; i++)
|
|
{
|
|
dwHash = (dwHash << 8) ^ *pdw++;
|
|
}
|
|
|
|
return dwHash;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CNameHashTable::HashNode
|
|
//
|
|
// Synopsis: Computes the hash value for a given node.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
DWORD CNameHashTable::HashNode(SHashChain *pNode)
|
|
{
|
|
SNameHashNode *pNNode = (SNameHashNode *) pNode;
|
|
return Hash( pNNode->ipid, &pNNode->sName );
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CNameHashTable::Compare
|
|
//
|
|
// Synopsis: Compares a node and a key.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
BOOL CNameHashTable::Compare(const void *k, SHashChain *pNode, DWORD dwHash )
|
|
{
|
|
SNameHashNode *pNNode = (SNameHashNode *) pNode;
|
|
const SNameKey *pKey = (const SNameKey *) k;
|
|
|
|
if (dwHash == pNNode->dwHash)
|
|
{
|
|
// a quick compare of the hash values found a match, now do
|
|
// a full compare of the key
|
|
if (*pKey->pIpid == pNNode->ipid)
|
|
return !lstrcmpW( (WCHAR *) pKey->pName, (WCHAR *) &pNNode->sName );
|
|
else
|
|
return FALSE;
|
|
}
|
|
|
|
return FALSE;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CNameHashTable::IncRef
|
|
//
|
|
// Synopsis: Find or create an entry for the specified name. Increment
|
|
// its reference count.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
HRESULT CNameHashTable::IncRef( ULONG cRefs, REFIPID ipid,
|
|
SECURITYBINDING *pName )
|
|
{
|
|
SNameHashNode *pNode;
|
|
DWORD dwHash = Hash( ipid, pName );
|
|
HRESULT hr = S_OK;
|
|
ULONG lLen;
|
|
SNameKey key;
|
|
|
|
ASSERT_LOCK_HELD
|
|
|
|
// See if there is already a node in the table.
|
|
key.pIpid = &ipid;
|
|
key.pName = pName;
|
|
pNode = (SNameHashNode *) Lookup( dwHash, &key );
|
|
|
|
// If not, create one.
|
|
if (pNode == NULL)
|
|
{
|
|
lLen = lstrlenW( (WCHAR *) pName );
|
|
pNode = (SNameHashNode *) PrivMemAlloc( sizeof(SNameHashNode) +
|
|
lLen*sizeof(WCHAR) );
|
|
if (pNode != NULL)
|
|
{
|
|
pNode->cRef = 0;
|
|
pNode->dwHash = dwHash;
|
|
pNode->ipid = ipid;
|
|
memcpy( &pNode->sName, pName, (lLen + 1) * sizeof(WCHAR) );
|
|
Add( dwHash, &pNode->chain );
|
|
}
|
|
else
|
|
hr = E_OUTOFMEMORY;
|
|
}
|
|
|
|
// Increment the reference count on the node.
|
|
if (pNode != NULL)
|
|
pNode->cRef += cRefs;
|
|
return hr;
|
|
}
|
|
|
|
//---------------------------------------------------------------------------
|
|
//
|
|
// Method: CNameHashTable::DecRef
|
|
//
|
|
// Synopsis: Decrement references for the specified name. Do not decrement
|
|
// more references then exist. Return the actual decrement count.
|
|
//
|
|
//---------------------------------------------------------------------------
|
|
ULONG CNameHashTable::DecRef( ULONG cRefs, REFIPID ipid,
|
|
SECURITYBINDING *pName )
|
|
{
|
|
SNameHashNode *pNode;
|
|
DWORD dwHash = Hash( ipid, pName );
|
|
SNameKey key;
|
|
|
|
ASSERT_LOCK_HELD
|
|
|
|
// Lookup the name.
|
|
key.pIpid = &ipid;
|
|
key.pName = pName;
|
|
pNode = (SNameHashNode *) Lookup( dwHash, &key );
|
|
|
|
if (pNode != NULL)
|
|
{
|
|
if (pNode->cRef < cRefs)
|
|
cRefs = pNode->cRef;
|
|
pNode->cRef -= cRefs;
|
|
if (pNode->cRef == 0)
|
|
{
|
|
Remove( &pNode->chain );
|
|
PrivMemFree( pNode );
|
|
}
|
|
}
|
|
else
|
|
cRefs = 0;
|
|
|
|
return cRefs;
|
|
}
|
|
|