X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=src%2Fcommon%2Fhashtab.c;h=36a3b389c6810e1310b0ab70706a19d86cddc10a;hb=f266612697b213f2f74027eb5b2605b19a97d6d7;hp=a96dc16527465f18ffb00eb8aa79cdcd43849610;hpb=279ad0515094c36cf70f6e84b721265cedd22da8;p=cc65 diff --git a/src/common/hashtab.c b/src/common/hashtab.c index a96dc1652..36a3b389c 100644 --- a/src/common/hashtab.c +++ b/src/common/hashtab.c @@ -46,6 +46,32 @@ +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! */ { @@ -75,20 +101,6 @@ static void HT_Alloc (HashTable* T) -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. @@ -109,7 +121,7 @@ HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash) * if it is not really necessary. */ if (N->Hash == Hash && - T->Func->Compare (Key, T->Func->GetKey (HN_GetEntry (N))) == 0) { + T->Func->Compare (Key, T->Func->GetKey (N)) == 0) { /* Found */ break; } @@ -124,21 +136,19 @@ HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash) -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? HN_GetEntry (N) : 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 */ @@ -146,8 +156,11 @@ void HT_Insert (HashTable* T, HashNode* N) 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 (HN_GetEntry (N))); + N->Hash = T->Func->GenHash (T->Func->GetKey (N)); /* Calculate the reduced hash */ RHash = N->Hash % T->Slots; @@ -156,20 +169,17 @@ void HT_Insert (HashTable* T, HashNode* N) 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; @@ -184,6 +194,7 @@ void HT_Remove (HashNode* N) if (*Q == N) { /* Found - remove it */ *Q = N->Next; + --T->Count; break; } /* Next node */ @@ -193,33 +204,13 @@ void HT_Remove (HashNode* N) -void HT_InsertEntry (HashTable* T, void* Entry) -/* Insert an entry into the given hash table */ -{ - HT_Insert (T, T->Func->GetHashNode (Entry)); -} - - - -void HT_RemoveEntry (HashTable* T, void* Entry) -/* Remove an entry from the given hash table */ -{ - /* Get the node from the entry */ - HashNode* N = T->Func->GetHashNode (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; @@ -233,18 +224,23 @@ void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data) 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 (HN_GetEntry (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; + } } - } } - - -