/* */
/* */
/* */
-/* (C) 2003 Ullrich von Bassewitz */
-/* Römerstrasse 52 */
-/* D-70794 Filderstadt */
-/* EMail: uz@cc65.org */
+/* (C) 2003-2011, Ullrich von Bassewitz */
+/* Roemerstrasse 52 */
+/* D-70794 Filderstadt */
+/* EMail: uz@cc65.org */
/* */
/* */
/* This software is provided 'as-is', without any expressed or implied */
/* common */
+#include "check.h"
#include "hashtab.h"
#include "xmalloc.h"
+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 */
+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.
+ */
{
- unsigned Hash;
HashNode* N;
/* If we don't have a table, there's nothing to find */
return 0;
}
- /* Generate the hash over the index */
- Hash = T->Func->GenHash (Key);
-
/* Search for the entry in the given chain */
N = T->Table[Hash % T->Slots];
while (N) {
* if it is not really necessary.
*/
if (N->Hash == Hash &&
- T->Func->Compare (Key, T->Func->GetKey (N->Entry))) {
+ T->Func->Compare (Key, T->Func->GetKey (N)) == 0) {
/* Found */
break;
}
-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 */
{
- /* First, search for the hash node */
- HashNode* N = HT_Find (T, Key);
-
- /* Convert the node into an entry if necessary */
- return N? N->Entry : 0;
+ /* 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->Entry));
+ 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_InsertEntry (HashTable* T, void* Entry)
-/* Insert an entry into the given hash table */
+void HT_Remove (HashTable* T, void* Entry)
+/* Remove an entry from the given hash table */
{
- HT_Insert (T, T->Func->GetHashNode (Entry));
+ /* 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;
+
+ /* Remove the entry from the single linked list */
+ 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.
+ */
+ CHECK (*Q != 0);
+ if (*Q == N) {
+ /* Found - remove it */
+ *Q = N->Next;
+ --T->Count;
+ break;
+ }
+ /* Next node */
+ Q = &(*Q)->Next;
+ }
}
-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 */
- F (N->Entry, 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