PS2SDK
PS2 Homebrew Libraries
Loading...
Searching...
No Matches
hashtab.c
1/*
2--------------------------------------------------------------------
3By Bob Jenkins, 1996. hashtab.c. Public Domain.
4
5This implements a hash table.
6* Keys are unique. Adding an item fails if the key is already there.
7* Keys and items are pointed at, not copied. If you change the value
8 of the key after it is inserted then hfind will not be able to find it.
9* The hash table maintains a position that can be set and queried.
10* The table length doubles dynamically and never shrinks. The insert
11 that causes table doubling may take a long time.
12* The table length splits when the table length equals the number of items
13 Comparisons usually take 7 instructions.
14 Computing a hash value takes 35+6n instructions for an n-byte key.
15
16 hcreate - create a hash table
17 hdestroy - destroy a hash table
18 hcount - The number of items in the hash table
19 hkey - key at the current position
20 hkeyl - key length at the current position
21 hstuff - stuff at the current position
22 hfind - find an item in the table
23 hadd - insert an item into the table
24 hdel - delete an item from the table
25 hstat - print statistics about the table
26 hfirst - position at the first item in the table
27 hnext - move the position to the next item in the table
28--------------------------------------------------------------------
29*/
30
31#include <string.h>
32#include <stdlib.h>
33#include <stdint.h>
34#include <stdbool.h>
35
36#include "lookupa.h"
37#include "hashtab.h"
38#include "recycle.h"
39
40/* sanity check -- make sure ipos, apos, and count make sense */
41#ifdef HSANITY
42static void hsanity(
43 htab *t
44) {
45 uint32_t i, end, counter;
46 hitem *h;
47
48 /* test that apos makes sense */
49 end = (uint32_t)1<<(t->logsize);
50 if (end < t->apos)
51 printf("error: end %lu apos %lu\n", end, t->apos);
52
53 /* test that ipos is in bucket apos */
54 if (t->ipos)
55 {
56 for (h=t->table[t->apos]; h && h != t->ipos; h = h->next)
57 ;
58 if (h != t->ipos)
59 printf("error:ipos not in apos, apos is %lu\n", t->apos);
60 }
61
62 /* test that t->count is the number of elements in the table */
63 counter=0;
64 for (counter=0, i=0; i<end; ++i)
65 for (h=t->table[i]; h; h=h->next)
66 ++counter;
67 if (counter != t->count)
68 printf("error: counter %lu t->count %lu\n", counter, t->count);
69}
70#endif
71
72
73/*
74 * hgrow - Double the size of a hash table.
75 * Allocate a new, 2x bigger array,
76 * move everything from the old array to the new array,
77 * then free the old array.
78 */
79static void hgrow(
80 htab *t /* table */
81) {
82 register uint32_t newsize = (uint32_t)1<<(++t->logsize);
83 register uint32_t newmask = newsize-1;
84 register uint32_t i;
85 register hitem **oldtab = t->table;
86 register hitem **newtab = (hitem **)malloc(newsize*sizeof(hitem *));
87
88 /* make sure newtab is cleared */
89 for (i=0; i<newsize; ++i) newtab[i] = (hitem *)0;
90 t->table = newtab;
91 t->mask = newmask;
92
93 /* Walk through old table putting entries in new table */
94 for (i=newsize>>1; i--;)
95 {
96 register hitem *this, *that;
97 for (this = oldtab[i]; this;)
98 {
99 register hitem **newplace;
100 that = this;
101 this = this->next;
102 newplace = &newtab[(that->hval & newmask)];
103 that->next = *newplace;
104 *newplace = that;
105 }
106 }
107
108 /* position the hash table on some existing item */
109 hfirst(t);
110
111 /* free the old array */
112 free((char *)oldtab);
113}
114
115/* hcreate - create a hash table initially of size power(2,logsize) */
116htab *hcreate(
117 int logsize /* log base 2 of the size of the hash table */
118) {
119 uint32_t i,len;
120 htab *t = (htab *)malloc(sizeof(htab));
121
122 len = ((uint32_t)1<<logsize);
123 t->table = (hitem **)malloc(sizeof(hitem *)*(uint32_t)len);
124 for (i=0; i<len; ++i) t->table[i] = (hitem *)0;
125 t->logsize = logsize;
126 t->mask = len-1;
127 t->count = 0;
128 t->apos = (uint32_t)0;
129 t->ipos = (hitem *)0;
130 t->space = remkroot(sizeof(hitem));
131 t->bcount = 0;
132 return t;
133}
134
135/* hdestroy - destroy the hash table and free all its memory */
136void hdestroy(
137 htab *t /* the table */
138) {
139 refree(t->space);
140 free((char *)t->table);
141 free((char *)t);
142}
143
144/* hcount() is a macro, see hashtab.h */
145/* hkey() is a macro, see hashtab.h */
146/* hkeyl() is a macro, see hashtab.h */
147/* hstuff() is a macro, see hashtab.h */
148
149/* hfind - find an item with a given key in a hash table */
150int hfind(
151 htab *t, /* table */
152 const char *key, /* key to find */
153 size_t keyl /* key length */
154) {
155 hitem *h;
156 uint32_t x = lookup(key,keyl,0);
157 uint32_t y;
158 for (h = t->table[y=(x&t->mask)]; h; h = h->next)
159 {
160 if ((x == h->hval) &&
161 (keyl == h->keyl) &&
162 !memcmp(key, h->key, keyl))
163 {
164 t->apos = y;
165 t->ipos = h;
166 return true;
167 }
168 }
169 return false;
170}
171
172/*
173 * hadd - add an item to a hash table.
174 * return FALSE if the key is already there, otherwise TRUE.
175 */
176int hadd(
177 htab *t, /* table */
178 const char *key, /* key to add to hash table */
179 size_t keyl, /* key length */
180 void *stuff /* stuff to associate with this key */
181) {
182 register hitem *h,**hp;
183 register uint32_t y, x = lookup(key,keyl,0);
184
185 /* make sure the key is not already there */
186 for (h = t->table[(y=(x&t->mask))]; h; h = h->next)
187 {
188 if ((x == h->hval) &&
189 (keyl == h->keyl) &&
190 !memcmp(key, h->key, keyl))
191 {
192 t->apos = y;
193 t->ipos = h;
194 return false;
195 }
196 }
197
198 /* find space for a new item */
199 h = (hitem *)renew(t->space);
200
201 /* make the hash table bigger if it is getting full */
202 if (++t->count > (uint32_t)1<<(t->logsize))
203 {
204 hgrow(t);
205 y = (x&t->mask);
206 }
207
208 /* add the new key to the table */
209 h->key = key;
210 h->keyl = keyl;
211 h->stuff = stuff;
212 h->hval = x;
213 hp = &t->table[y];
214 h->next = *hp;
215 *hp = h;
216 t->ipos = h;
217 t->apos = y;
218
219#ifdef HSANITY
220 hsanity(t);
221#endif /* HSANITY */
222
223 return true;
224}
225
226/* hdel - delete the item at the current position */
227int hdel(
228 htab *t /* the hash table */
229) {
230 hitem *h; /* item being deleted */
231 hitem **ip; /* a counter */
232
233 /* check for item not existing */
234 if (!(h = t->ipos)) return false;
235
236 /* remove item from its list */
237 for (ip = &t->table[t->apos]; *ip != h; ip = &(*ip)->next)
238 ;
239 *ip = (*ip)->next;
240 --(t->count);
241
242 /* adjust position to something that exists */
243 if (!(t->ipos = h->next)) hnbucket(t);
244
245 /* recycle the deleted hitem node */
246 redel(t->space, h);
247
248#ifdef HSANITY
249 hsanity(t);
250#endif /* HSANITY */
251
252 return true;
253}
254
255/* hfirst - position on the first element in the table */
256int hfirst(
257 htab *t /* the hash table */
258) {
259 t->apos = t->mask;
260 (void)hnbucket(t);
261 return (t->ipos != (hitem *)0);
262}
263
264/* hnext() is a macro, see hashtab.h */
265
266/*
267 * hnbucket - Move position to the first item in the next bucket.
268 * Return TRUE if we did not wrap around to the beginning of the table
269 */
270int hnbucket(
271 htab *t /* hash table */
272) {
273 uint32_t oldapos = t->apos;
274 uint32_t end = (uint32_t)1<<(t->logsize);
275 uint32_t i;
276
277 /* see if the element can be found without wrapping around */
278 for (i=oldapos+1; i<end; ++i)
279 {
280 if (t->table[i&t->mask])
281 {
282 t->apos = i;
283 t->ipos = t->table[i];
284 return true;
285 }
286 }
287
288 /* must have to wrap around to find the last element */
289 for (i=0; i<=oldapos; ++i)
290 {
291 if (t->table[i])
292 {
293 t->apos = i;
294 t->ipos = t->table[i];
295 return false;
296 }
297 }
298
299 return false;
300}
301
302#ifdef HSTAT
303void hstat(
304 htab *t
305) {
306 uint32_t i,j;
307 double total = 0.0;
308 hitem *h;
309 hitem *walk, *walk2, *stat = (hitem *)0;
310
311 /* in stat, keyl will store length of list, hval the number of buckets */
312 for (i=0; i<=t->mask; ++i)
313 {
314 for (h=t->table[i], j=0; h; ++j, h=h->next)
315 ;
316 for (walk=stat; walk && (walk->keyl != j); walk=walk->next)
317 ;
318 if (walk)
319 {
320 ++(walk->hval);
321 }
322 else
323 {
324 walk = (hitem *)renew(t->space);
325 walk->keyl = j;
326 walk->hval = 1;
327 if (!stat || stat->keyl > j) {walk->next=stat; stat=walk;}
328 else
329 {
330 for (walk2=stat;
331 walk2->next && (walk2->next->keyl<j);
332 walk2=walk2->next)
333 ;
334 walk->next = walk2->next;
335 walk2->next = walk;
336 }
337 }
338 }
339
340 /* figure out average list length for existing elements */
341 for (walk=stat; walk; walk=walk->next)
342 {
343 total+=(double)walk->hval*(double)walk->keyl*(double)walk->keyl;
344 }
345 if (t->count) total /= (double)t->count;
346 else total = (double)0;
347
348 /* print statistics */
349 printf("\n");
350 for (walk=stat; walk; walk=walk->next)
351 {
352 printf("items %ld: %ld buckets\n", walk->keyl, walk->hval);
353 }
354 printf("\nbuckets: %lu items: %ld existing: %g\n\n",
355 ((uint32_t)1<<t->logsize), t->count, total);
356
357 /* clean up */
358 while (stat)
359 {
360 walk = stat->next;
361 redel(t->space, stat);
362 stat = walk;
363 }
364}
365#endif
Definition hashtab.h:54