1 /*****************************************************************************/
5 /* Generic hash table */
9 /* (C) 2003-2011, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
15 /* This software is provided 'as-is', without any expressed or implied */
16 /* warranty. In no event will the authors be held liable for any damages */
17 /* arising from the use of this software. */
19 /* Permission is granted to anyone to use this software for any purpose, */
20 /* including commercial applications, and to alter it and redistribute it */
21 /* freely, subject to the following restrictions: */
23 /* 1. The origin of this software must not be misrepresented; you must not */
24 /* claim that you wrote the original software. If you use this software */
25 /* in a product, an acknowledgment in the product documentation would be */
26 /* appreciated but is not required. */
27 /* 2. Altered source versions must be plainly marked as such, and must not */
28 /* be misrepresented as being the original software. */
29 /* 3. This notice may not be removed or altered from any source */
32 /*****************************************************************************/
43 /*****************************************************************************/
44 /* struct HashTable */
45 /*****************************************************************************/
49 HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func)
50 /* Initialize a hash table and return it */
52 /* Initialize the fields */
58 /* Return the initialized table */
64 void DoneHashTable (HashTable* T)
65 /* Destroy the contents of a hash table. Note: This will not free the entries
69 /* Just free the array with the table pointers */
75 void FreeHashTable (HashTable* T)
76 /* Free a hash table. Note: This will not free the entries in the table! */
79 /* Free the contents */
81 /* Free the table structure itself */
88 static void HT_Alloc (HashTable* T)
89 /* Allocate table memory */
94 T->Table = xmalloc (T->Slots * sizeof (T->Table[0]));
96 /* Initialize the table */
97 for (I = 0; I < T->Slots; ++I) {
104 HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash)
105 /* Find the node with the given key. Differs from HT_Find in that the hash
106 * for the key is precalculated and passed to the function.
111 /* If we don't have a table, there's nothing to find */
116 /* Search for the entry in the given chain */
117 N = T->Table[Hash % T->Slots];
120 /* First compare the full hash, to avoid calling the compare function
121 * if it is not really necessary.
123 if (N->Hash == Hash &&
124 T->Func->Compare (Key, T->Func->GetKey (N)) == 0) {
129 /* Not found, next entry */
133 /* Return what we found */
139 void* HT_Find (const HashTable* T, const void* Key)
140 /* Find the entry with the given key and return it */
142 /* Search for the entry */
143 return HT_FindHash (T, Key, T->Func->GenHash (Key));
148 void HT_Insert (HashTable* T, void* Entry)
149 /* Insert an entry into the given hash table */
154 /* If we don't have a table, we need to allocate it now */
159 /* The first member of Entry is also the hash node */
162 /* Generate the hash over the node key. */
163 N->Hash = T->Func->GenHash (T->Func->GetKey (N));
165 /* Calculate the reduced hash */
166 RHash = N->Hash % T->Slots;
168 /* Insert the entry into the correct chain */
169 N->Next = T->Table[RHash];
178 void HT_Remove (HashTable* T, void* Entry)
179 /* Remove an entry from the given hash table */
181 /* The first member of Entry is also the hash node */
184 /* Calculate the reduced hash, which is also the slot number */
185 unsigned Slot = N->Hash % T->Slots;
187 /* Remove the entry from the single linked list */
188 HashNode** Q = &T->Table[Slot];
190 /* If the pointer is NULL, the node is not in the table which we will
191 * consider a serious error.
195 /* Found - remove it */
207 void HT_Walk (HashTable* T, int (*F) (void* Entry, void* Data), void* Data)
208 /* Walk over all nodes of a hash table, optionally deleting entries from the
209 * table. For each node, the user supplied function F is called, passing a
210 * pointer to the entry, and the data pointer passed to HT_Walk by the caller.
211 * If F returns true, the node is deleted from the hash table otherwise it's
212 * left in place. While deleting the node, the node is not accessed, so it is
213 * safe for F to free the memory associcated with the entry.
218 /* If we don't have a table there are no entries to walk over */
223 /* Walk over all chains */
224 for (I = 0; I < T->Slots; ++I) {
226 /* Get the pointer to the first entry of the hash chain */
227 HashNode** Cur = &T->Table[I];
229 /* Walk over all entries in this chain */
231 /* Fetch the next node in chain now, because F() may delete it */
232 HashNode* Next = (*Cur)->Next;
233 /* Call the user function. N is also the pointer to the entry. If
234 * the function returns true, the entry is to be deleted.
236 if (F (*Cur, Data)) {
237 /* Delete the node from the chain */
241 /* Next node in chain */