void DoneHashTable (HashTable* T)
/* Destroy the contents of a hash table. Note: This will not free the entries
- * in the table!
- */
+** in the table!
+*/
{
/* Just free the array with the table pointers */
xfree (T->Table);
-HashNode* HT_Find (const HashTable* T, const void* Key)
-/* Find the node with the given index */
-{
- /* If we don't have a table, there's nothing to find */
- if (T->Table == 0) {
- return 0;
- }
-
- /* Search for the entry */
- return HT_FindHash (T, Key, T->Func->GenHash (Key));
-}
-
-
-
HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash)
/* Find the node with the given key. Differs from HT_Find in that the hash
- * for the key is precalculated and passed to the function.
- */
+** for the key is precalculated and passed to the function.
+*/
{
HashNode* N;
while (N) {
/* First compare the full hash, to avoid calling the compare function
- * if it is not really necessary.
- */
+ ** if it is not really necessary.
+ */
if (N->Hash == Hash &&
T->Func->Compare (Key, T->Func->GetKey (N)) == 0) {
/* Found */
-void* HT_FindEntry (const HashTable* T, const void* Key)
-/* Find the node with the given index and return the corresponding entry */
+void* HT_Find (const HashTable* T, const void* Key)
+/* Find the entry with the given key and return it */
{
- /* Since the HashEntry must be first member, we can use HT_Find here */
- return HT_Find (T, Key);
+ /* Search for the entry */
+ return HT_FindHash (T, Key, T->Func->GenHash (Key));
}
-void HT_Insert (HashTable* T, HashNode* N)
-/* Insert a node into the given hash table */
+void HT_Insert (HashTable* T, void* Entry)
+/* Insert an entry into the given hash table */
{
+ HashNode* N;
unsigned RHash;
/* If we don't have a table, we need to allocate it now */
HT_Alloc (T);
}
+ /* The first member of Entry is also the hash node */
+ N = Entry;
+
/* Generate the hash over the node key. */
N->Hash = T->Func->GenHash (T->Func->GetKey (N));
-void HT_Remove (HashTable* T, HashNode* N)
-/* Remove a node from a hash table. */
+void HT_Remove (HashTable* T, void* Entry)
+/* Remove an entry from the given hash table */
{
+ /* The first member of Entry is also the hash node */
+ HashNode* N = Entry;
+
/* Calculate the reduced hash, which is also the slot number */
unsigned Slot = N->Hash % T->Slots;
HashNode** Q = &T->Table[Slot];
while (1) {
/* If the pointer is NULL, the node is not in the table which we will
- * consider a serious error.
- */
+ ** consider a serious error.
+ */
CHECK (*Q != 0);
if (*Q == N) {
/* Found - remove it */
*Q = N->Next;
+ --T->Count;
break;
}
/* Next node */
-void HT_InsertEntry (HashTable* T, void* Entry)
-/* Insert an entry into the given hash table */
-{
- /* Since the hash node must be first member, Entry is also the pointer to
- * the hash node.
- */
- HT_Insert (T, Entry);
-}
-
-
-
-void HT_RemoveEntry (HashTable* T, void* Entry)
-/* Remove an entry from the given hash table */
-{
- /* The entry is the first member, so we can just convert the pointer */
- HT_Remove (T, Entry);
-}
-
-
-
-void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data)
-/* Walk over all nodes of a hash table. For each node, the user supplied
- * function F is called, passing a pointer to the entry, and the data pointer
- * passed to HT_Walk by the caller.
- */
+void HT_Walk (HashTable* T, int (*F) (void* Entry, void* Data), void* Data)
+/* Walk over all nodes of a hash table, optionally deleting entries from the
+** table. For each node, the user supplied function F is called, passing a
+** pointer to the entry, and the data pointer passed to HT_Walk by the caller.
+** If F returns true, the node is deleted from the hash table otherwise it's
+** left in place. While deleting the node, the node is not accessed, so it is
+** safe for F to free the memory associcated with the entry.
+*/
{
unsigned I;
for (I = 0; I < T->Slots; ++I) {
/* Get the pointer to the first entry of the hash chain */
- HashNode* N = T->Table[I];
+ HashNode** Cur = &T->Table[I];
/* Walk over all entries in this chain */
- while (N) {
- /* Call the user function. N is also the pointer to the entry */
- F (N, Data);
- /* Next node in chain */
- N = N->Next;
+ while (*Cur) {
+ /* Fetch the next node in chain now, because F() may delete it */
+ HashNode* Next = (*Cur)->Next;
+ /* Call the user function. N is also the pointer to the entry. If
+ ** the function returns true, the entry is to be deleted.
+ */
+ if (F (*Cur, Data)) {
+ /* Delete the node from the chain */
+ *Cur = Next;
+ --T->Count;
+ } else {
+ /* Next node in chain */
+ Cur = &(*Cur)->Next;
+ }
}
-
}
}
-
-
-