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.
1764 lines
50 KiB
1764 lines
50 KiB
/*++
|
|
|
|
Copyright (c) 1997-1999 Microsoft Corporation
|
|
|
|
Module Name:
|
|
|
|
genhash.c
|
|
|
|
Abstract:
|
|
|
|
Generic Hash Table routines. Each hash table is an array of FRS_LIST entries
|
|
that provide interlocked access to each row of the hash table. Each table
|
|
is managed by a GENERIC_HASH_TABLE struct which holds function entry points for
|
|
freeing an entry, comparing keys, performing a hash calculation, printing
|
|
an entry and dumping the table.
|
|
|
|
|
|
Note: All hash entries must be prefixed with GENERIC_HASH_ROW_ENTRY at the
|
|
beginning of the structure.
|
|
|
|
Author:
|
|
|
|
David Orbits [davidor] 22-Apr-1997
|
|
|
|
Environment:
|
|
|
|
User Mode Service
|
|
|
|
Revision History:
|
|
|
|
|
|
--*/
|
|
|
|
#include <ntreppch.h>
|
|
#pragma hdrstop
|
|
|
|
#include <frs.h>
|
|
#include <genhash.h>
|
|
#include <tablefcn.h>
|
|
|
|
|
|
#pragma warning( disable:4102) // unreferenced label
|
|
|
|
|
|
|
|
|
|
PGENERIC_HASH_TABLE
|
|
GhtCreateTable(
|
|
PCHAR ArgName,
|
|
ULONG NumberRows,
|
|
ULONG KeyOffset,
|
|
ULONG KeyLength,
|
|
PGENERIC_HASH_FREE_ROUTINE GhtFree,
|
|
PGENERIC_HASH_COMPARE_ROUTINE GhtCompare,
|
|
PGENERIC_HASH_CALC_ROUTINE GhtHashCalc,
|
|
PGENERIC_HASH_PRINT_ROUTINE GhtPrint
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Allocate and initialize a hash table.
|
|
|
|
Arguments:
|
|
|
|
ArgName -- The table name. [16 byte max]
|
|
NumberRows -- The number of rows in the table.
|
|
KeyOffset -- The byte offset to the key value in each table entry.
|
|
KeyLength -- The byte length of the key value in each table entry.
|
|
GhtFree -- function to call to free an entry.
|
|
GhtCompare -- function to comoare two keys.
|
|
GhtHashCalc -- function to calculate the ULONG hash value on a key.
|
|
GhtPrint -- Function to print out a table entry.
|
|
GhtDump -- Function to call to dump all table entries.
|
|
|
|
Return Value:
|
|
|
|
ptr to a GENERIC_HASH_TABLE struct or NULL if failure.
|
|
use GetLastError for the error status.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtCreateTable:"
|
|
|
|
PGENERIC_HASH_TABLE HashTable;
|
|
PGENERIC_HASH_ROW_ENTRY RowBase, HashRowEntry;
|
|
ULONG NameLen;
|
|
ULONG WStatus;
|
|
ULONG i;
|
|
|
|
|
|
HashTable = (PGENERIC_HASH_TABLE) FrsAllocType(GENERIC_HASH_TABLE_TYPE);
|
|
|
|
RowBase = (PGENERIC_HASH_ROW_ENTRY) FrsAlloc(
|
|
NumberRows * sizeof(GENERIC_HASH_ROW_ENTRY));
|
|
|
|
NameLen = min(strlen(ArgName), 15);
|
|
CopyMemory(HashTable->Name, ArgName, NameLen);
|
|
HashTable->Name[NameLen] = '\0';
|
|
|
|
HashTable->NumberRows = NumberRows;
|
|
HashTable->GhtFree = GhtFree;
|
|
HashTable->GhtCompare = GhtCompare;
|
|
HashTable->GhtHashCalc = GhtHashCalc;
|
|
HashTable->GhtPrint = GhtPrint;
|
|
HashTable->KeyOffset = KeyOffset;
|
|
HashTable->KeyLength = KeyLength;
|
|
HashTable->RowLockEnabled = TRUE;
|
|
HashTable->RefCountEnabled = TRUE;
|
|
HashTable->HeapHandle = NULL;
|
|
HashTable->UseOffsets = FALSE;
|
|
HashTable->OffsetBase = 0;
|
|
HashTable->HashRowBase = RowBase;
|
|
HashTable->LockTimeout = 10000; // milliseconds
|
|
|
|
//
|
|
// Initialize all the hash table rows. Each has a critical section and
|
|
// an event to wait on.
|
|
//
|
|
HashRowEntry = RowBase;
|
|
|
|
for (i=0; i<NumberRows; i++) {
|
|
//
|
|
// Create the event first so if we fail GhtDestroyTable sees a null handle.
|
|
//
|
|
//HashRowEntry->Event = CreateEvent(NULL, TRUE, FALSE, NULL);
|
|
|
|
WStatus = FrsRtlInitializeList(&HashRowEntry->HashRow);
|
|
if (WStatus != ERROR_SUCCESS) {
|
|
goto CLEANUP;
|
|
}
|
|
|
|
//if (HashRowEntry->Event == NULL) {
|
|
// WStatus = GetLastError();
|
|
// goto CLEANUP;
|
|
//}
|
|
|
|
HashRowEntry += 1;
|
|
}
|
|
|
|
return HashTable;
|
|
|
|
|
|
CLEANUP:
|
|
|
|
HashTable->NumberRows = i+1;
|
|
GhtDestroyTable(HashTable);
|
|
SetLastError(WStatus);
|
|
return NULL;
|
|
|
|
}
|
|
|
|
|
|
VOID
|
|
GhtDestroyTable(
|
|
PGENERIC_HASH_TABLE HashTable
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Free all the memory for a hash table.
|
|
This includes any data elements left in the table.
|
|
No locks are acquired.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtDestroyTable:"
|
|
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
ULONG i;
|
|
|
|
if (HashTable == NULL) {
|
|
return;
|
|
}
|
|
|
|
RowEntry = HashTable->HashRowBase;
|
|
DPRINT1(5, "GhtDestroyTable for %s\n", HashTable->Name);
|
|
|
|
//
|
|
// Loop through all the Hash table rows and delete any entries still on
|
|
// each row.
|
|
//
|
|
for (i=0; i<HashTable->NumberRows; i++, RowEntry++) {
|
|
if (RowEntry->HashRow.Count != 0) {
|
|
//DPRINT2(5, "HashRow: %d, RowCount %d\n",i, RowEntry->HashRow.Count);
|
|
}
|
|
|
|
ForEachListEntryLock(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
|
|
FrsRtlRemoveEntryListLock(&RowEntry->HashRow, &pE->ListEntry);
|
|
|
|
//DPRINT4(5, " Deleteing entry: %08x, Hval %08x, Index %d, refcnt %d\n",
|
|
// pE, pE->HashValue, i, pE->ReferenceCount);
|
|
|
|
(HashTable->GhtFree)(HashTable, pE);
|
|
);
|
|
|
|
FrsRtlDeleteList(&RowEntry->HashRow);
|
|
//if (RowEntry->Event != NULL) {
|
|
// FRS_CLOSE(RowEntry->Event);
|
|
//}
|
|
}
|
|
|
|
FrsFree(HashTable->HashRowBase);
|
|
FrsFreeType(HashTable);
|
|
return;
|
|
}
|
|
|
|
|
|
ULONG
|
|
GhtCleanTableByFilter(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
IN PGENERIC_HASH_ENUM_ROUTINE Function,
|
|
PVOID Context
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Free the elements in the hash table for which the predicate function
|
|
returns TRUE.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
Function - The function to call for each record in the table. It is of
|
|
of type PGENERIC_HASH_FILTER_ROUTINE.
|
|
Return TRUE to delete the entry in the table.
|
|
Context -- Arg to pass thru to the filter function.
|
|
|
|
Return Value:
|
|
|
|
The number of entries deleted.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtCleanTableByFilter:"
|
|
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
ULONG i;
|
|
ULONG Count = 0;
|
|
|
|
if (HashTable == NULL) {
|
|
return Count;
|
|
}
|
|
|
|
RowEntry = HashTable->HashRowBase;
|
|
|
|
//
|
|
// Loop through all the Hash table rows and delete any entries still on
|
|
// each row.
|
|
//
|
|
for (i=0; i<HashTable->NumberRows; i++, RowEntry++) {
|
|
if (RowEntry->HashRow.Count != 0) {
|
|
//DPRINT2(4, "HashRow: %d, RowCount %d\n", i, RowEntry->HashRow.Count);
|
|
}
|
|
|
|
ForEachListEntry(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
//
|
|
// The iterator pE is of type GENERIC_HASH_ENTRY_HEADER.
|
|
// Call predicate to see if we should do the delete.
|
|
//
|
|
if ((Function)(HashTable, pE, Context)) {
|
|
|
|
FrsRtlRemoveEntryListLock(&RowEntry->HashRow, &pE->ListEntry);
|
|
|
|
//DPRINT4(4, "Deleting entry: %08x, Hval %08x, Index %d, refcnt %d\n",
|
|
// pE, pE->HashValue, i, pE->ReferenceCount);
|
|
|
|
(HashTable->GhtFree)(HashTable, pE);
|
|
|
|
Count += 1;
|
|
}
|
|
);
|
|
}
|
|
|
|
return Count;
|
|
}
|
|
|
|
|
|
|
|
#if DBG
|
|
VOID
|
|
GhtDumpTable(
|
|
ULONG Sev,
|
|
PGENERIC_HASH_TABLE HashTable
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Call the print routine for each element in the table.
|
|
|
|
Arguments:
|
|
|
|
Sev -- DPRINT severity level.
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtDumpTable:"
|
|
|
|
PGENERIC_HASH_ROW_ENTRY HashRowEntry;
|
|
ULONG i;
|
|
|
|
HashRowEntry = HashTable->HashRowBase;
|
|
DPRINT(Sev,"----------------------------------------------\n");
|
|
DPRINT(Sev,"----------------------------------------------\n");
|
|
DPRINT1(Sev, "GhtDumpTable for %s\n", HashTable->Name);
|
|
DPRINT(Sev,"----------------------------------------------\n");
|
|
DPRINT(Sev,"----------------------------------------------\n");
|
|
|
|
//
|
|
// Loop through all the Hash table rows and call the print function for
|
|
// each element.
|
|
//
|
|
for (i=0; i<HashTable->NumberRows; i++) {
|
|
if (HashRowEntry->HashRow.Count != 0) {
|
|
DPRINT(Sev, " \n");
|
|
DPRINT(Sev,"----------------------------------------------\n");
|
|
DPRINT2(Sev, "HashRow: %d, RowCount %d\n",
|
|
i, HashRowEntry->HashRow.Count);
|
|
DPRINT5(Sev, "Inserts: %d, Removes: %d, Compares: %d, Lookups: %d, Lookupfails: %d \n",
|
|
HashRowEntry->RowInserts,
|
|
HashRowEntry->RowRemoves,
|
|
HashRowEntry->RowCompares,
|
|
HashRowEntry->RowLookups,
|
|
HashRowEntry->RowLookupFails);
|
|
}
|
|
|
|
ForEachListEntry(&HashRowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
(HashTable->GhtPrint)(HashTable, pE);
|
|
);
|
|
|
|
HashRowEntry += 1;
|
|
}
|
|
}
|
|
#endif DBG
|
|
|
|
|
|
ULONG_PTR
|
|
GhtEnumerateTable(
|
|
IN PGENERIC_HASH_TABLE HashTable,
|
|
IN PGENERIC_HASH_ENUM_ROUTINE Function,
|
|
IN PVOID Context
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine walks through the entries in a generic hash table and
|
|
calls the function provided with the entry address and the context.
|
|
No locks are taken by this function so the called function can make
|
|
calls to other GHT routines to lookup or insert new entries.
|
|
|
|
THis routine increments the ref count on each entry before it makes the
|
|
call to ensure the entry does not vanish. It keeps a pointer to the
|
|
entry that tells it where to continue the scan. If the argument function
|
|
inserts an entry that is earlier in the table the enumeration will not
|
|
pick it up.
|
|
|
|
Arguments:
|
|
|
|
HashTable - The context of the Hash Table to enumerate.
|
|
Function - The function to call for each record in the table. It is of
|
|
of type PGENERIC_HASH_ENUM_ROUTINE. Return FALSE to abort the
|
|
enumeration else true.
|
|
Context - A context ptr to pass through to the RecordFunction.
|
|
|
|
Return Value:
|
|
|
|
The status code from the argument function.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtEnumerateTable:"
|
|
|
|
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
ULONG i;
|
|
ULONG_PTR WStatus;
|
|
|
|
RowEntry = HashTable->HashRowBase;
|
|
|
|
DPRINT(5,"----------------------------------------------\n");
|
|
DPRINT(5,"----------------------------------------------\n");
|
|
DPRINT1(5, "GhtEnumerateTable for %s\n", HashTable->Name);
|
|
DPRINT(5,"----------------------------------------------\n");
|
|
DPRINT(5,"----------------------------------------------\n");
|
|
|
|
//
|
|
// Loop through all the Hash table rows and call the print function for
|
|
// each element.
|
|
//
|
|
for (i=0; i<HashTable->NumberRows; i++) {
|
|
if (RowEntry->HashRow.Count != 0) {
|
|
DPRINT(5, " \n");
|
|
DPRINT(5,"----------------------------------------------\n");
|
|
DPRINT2(5, "HashRow: %d, RowCount %d\n",
|
|
i, RowEntry->HashRow.Count);
|
|
}
|
|
|
|
ForEachListEntryLock(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
|
|
InterlockedIncrement(&pE->ReferenceCount);
|
|
DPRINT2(5, "inc ref: %08x, %d\n", pE, pE->ReferenceCount);
|
|
|
|
WStatus = (Function)(HashTable, pE, Context);
|
|
|
|
InterlockedDecrement(&pE->ReferenceCount);
|
|
DPRINT2(5, "dec ref: %08x, %d\n", pE, pE->ReferenceCount);
|
|
|
|
// Note: If caller needs this we should add code to check for
|
|
// zero ref count and call the delete function.
|
|
|
|
if( WStatus != 0 ) {
|
|
return WStatus;
|
|
}
|
|
);
|
|
|
|
RowEntry += 1;
|
|
}
|
|
|
|
return ERROR_SUCCESS;
|
|
|
|
}
|
|
|
|
|
|
|
|
ULONG_PTR
|
|
GhtEnumerateTableNoRef(
|
|
IN PGENERIC_HASH_TABLE HashTable,
|
|
IN PGENERIC_HASH_ENUM_ROUTINE Function,
|
|
IN PVOID Context
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine walks through the entries in a generic hash table and
|
|
calls the function provided with the entry address and the context.
|
|
No locks are taken by this function so the called function can make
|
|
calls to other GHT routines to lookup or insert new entries.
|
|
|
|
THis routine does not take a ref count out on the entry.
|
|
It keeps a pointer to the next entry that tells it where to continue
|
|
the scan if the argument function deletes the entry. If the argument function
|
|
inserts an entry that is earlier in the table the enumeration will not
|
|
pick it up.
|
|
|
|
Arguments:
|
|
|
|
HashTable - The context of the Hash Table to enumerate.
|
|
Function - The function to call for each record in the table. It is of
|
|
of type PGENERIC_HASH_ENUM_ROUTINE. Return FALSE to abort the
|
|
enumeration else true.
|
|
Context - A context ptr to pass through to the RecordFunction.
|
|
|
|
Return Value:
|
|
|
|
The status code from the argument function.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtEnumerateTableNoRef:"
|
|
|
|
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
ULONG i;
|
|
ULONG_PTR WStatus;
|
|
|
|
RowEntry = HashTable->HashRowBase;
|
|
|
|
DPRINT1(5, "GhtEnumerateTableNoRef for %s\n", HashTable->Name);
|
|
|
|
//
|
|
// Loop through all the Hash table rows and call the print function for
|
|
// each element.
|
|
//
|
|
for (i=0; i<HashTable->NumberRows; i++) {
|
|
if (RowEntry->HashRow.Count != 0) {
|
|
DPRINT(5, " \n");
|
|
DPRINT(5,"----------------------------------------------\n");
|
|
DPRINT2(5, "HashRow: %d, RowCount %d\n",
|
|
i, RowEntry->HashRow.Count);
|
|
}
|
|
|
|
ForEachListEntryLock(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
|
|
WStatus = (Function)(HashTable, pE, Context);
|
|
|
|
if (WStatus != 0) {
|
|
return WStatus;
|
|
}
|
|
);
|
|
|
|
RowEntry += 1;
|
|
}
|
|
|
|
return (ULONG_PTR)0;
|
|
}
|
|
|
|
|
|
|
|
|
|
PGENERIC_HASH_ENTRY_HEADER
|
|
GhtGetNextEntry(
|
|
IN PGENERIC_HASH_TABLE HashTable,
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine returns the next entry in the table that follows the HashEntry
|
|
argument. If the HashEntry is NULL it returns the first entry.
|
|
|
|
It gets the row lock containing the current entry, decrements the
|
|
ref count on the entry. It scans forward to the next entry in the table
|
|
getting its row lock if needed, increments its ref count and returns the
|
|
pointer. If the end of table is reached NULL is returned.
|
|
|
|
If an entry is inserted earlier in the table the enumeration will not
|
|
pick it up.
|
|
|
|
Arguments:
|
|
|
|
HashTable - The context of the Hash Table to enumerate.
|
|
|
|
HashEntry - The current entry we are looking at. Used to get the next entry
|
|
If null start scan at beginning of table.
|
|
|
|
Return Value:
|
|
|
|
The status code from the argument function.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtGetNextEntry:"
|
|
|
|
|
|
PGENERIC_HASH_ROW_ENTRY LastRow;
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
PLIST_ENTRY Entry;
|
|
RowEntry = HashTable->HashRowBase;
|
|
|
|
|
|
//
|
|
// Get the hash value for the element and compute the index and RowEntry
|
|
// address. Then get the row lock.
|
|
//
|
|
if (HashEntry != NULL) {
|
|
Hval = HashEntry->HashValue;
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry += HvalIndex;
|
|
|
|
//
|
|
// Get the row lock and decrement the ref count.
|
|
// (could delete if it hits zero)
|
|
//
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
InterlockedDecrement(&HashEntry->ReferenceCount);
|
|
//
|
|
// look for next entry in same row.
|
|
// if found, bump ref count, drop lock, return entry.
|
|
//
|
|
Entry = GetListNext(&HashEntry->ListEntry);
|
|
if (Entry != &RowEntry->HashRow.ListHead) {
|
|
goto FOUND;
|
|
}
|
|
//
|
|
// if not found drop row lock and execute scan code below
|
|
// starting from next row entry.
|
|
//
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
RowEntry += 1;
|
|
}
|
|
|
|
//
|
|
// Scan the rest of the table for a non-empty row.
|
|
//
|
|
LastRow = HashTable->HashRowBase + HashTable->NumberRows;
|
|
|
|
while (RowEntry < LastRow) {
|
|
|
|
if (RowEntry->HashRow.Count != 0) {
|
|
//
|
|
// Found one. Get the row lock and recheck the count incase
|
|
// someone beat us too it.
|
|
//
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
if (RowEntry->HashRow.Count == 0) {
|
|
//
|
|
// Too bad. Continue scan.
|
|
//
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
RowEntry += 1;
|
|
continue;
|
|
}
|
|
//
|
|
// We got one. Get the entry address, bump the ref count, drop lock.
|
|
//
|
|
FRS_ASSERT(!IsListEmpty(&RowEntry->HashRow.ListHead));
|
|
|
|
Entry = GetListHead(&RowEntry->HashRow.ListHead);
|
|
goto FOUND;
|
|
}
|
|
|
|
RowEntry += 1;
|
|
}
|
|
|
|
return NULL;
|
|
|
|
FOUND:
|
|
HashEntry = CONTAINING_RECORD(Entry, GENERIC_HASH_ENTRY_HEADER, ListEntry);
|
|
InterlockedIncrement(&HashEntry->ReferenceCount);
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return HashEntry;
|
|
|
|
}
|
|
|
|
|
|
ULONG
|
|
GhtCountEntries(
|
|
IN PGENERIC_HASH_TABLE HashTable
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine walks through the rows in a generic hash table and
|
|
adds up the entry count. It takes no locks so the count is approx.
|
|
Caller must know the table can't go away.
|
|
|
|
Arguments:
|
|
|
|
HashTable - The context of the Hash Table to count.
|
|
|
|
Return Value:
|
|
|
|
The count.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtCountEntries:"
|
|
|
|
|
|
ULONG Total = 0;
|
|
PGENERIC_HASH_ROW_ENTRY LastRow, RowEntry = HashTable->HashRowBase;
|
|
|
|
//
|
|
// Loop through all the Hash table rows and add counts.
|
|
//
|
|
|
|
LastRow = RowEntry + HashTable->NumberRows;
|
|
|
|
while (RowEntry < LastRow) {
|
|
Total += RowEntry->HashRow.Count;
|
|
RowEntry += 1;
|
|
}
|
|
|
|
return Total;
|
|
|
|
}
|
|
|
|
|
|
PGENERIC_HASH_ENTRY_HEADER
|
|
GhtGetEntryNumber(
|
|
IN PGENERIC_HASH_TABLE HashTable,
|
|
IN LONG EntryNumber
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine walks through the rows in a generic hash table
|
|
counting entries as it goes. It returns the requested entry (by number)
|
|
from the table. Note this will not be the same entry from call to call
|
|
because of intervening inserts and deletes. It takes no locks until it
|
|
gets to the row of the table that contains the entry.
|
|
The ref count on the entry is incremented.
|
|
|
|
Arguments:
|
|
|
|
HashTable - The context of the Hash Table to enumerate.
|
|
|
|
EntryNumber - The ordinal number of the entry in the table.
|
|
zero is the first entry.
|
|
|
|
Return Value:
|
|
|
|
The address of the entry.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtGetEntryNumber:"
|
|
|
|
|
|
PGENERIC_HASH_ROW_ENTRY LastRow, RowEntry = HashTable->HashRowBase;
|
|
ULONG Rcount;
|
|
PLIST_ENTRY Entry;
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry;
|
|
|
|
FRS_ASSERT(EntryNumber >= 0);
|
|
|
|
//
|
|
// Loop through Hash table rows looking for the row with the entry.
|
|
//
|
|
LastRow = RowEntry + HashTable->NumberRows;
|
|
|
|
while (RowEntry < LastRow) {
|
|
|
|
Rcount = RowEntry->HashRow.Count;
|
|
|
|
if (Rcount > 0) {
|
|
EntryNumber -= Rcount;
|
|
if (EntryNumber < 0) {
|
|
//
|
|
// Should be in this row. Get the row lock and recheck
|
|
// the count incase someone beat us too it.
|
|
//
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
if (RowEntry->HashRow.Count < Rcount) {
|
|
//
|
|
// Too bad. It got shorter, Retry test.
|
|
//
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
EntryNumber += Rcount;
|
|
continue;
|
|
}
|
|
|
|
//
|
|
// We got one. Get the entry address, bump the ref count, drop lock.
|
|
//
|
|
EntryNumber += Rcount;
|
|
Entry = GetListHead(&RowEntry->HashRow.ListHead);
|
|
while (EntryNumber-- > 0) {
|
|
FRS_ASSERT(Entry != &RowEntry->HashRow.ListHead);
|
|
Entry = GetListNext(Entry);
|
|
}
|
|
|
|
HashEntry = CONTAINING_RECORD(Entry, GENERIC_HASH_ENTRY_HEADER, ListEntry);
|
|
InterlockedIncrement(&HashEntry->ReferenceCount);
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return HashEntry;
|
|
|
|
}
|
|
}
|
|
RowEntry += 1;
|
|
}
|
|
|
|
return NULL;
|
|
|
|
}
|
|
|
|
|
|
|
|
PGENERIC_HASH_ENTRY_HEADER
|
|
GhtQuickCheck(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry,
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry,
|
|
ULONG Hval
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Internal function to do a quick scan of a row to find an entry.
|
|
Used in debug code to check that an entry is actually in the table.
|
|
|
|
|
|
Assumes caller has the row lock.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
RowEntry -- ptr to the ROW_ENTRY struct.
|
|
HashEntry -- ptr to the hash entry we are looking for.
|
|
Hval -- hash value we are looking for.
|
|
|
|
Return Value:
|
|
|
|
ptr to entry if we find it.
|
|
NULL if we don't.
|
|
|
|
--*/
|
|
{
|
|
PCHAR pKeyValue;
|
|
|
|
pKeyValue = ((PCHAR)HashEntry) + HashTable->KeyOffset;
|
|
|
|
ForEachListEntryLock(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
//
|
|
// The iterator pE is of type PGENERIC_HASH_ENTRY_HEADER.
|
|
//
|
|
if (pE->HashValue == Hval) {
|
|
if ((HashTable->GhtCompare)(pKeyValue,
|
|
((PCHAR)pE) + HashTable->KeyOffset,
|
|
HashTable->KeyLength)) {
|
|
//
|
|
// Found it.
|
|
//
|
|
return pE;
|
|
}
|
|
}
|
|
);
|
|
|
|
return NULL;
|
|
}
|
|
|
|
|
|
GHT_STATUS
|
|
GhtLookup2(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID pKeyValue,
|
|
BOOL WaitIfLocked,
|
|
PVOID *RetHashEntry,
|
|
ULONG DupIndex
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Takes the KeyValue and calls the hash function which returns a ULONG. Then
|
|
calculate the index of HashValue Mod TableLenth. With the index find the hash
|
|
row header and acquire the row lock. It then walks the list looking for a hash
|
|
value match on the KeyValue. The entires are kept in ascending order so the
|
|
lookup stops as soon as new entry value is < the list entry value. Then call
|
|
the compare routine to see if the key data in the entry (entry+key offset)
|
|
matches the keyValue passed in. If it matches, the ref count in the entry is
|
|
bumped and the address is returned.
|
|
|
|
If there are duplicate entries then the ptr to the nth oldest duplicate is
|
|
returned where n is supplied by DupIndex. A value of 0 for DupIndex means
|
|
return the last duplicate in the list. This is the most recent duplicate
|
|
inserted since insert puts new entries at the end of the duplicate group. A
|
|
value of one returns the oldest duplicate as determined by time of insert.
|
|
|
|
|
|
TBI -
|
|
If the row is locked and WaitIfLocked is TRUE then we wait on the row event.
|
|
If the row is locked and WaitIfLocked is FALSE then return status
|
|
GHT_STATUS_LOCKCONFLICT. In this case you can't tell if the entry is in
|
|
the table.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
pKeyValue -- ptr to the keyValue we are looking for.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
RetHashEntry -- Returned ptr if found or NULL.
|
|
DupIndex -- return the nth duplicate, if 0 return last duplicate in list.
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_NOT_FOUND -- if not found.
|
|
GHT_STATUS_SUCCESS -- if found.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtLookup2:"
|
|
|
|
ULONG GStatus;
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
PGENERIC_HASH_ENTRY_HEADER LastFoundpE = NULL;
|
|
|
|
// Note: Get lock earlier if table resize support is added.
|
|
|
|
if (pKeyValue == NULL) {
|
|
*RetHashEntry = NULL;
|
|
return GHT_STATUS_NOT_FOUND;
|
|
}
|
|
//
|
|
// Compute the hash index and calculate the row pointer.
|
|
//
|
|
Hval = (HashTable->GhtHashCalc)(pKeyValue, HashTable->KeyLength);
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
if (FrsRtlCountList(&RowEntry->HashRow) == 0) {
|
|
*RetHashEntry = NULL;
|
|
RowEntry->RowLookupFails += 1;
|
|
return GHT_STATUS_NOT_FOUND;
|
|
}
|
|
|
|
if (DupIndex == 0) {
|
|
DupIndex = 0xFFFFFFFF;
|
|
}
|
|
|
|
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
//
|
|
// Walk the list looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
ForEachListEntryLock(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
//
|
|
// The iterator pE is of type PGENERIC_HASH_ENTRY_HEADER.
|
|
//
|
|
RowEntry->RowCompares += 1;
|
|
if (Hval < pE->HashValue) {
|
|
//
|
|
// Not on the list.
|
|
//
|
|
break;
|
|
}
|
|
|
|
if (pE->HashValue == Hval) {
|
|
if ((HashTable->GhtCompare)(pKeyValue,
|
|
((PCHAR)pE) + HashTable->KeyOffset,
|
|
HashTable->KeyLength)) {
|
|
//
|
|
// Found it. Check DupIndex count.
|
|
//
|
|
RowEntry->RowLookups += 1;
|
|
LastFoundpE = pE;
|
|
if (--DupIndex == 0) {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
);
|
|
|
|
|
|
if (LastFoundpE != NULL) {
|
|
//
|
|
// Found one. Bump ref count, release the lock, return success.
|
|
//
|
|
InterlockedIncrement(&LastFoundpE->ReferenceCount);
|
|
DPRINT2(5, ":: inc ref: %08x, %d\n", LastFoundpE, LastFoundpE->ReferenceCount);
|
|
GStatus = GHT_STATUS_SUCCESS;
|
|
} else {
|
|
RowEntry->RowLookupFails += 1;
|
|
GStatus = GHT_STATUS_NOT_FOUND;
|
|
}
|
|
|
|
ReleaseListLock(&RowEntry->HashRow);
|
|
*RetHashEntry = LastFoundpE;
|
|
return GStatus;
|
|
}
|
|
|
|
|
|
|
|
GHT_STATUS
|
|
GhtInsert(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID HashEntryArg,
|
|
BOOL WaitIfLocked,
|
|
BOOL DuplicatesOk
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Inserts a HashEntry into the HashTable. It calls the hash function with a ptr
|
|
to the key data (HashEntry+key offset) which returns a ULONG that is stored in
|
|
HashEntry.HashValue. Insert then calculates the index of HashValue Mod
|
|
TableLenth. With the index it finds the hash row header and acquires the row
|
|
lock. It then walks the list looking for a hash value match. The entires are
|
|
kept in ascending order so the lookup stops as soon as new entry value is < the
|
|
list entry value. It then inserts the entry in the table, updates the counts in
|
|
the row header, releases the lock and returns. If it finds a match it calls the
|
|
user compare function with HashEntry+offset and ListEntry+offset to validate the
|
|
match. The validate returns true if it matches and false if it fails (i.e.
|
|
continue walking the list). Duplicates are allowed when DuplicatesOk is True.
|
|
Insert returns GHT_STATUS_SUCCESS if the entry was inserted and
|
|
GHT_STATUS_FAILURE if this is a duplicate node and DuplicatesOk is False (the
|
|
compare function returned TRUE). The refcount is incremented if the node was
|
|
inserted.
|
|
|
|
|
|
Note: All hash entries must be prefixed with GENERIC_HASH_ROW_ENTRY at the
|
|
beginning of the structure.
|
|
|
|
TBI -
|
|
If the row is locked and WaitIfLocked is FALSE then return status
|
|
GHT_STATUS_LOCKCONFLICT else wait on the row.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
HashEntryArg -- ptr to new entry to insert.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
DuplicatesOk -- True means duplicate entries are ok. They are placed at
|
|
the end of the list of duplicates.
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_FAILURE -- Conflicting entry is in table already.
|
|
GHT_STATUS_SUCCESS -- Insert was successful.
|
|
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtInsert:"
|
|
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
PVOID pKeyValue;
|
|
PLIST_ENTRY BeforeEntry;
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry =
|
|
(PGENERIC_HASH_ENTRY_HEADER)HashEntryArg;
|
|
|
|
|
|
//
|
|
// Compute the hash value on the key in the entry.
|
|
//
|
|
pKeyValue = ((PCHAR)HashEntry) + HashTable->KeyOffset;
|
|
Hval = (HashTable->GhtHashCalc)(pKeyValue, HashTable->KeyLength);
|
|
HashEntry->HashValue = Hval;
|
|
|
|
//
|
|
// Compute the index and calculate the row pointer.
|
|
//
|
|
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
|
|
BeforeEntry = &RowEntry->HashRow.ListHead; // incase of empty list.
|
|
|
|
//
|
|
// Walk the list with the lock looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
ForEachListEntryLock(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
|
|
RowEntry->RowCompares += 1;
|
|
if (Hval < pE->HashValue) {
|
|
//
|
|
// Not on the list. Put new entry before this one.
|
|
//
|
|
BeforeEntry = &pE->ListEntry;
|
|
break;
|
|
}
|
|
|
|
if (pE->HashValue == Hval) {
|
|
if ((HashTable->GhtCompare)(pKeyValue,
|
|
((PCHAR)pE) + HashTable->KeyOffset,
|
|
HashTable->KeyLength)) {
|
|
//
|
|
// Found it. Release the lock and return failure if no
|
|
// duplicates are allowed.
|
|
//
|
|
if (!DuplicatesOk) {
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
}
|
|
}
|
|
);
|
|
|
|
//
|
|
// Put new entry on the list in front of 'BeforeEntry'.
|
|
//
|
|
InterlockedIncrement(&HashEntry->ReferenceCount);
|
|
DPRINT2(5, ":: inc ref: %08x, %d\n", HashEntry, HashEntry->ReferenceCount);
|
|
RowEntry->RowInserts += 1;
|
|
|
|
FrsRtlInsertBeforeEntryListLock( &RowEntry->HashRow,
|
|
BeforeEntry,
|
|
&HashEntry->ListEntry);
|
|
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_SUCCESS;
|
|
|
|
}
|
|
|
|
|
|
GHT_STATUS
|
|
GhtDeleteEntryByAddress(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID HashEntryArg,
|
|
BOOL WaitIfLocked
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Takes HashEntry address and fetches the hash value to acquire the row lock.
|
|
Decrement the reference count and if it is one (the count for being in the
|
|
table) remove the entry from the row and call the memory free function to
|
|
release the entries memory. Drop the row lock. Return GHT_STATUS_SUCCESS if we
|
|
deleted the entry.
|
|
|
|
TBI -
|
|
Return GHT_STATUS_LOCKCONFLICT if we failed to get the lock and
|
|
WaitIfLocked was FALSE.
|
|
|
|
Note: This function is only safe if you have a reference on the entry otherwise
|
|
another thread could have already deleted the entry and your entry address is
|
|
pointing at freed memory.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
HashEntryArg -- ptr to entry to delete.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
|
|
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_FAILURE -- Entry was not deleted.
|
|
GHT_STATUS_SUCCESS -- Entry was deleted.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtDeleteEntryByAddress:"
|
|
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
BOOL Found;
|
|
ULONG GhtStatus;
|
|
LONG NewCount;
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry =
|
|
(PGENERIC_HASH_ENTRY_HEADER)HashEntryArg;
|
|
|
|
|
|
GhtStatus = GHT_STATUS_FAILURE;
|
|
|
|
//
|
|
// Get the hash value for the element and compute the index and RowEntry
|
|
// address. Then get the row lock.
|
|
//
|
|
Hval = HashEntry->HashValue;
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
|
|
|
|
#if DBG
|
|
//
|
|
// check if the entry is actually on the List.
|
|
//
|
|
// Walk the list with the lock looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
Found = GhtQuickCheck(HashTable, RowEntry, HashEntry, Hval) != NULL;
|
|
if (!Found) {
|
|
DPRINT4(0, "GhtDeleteEntryByAddress - entry not on list %08x, %08x, %d, %s\n",
|
|
HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"entry not on list");
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
#endif
|
|
|
|
|
|
//
|
|
// Decrement the ref count.
|
|
//
|
|
NewCount = InterlockedDecrement(&HashEntry->ReferenceCount);
|
|
DPRINT2(5, ":: dec ref: %08x, %d\n", HashEntry, HashEntry->ReferenceCount);
|
|
|
|
if (NewCount <= 0) {
|
|
DPRINT4(0, "GhtDeleteEntryByAddress - ref count equal zero: %08x, %08x, %d, %s\n",
|
|
HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"ref count <= zero");
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
|
|
if (NewCount == 1) {
|
|
//
|
|
// Ref count zero. Remove and free the entry.
|
|
//
|
|
FrsRtlRemoveEntryListLock(&RowEntry->HashRow, &HashEntry->ListEntry);
|
|
(HashTable->GhtFree)(HashTable, HashEntry);
|
|
GhtStatus = GHT_STATUS_SUCCESS;
|
|
}
|
|
|
|
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
|
|
return GhtStatus;
|
|
}
|
|
|
|
|
|
|
|
GHT_STATUS
|
|
GhtRemoveEntryByAddress(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID HashEntryArg,
|
|
BOOL WaitIfLocked
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Takes HashEntry address and fetches the hash value to acquire the row lock.
|
|
Remove the entry from the table. The reference count is decremented.
|
|
|
|
Return GHT_STATUS_SUCCESS.
|
|
|
|
TBI -
|
|
Return GHT_STATUS_LOCKCONFLICT if we failed to get the lock and
|
|
WaitIfLocked was FALSE.
|
|
|
|
Note: This function is only safe if you have a reference on the entry otherwise
|
|
another thread could have already deleted the entry and your entry address is
|
|
pointing at freed memory.
|
|
|
|
Also Note: The caller must have a lock that prevents other threads from
|
|
changing the entry. In addition removing an entry from one hash table and
|
|
inserting it on another will confuse another thread that may be accessing the
|
|
entry so the caller better be sure that no other thread assumes the hash
|
|
table can't change while it has a reference to the entry.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
HashEntryArg -- ptr to entry to delete.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
|
|
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_SUCCESS -- if the entry was removed successfully.
|
|
GHT_STATUS_FAILURE -- if the entry was not on the list.
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtRemoveEntryByAddress:"
|
|
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
BOOL Found;
|
|
LONG NewCount;
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry =
|
|
(PGENERIC_HASH_ENTRY_HEADER)HashEntryArg;
|
|
|
|
|
|
//
|
|
// Get the hash value for the element and compute the index and RowEntry
|
|
// address. Then get the row lock.
|
|
//
|
|
Hval = HashEntry->HashValue;
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
|
|
|
|
#if DBG
|
|
//
|
|
// check if the entry is actually on the List.
|
|
//
|
|
// Walk the list with the lock looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
Found = GhtQuickCheck(HashTable, RowEntry, HashEntry, Hval) != NULL;
|
|
if (!Found) {
|
|
DPRINT4(0, "GhtRemoveEntryByAddress - entry not on list %08x, %08x, %d, %s\n",
|
|
HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"entry not on list-2");
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
#endif
|
|
|
|
|
|
//
|
|
// Decrement the ref count.
|
|
//
|
|
NewCount = InterlockedDecrement(&HashEntry->ReferenceCount);
|
|
DPRINT2(5, ":: dec ref: %08x, %d\n", HashEntry, HashEntry->ReferenceCount);
|
|
|
|
if (NewCount < 0) {
|
|
DPRINT4(0, ":: ERROR- GhtRemoveEntryByAddress - ref count less than zero: %08x, %08x, %d, %s\n",
|
|
HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"ref count less than zero-2");
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
|
|
if (NewCount > 1) {
|
|
//
|
|
// Other Refs than the caller's exist. Print a warning.
|
|
//
|
|
DPRINT5(1, ":: WARNING- GhtRemoveEntryByAddress - ref count(%d) > 1: %08x, %08x, %d, %s\n",
|
|
NewCount, HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
}
|
|
|
|
FrsRtlRemoveEntryListLock(&RowEntry->HashRow, &HashEntry->ListEntry);
|
|
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
|
|
return GHT_STATUS_SUCCESS;
|
|
}
|
|
|
|
|
|
|
|
GHT_STATUS
|
|
GhtReferenceEntryByAddress(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID HashEntryArg,
|
|
BOOL WaitIfLocked
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Takes HashEntry address and fetches the hash value to acquire the row lock.
|
|
Increment the reference count. Drop the row lock.
|
|
|
|
TBI -
|
|
Return GHT_STATUS_LOCKCONFLICT if we failed to get the lock and
|
|
WaitIfLocked was FALSE.
|
|
|
|
Note: This function is only safe if you have a reference on the entry otherwise
|
|
another thread could have already deleted the entry and your entry address is
|
|
pointing at freed memory. A Lookup which gave you the address bumps the
|
|
reference count. An insert in which you kept the address does NOT bump
|
|
the reference count.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
HashEntryArg -- ptr to entry to reference.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_SUCCESS
|
|
|
|
--*/
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtReferenceEntryByAddress:"
|
|
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
BOOL Found;
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry =
|
|
(PGENERIC_HASH_ENTRY_HEADER)HashEntryArg;
|
|
|
|
//
|
|
// Get the hash value for the element and compute the index and RowEntry
|
|
// address. Then get the row lock.
|
|
//
|
|
Hval = HashEntry->HashValue;
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
|
|
|
|
#if DBG
|
|
//
|
|
// check if the entry is actually on the List.
|
|
//
|
|
// Walk the list with the lock looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
Found = GhtQuickCheck(HashTable, RowEntry, HashEntry, Hval) != NULL;
|
|
if (!Found) {
|
|
DPRINT4(0, "GhtReferenceEntryByAddress - entry not on list %08x, %08x, %d, %s\n",
|
|
HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"entry not on list-3");
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
#endif
|
|
|
|
|
|
//
|
|
// Increment the ref count.
|
|
//
|
|
InterlockedIncrement(&HashEntry->ReferenceCount);
|
|
DPRINT2(5, ":: inc ref: %08x, %d\n", HashEntry, HashEntry->ReferenceCount);
|
|
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
|
|
return GHT_STATUS_SUCCESS;
|
|
}
|
|
|
|
|
|
|
|
GHT_STATUS
|
|
GhtDereferenceEntryByAddress(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID HashEntryArg,
|
|
BOOL WaitIfLocked
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Takes HashEntry address and fetches the hash value to acquire the row lock.
|
|
Decrement the reference count. Drop the row lock.
|
|
|
|
TBI -
|
|
Return GHT_STATUS_LOCKCONFLICT if we failed to get the lock and
|
|
WaitIfLocked was FALSE.
|
|
|
|
Note: This function is only safe if you have a reference on the entry otherwise
|
|
another thread could have already deleted the entry and your entry address is
|
|
pointing at freed memory. A Lookup which gave you the address bumps the
|
|
reference count. An insert in which you kept the address does NOT bump
|
|
the reference count.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
HashEntryArg -- ptr to entry to reference.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_SUCCESS
|
|
|
|
--*/
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtDereferenceEntryByAddress:"
|
|
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
BOOL Found;
|
|
LONG NewCount;
|
|
PGENERIC_HASH_ENTRY_HEADER HashEntry =
|
|
(PGENERIC_HASH_ENTRY_HEADER)HashEntryArg;
|
|
|
|
|
|
//
|
|
// Get the hash value for the element and compute the index and RowEntry
|
|
// address. Then get the row lock.
|
|
//
|
|
Hval = HashEntry->HashValue;
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
|
|
|
|
#if DBG
|
|
//
|
|
// check if the entry is actually on the List.
|
|
//
|
|
// Walk the list with the lock looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
Found = GhtQuickCheck(HashTable, RowEntry, HashEntry, Hval) != NULL;
|
|
if (!Found) {
|
|
DPRINT4(0, "GhtDereferenceEntryByAddress - entry not on list %08x, %08x, %d, %s\n",
|
|
HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"entry not on list-4");
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
#endif
|
|
|
|
|
|
//
|
|
// Decrement the ref count.
|
|
//
|
|
NewCount = InterlockedDecrement(&HashEntry->ReferenceCount);
|
|
DPRINT2(5, ":: dec ref: %08x, %d\n", HashEntry, HashEntry->ReferenceCount);
|
|
|
|
if (NewCount <= 0) {
|
|
DPRINT4(0, "GhtDereferenceEntryByAddress - ref count now zero: %08x, %08x, %d, %s\n",
|
|
HashEntry, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"ref count now zero-4");
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
|
|
return GHT_STATUS_SUCCESS;
|
|
}
|
|
|
|
|
|
|
|
|
|
GHT_STATUS
|
|
GhtAdjustRefCountByKey(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID pKeyValue,
|
|
LONG Delta,
|
|
ULONG ActionIfZero,
|
|
BOOL WaitIfLocked,
|
|
PVOID *RetHashEntry
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
Takes keyvalue, finds the HashEntry address and adds Delta to
|
|
the reference count. Drop the row lock.
|
|
|
|
** WARNING **
|
|
If you allow duplicate entries in the hash table this routine will not work
|
|
because you can't guarantee that you will adjust a given entry.
|
|
|
|
TBI -
|
|
Return GHT_STATUS_LOCKCONFLICT if we failed to get the lock and
|
|
WaitIfLocked was FALSE.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
pKeyValue -- ptr to a datavalue for the key.
|
|
Delta -- The amount of the ref count adjustment.
|
|
ActionIfZero -- If RC is zero Choice of nothing, remove, remove and delete.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
RetHashEntry -- If GHT_ACTION_REMOVE requested, the hash entry
|
|
address is returned if element removed else NULL returned.
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_SUCCESS
|
|
GHT_STATUS_NOT_FOUND
|
|
|
|
--*/
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtDecrementRefCountByKey:"
|
|
|
|
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
LONG NewCount;
|
|
|
|
if (ActionIfZero == GHT_ACTION_REMOVE) {
|
|
*RetHashEntry = NULL;
|
|
}
|
|
|
|
// Note: Get lock earlier if table resize support is added.
|
|
//
|
|
// Compute the hash index and calculate the row pointer.
|
|
//
|
|
Hval = (HashTable->GhtHashCalc)(pKeyValue, HashTable->KeyLength);
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
if (FrsRtlCountList(&RowEntry->HashRow) == 0) {
|
|
RowEntry->RowLookupFails += 1;
|
|
return GHT_STATUS_NOT_FOUND;
|
|
}
|
|
|
|
//
|
|
// Walk the list with the lock looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
ForEachListEntry(&RowEntry->HashRow, GENERIC_HASH_ENTRY_HEADER, ListEntry,
|
|
//
|
|
// pE is iterator of type GENERIC_HASH_ENTRY_HEADER.
|
|
//
|
|
RowEntry->RowCompares += 1;
|
|
if (pE->HashValue == Hval) {
|
|
if ((HashTable->GhtCompare)(pKeyValue,
|
|
((PCHAR)pE) + HashTable->KeyOffset,
|
|
HashTable->KeyLength)) {
|
|
//
|
|
// Found it. Adjust ref count,
|
|
//
|
|
NewCount = InterlockedExchangeAdd(&pE->ReferenceCount, Delta);
|
|
DPRINT2(5, ":: adj ref: %08x, %d\n", pE, pE->ReferenceCount);
|
|
RowEntry->RowLookups += 1;
|
|
if (NewCount <= 0) {
|
|
if (NewCount < 0) {
|
|
DPRINT4(0, "GhtDecrementRefCountByKey - ref count neg: %08x, %08x, %d, %s\n",
|
|
pE, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"ref count neg-5");
|
|
ReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
|
|
//
|
|
// Ref count zero. Optionally remove and free the entry.
|
|
//
|
|
if (ActionIfZero == GHT_ACTION_REMOVE) {
|
|
*RetHashEntry = pE;
|
|
FrsRtlRemoveEntryListLock(&RowEntry->HashRow, &pE->ListEntry);
|
|
} else
|
|
|
|
if (ActionIfZero == GHT_ACTION_DELETE) {
|
|
(HashTable->GhtFree)(HashTable, pE);
|
|
} else {
|
|
|
|
//
|
|
// Not good. Action was noop so refcount expected to
|
|
// be > 0.
|
|
//
|
|
DPRINT4(0, "GhtDecrementRefCountByKey - ref count zero with Noop Action: %08x, %08x, %d, %s\n",
|
|
pE, Hval, HvalIndex, HashTable->Name);
|
|
FRS_ASSERT(!"ref count zero-6");
|
|
ReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_FAILURE;
|
|
}
|
|
}
|
|
|
|
ReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_SUCCESS;
|
|
}
|
|
}
|
|
);
|
|
|
|
RowEntry->RowLookupFails += 1;
|
|
return GHT_STATUS_NOT_FOUND;
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
GHT_STATUS
|
|
GhtSwapEntryByAddress(
|
|
PGENERIC_HASH_TABLE HashTable,
|
|
PVOID OldHashEntryArg,
|
|
PVOID NewHashEntryArg,
|
|
BOOL WaitIfLocked
|
|
)
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
This routine replaces an existing old hash entry with a new entry.
|
|
It verifies tha the old hash entry is still in the table.
|
|
It assumes that the key value of the new entry is the same as the old entry.
|
|
NO CHECK IS MADE.
|
|
|
|
The expected use is when the caller needs to reallocate an entry with
|
|
more storage.
|
|
|
|
NOTE ALSO: The reference count is copied from the old entry to the new one.
|
|
Using this routine means that the caller is using GhtDecrementRefCountByKey()
|
|
and GhtIncrementRefCountByKey() to access the ref counts on any element in the
|
|
table since the entry could get swapped making the pointer invalid.
|
|
|
|
TBI -
|
|
Return GHT_STATUS_LOCKCONFLICT if we failed to get the lock and
|
|
WaitIfLocked was FALSE.
|
|
|
|
Note: This function is only safe if you have a reference on the entry otherwise
|
|
another thread could have already deleted the entry and your entry address is
|
|
pointing at freed memory. A Lookup which gave you the address bumps the
|
|
reference count. An insert in which you kept the address does NOT bump
|
|
the reference count.
|
|
|
|
Arguments:
|
|
|
|
HashTable -- ptr to a GENERIC_HASH_TABLE struct.
|
|
OldHashEntry -- ptr to entry to swap out of table.
|
|
NewHashEntry -- ptr to entry to swap in to table.
|
|
WaitIfLocked -- True means wait if the row is locked.
|
|
|
|
Return Value:
|
|
|
|
GHT_STATUS_SUCCESS if swap ok.
|
|
GHT_STATUS_NOT_FOUND if old entry not in table.
|
|
|
|
|
|
--*/
|
|
// Note: TBD if necc, implement GhtIncrementRefCountByKey.
|
|
|
|
{
|
|
#undef DEBSUB
|
|
#define DEBSUB "GhtSwapEntryByAddress:"
|
|
|
|
ULONG Hval, HvalIndex;
|
|
PGENERIC_HASH_ROW_ENTRY RowEntry;
|
|
PLIST_ENTRY BeforeEntry;
|
|
BOOL Found;
|
|
PGENERIC_HASH_ENTRY_HEADER Entry;
|
|
PGENERIC_HASH_ENTRY_HEADER NewHashEntry =
|
|
(PGENERIC_HASH_ENTRY_HEADER)NewHashEntryArg;
|
|
PGENERIC_HASH_ENTRY_HEADER OldHashEntry =
|
|
(PGENERIC_HASH_ENTRY_HEADER)OldHashEntryArg;
|
|
|
|
//
|
|
// Get the hash value for the element and compute the index and RowEntry
|
|
// address. Then get the row lock.
|
|
//
|
|
Hval = OldHashEntry->HashValue;
|
|
HvalIndex = Hval % HashTable->NumberRows;
|
|
RowEntry = HashTable->HashRowBase + HvalIndex;
|
|
|
|
FrsRtlAcquireListLock(&RowEntry->HashRow);
|
|
|
|
//
|
|
// check if the entry is actually on the List.
|
|
//
|
|
// Walk the list with the lock looking for a match on the
|
|
// the hash value then try and match the KeyValue.
|
|
//
|
|
Entry = GhtQuickCheck(HashTable, RowEntry, OldHashEntry, Hval);
|
|
if (Entry != OldHashEntry) {
|
|
DPRINT4(0, "GhtSwapEntryByAddress - entry not on list %08x, %08x, %d, %s\n",
|
|
OldHashEntry, Hval, HvalIndex, HashTable->Name);
|
|
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
return GHT_STATUS_NOT_FOUND;
|
|
}
|
|
|
|
//
|
|
// Copy the ref count and hash value from the old entry to the new one.
|
|
//
|
|
NewHashEntry->ReferenceCount = OldHashEntry->ReferenceCount;
|
|
NewHashEntry->HashValue = OldHashEntry->HashValue;
|
|
|
|
//
|
|
// Pull the old entry out and replace with the new entry.
|
|
// List counts do not change so do list juggling here.
|
|
//
|
|
BeforeEntry = OldHashEntry->ListEntry.Flink;
|
|
FrsRemoveEntryList(&OldHashEntry->ListEntry);
|
|
InsertTailList(BeforeEntry, &NewHashEntry->ListEntry);
|
|
|
|
FrsRtlReleaseListLock(&RowEntry->HashRow);
|
|
|
|
return GHT_STATUS_SUCCESS;
|
|
}
|
|
|
|
|
|
|