+HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func)
+/* Initialize a hash table and return it */
+{
+ /* Initialize the fields */
+ T->Slots = Slots;
+ T->Count = 0;
+ T->Table = 0;
+ T->Func = Func;
+
+ /* Return the initialized table */
+ return T;
+}
+
+
+
+void DoneHashTable (HashTable* T)
+/* Destroy the contents of a hash table. Note: This will not free the entries
+ * in the table!
+ */
+{
+ /* Just free the array with the table pointers */
+ xfree (T->Table);
+}
+
+
+
void FreeHashTable (HashTable* T)
/* Free a hash table. Note: This will not free the entries in the 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.
-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));
-
+
/* Calculate the reduced hash */
RHash = N->Hash % T->Slots;
N->Next = T->Table[RHash];
T->Table[RHash] = N;
- /* Set the owner */
- N->Owner = T;
-
/* One more entry */
++T->Count;
}
-void HT_Remove (HashNode* N)
-/* Remove a node from a hash table. */
+void HT_Remove (HashTable* T, void* Entry)
+/* Remove an entry from the given hash table */
{
- /* Get the table from the node */
- HashTable* T = N->Owner;
+ /* 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;
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 */
- HashNode* N = Entry;
-
- /* Make sure the entry is actually in the given table */
- CHECK (N->Owner == T);
-
- /* Remove the node */
- HT_Remove (N);
-}
-
-
-
-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;
+ }
}
-
}
}
-
-
-
projects / cc65 / blobdiff