1 /*****************************************************************************/
2 /* */
3 /* hashtab.c */
4 /* */
5 /* Generic hash table */
6 /* */
7 /* */
8 /* */
9 /* (C) 2003-2011, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
13 /* */
14 /* */
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. */
18 /* */
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: */
22 /* */
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 */
30 /* distribution. */
31 /* */
32 /*****************************************************************************/
33
34
35
36 /* common */
37 #include "check.h"
38 #include "hashtab.h"
39 #include "xmalloc.h"
40
41
42
43 /*****************************************************************************/
44 /* struct HashTable */
45 /*****************************************************************************/
46
47
48
InitHashTable(HashTable * T,unsigned Slots,const HashFunctions * Func)49 HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func)
50 /* Initialize a hash table and return it */
51 {
52 /* Initialize the fields */
53 T->Slots = Slots;
54 T->Count = 0;
55 T->Table = 0;
56 T->Func = Func;
57
58 /* Return the initialized table */
59 return T;
60 }
61
62
63
DoneHashTable(HashTable * T)64 void DoneHashTable (HashTable* T)
65 /* Destroy the contents of a hash table. Note: This will not free the entries
66 ** in the table!
67 */
68 {
69 /* Just free the array with the table pointers */
70 xfree (T->Table);
71 }
72
73
74
FreeHashTable(HashTable * T)75 void FreeHashTable (HashTable* T)
76 /* Free a hash table. Note: This will not free the entries in the table! */
77 {
78 if (T) {
79 /* Free the contents */
80 DoneHashTable (T);
81 /* Free the table structure itself */
82 xfree (T);
83 }
84 }
85
86
87
HT_Alloc(HashTable * T)88 static void HT_Alloc (HashTable* T)
89 /* Allocate table memory */
90 {
91 unsigned I;
92
93 /* Allocate memory */
94 T->Table = xmalloc (T->Slots * sizeof (T->Table[0]));
95
96 /* Initialize the table */
97 for (I = 0; I < T->Slots; ++I) {
98 T->Table[I] = 0;
99 }
100 }
101
102
103
HT_FindHash(const HashTable * T,const void * Key,unsigned Hash)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.
107 */
108 {
109 HashNode* N;
110
111 /* If we don't have a table, there's nothing to find */
112 if (T->Table == 0) {
113 return 0;
114 }
115
116 /* Search for the entry in the given chain */
117 N = T->Table[Hash % T->Slots];
118 while (N) {
119
120 /* First compare the full hash, to avoid calling the compare function
121 ** if it is not really necessary.
122 */
123 if (N->Hash == Hash &&
124 T->Func->Compare (Key, T->Func->GetKey (N)) == 0) {
125 /* Found */
126 break;
127 }
128
129 /* Not found, next entry */
130 N = N->Next;
131 }
132
133 /* Return what we found */
134 return N;
135 }
136
137
138
HT_Find(const HashTable * T,const void * Key)139 void* HT_Find (const HashTable* T, const void* Key)
140 /* Find the entry with the given key and return it */
141 {
142 /* Search for the entry */
143 return HT_FindHash (T, Key, T->Func->GenHash (Key));
144 }
145
146
147
HT_Insert(HashTable * T,void * Entry)148 void HT_Insert (HashTable* T, void* Entry)
149 /* Insert an entry into the given hash table */
150 {
151 HashNode* N;
152 unsigned RHash;
153
154 /* If we don't have a table, we need to allocate it now */
155 if (T->Table == 0) {
156 HT_Alloc (T);
157 }
158
159 /* The first member of Entry is also the hash node */
160 N = Entry;
161
162 /* Generate the hash over the node key. */
163 N->Hash = T->Func->GenHash (T->Func->GetKey (N));
164
165 /* Calculate the reduced hash */
166 RHash = N->Hash % T->Slots;
167
168 /* Insert the entry into the correct chain */
169 N->Next = T->Table[RHash];
170 T->Table[RHash] = N;
171
172 /* One more entry */
173 ++T->Count;
174 }
175
176
177
HT_Remove(HashTable * T,void * Entry)178 void HT_Remove (HashTable* T, void* Entry)
179 /* Remove an entry from the given hash table */
180 {
181 /* The first member of Entry is also the hash node */
182 HashNode* N = Entry;
183
184 /* Calculate the reduced hash, which is also the slot number */
185 unsigned Slot = N->Hash % T->Slots;
186
187 /* Remove the entry from the single linked list */
188 HashNode** Q = &T->Table[Slot];
189 while (1) {
190 /* If the pointer is NULL, the node is not in the table which we will
191 ** consider a serious error.
192 */
193 CHECK (*Q != 0);
194 if (*Q == N) {
195 /* Found - remove it */
196 *Q = N->Next;
197 --T->Count;
198 break;
199 }
200 /* Next node */
201 Q = &(*Q)->Next;
202 }
203 }
204
205
206
HT_Walk(HashTable * T,int (* F)(void * Entry,void * Data),void * Data)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.
214 */
215 {
216 unsigned I;
217
218 /* If we don't have a table there are no entries to walk over */
219 if (T->Table == 0) {
220 return;
221 }
222
223 /* Walk over all chains */
224 for (I = 0; I < T->Slots; ++I) {
225
226 /* Get the pointer to the first entry of the hash chain */
227 HashNode** Cur = &T->Table[I];
228
229 /* Walk over all entries in this chain */
230 while (*Cur) {
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.
235 */
236 if (F (*Cur, Data)) {
237 /* Delete the node from the chain */
238 *Cur = Next;
239 --T->Count;
240 } else {
241 /* Next node in chain */
242 Cur = &(*Cur)->Next;
243 }
244 }
245 }
246 }
247