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
49HashTable* 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
64void 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
75void 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
88static 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
104HashNode* 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
139void* 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
148void 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
178void 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
207void 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