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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |