1: /*
2: --------------------------------------------------------------------
3: By Bob Jenkins, 1996. hashtab.c. Public Domain.
4:
5: This 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 <stdlib.h>
32: #include <string.h>
33:
34: #ifndef STANDARD
35: #include "standard.h"
36: #endif
37: #ifndef LOOKUPA
38: #include "lookupa.h"
39: #endif
40: #ifndef HASHTAB
41: #include "hashtab.h"
42: #endif
43: #ifndef RECYCLE
44: #include "recycle.h"
45: #endif
46:
47: #ifdef DEBUG
48: /* sanity check -- make sure ipos, apos, and count make sense */
49: static void hsanity(t)
50: htab *t;
51: {
52: ub4 i, end, counter;
53: hitem *h;
54:
55: /* test that apos makes sense */
56: end = (ub4)1<<(t->logsize);
57: if (end < t->apos)
58: fprintf(stderr, "hsanity: end %ld, apos %ld\n", end, t->apos);
59:
60: /* test that ipos is in bucket apos */
61: if (t->ipos)
62: {
63: for (h=t->table[t->apos]; h && h != t->ipos; h = h->next)
64: ;
65: if (h != t->ipos)
66: fprintf(stderr, "hsanity: ipos not in apos, apos is %ld\n", t->apos);
67: }
68:
69: /* test that t->count is the number of elements in the table */
70: counter=0;
71: for (counter=0, i=0; i<end; ++i)
72: for (h=t->table[i]; h; h=h->next)
73: ++counter;
74: if (counter != t->count)
75: fprintf(stderr, "hsanity: counter %ld, t->count %ld\n", counter, t->count);
76: }
77: #endif /* DEBUG */
78:
79:
80: /*
81: * hgrow - Double the size of a hash table.
82: * Allocate a new, 2x bigger array,
83: * move everything from the old array to the new array,
84: * then free the old array.
85: */
86: static void hgrow( t)
87: htab *t; /* table */
88: {
89: register ub4 newsize = (ub4)1<<(++t->logsize);
90: register ub4 newmask = newsize-1;
91: register ub4 i;
92: register hitem **oldtab = t->table;
93: register hitem **newtab = (hitem **)malloc(newsize*sizeof(hitem *));
94: if (!newtab) return;
95:
96: /* make sure newtab is cleared */
97: for (i=0; i<newsize; ++i) newtab[i] = (hitem *)0;
98: t->table = newtab;
99: t->mask = newmask;
100:
101: /* Walk through old table putting entries in new table */
102: for (i=newsize>>1; i--;)
103: {
104: register hitem *this, *that, **newplace;
105: for (this = oldtab[i]; this;)
106: {
107: that = this;
108: this = this->next;
109: newplace = &newtab[(that->hval & newmask)];
110: that->next = *newplace;
111: *newplace = that;
112: }
113: }
114:
115: /* position the hash table on some existing item */
116: hfirst(t);
117:
118: /* free the old array */
119: free((char *)oldtab);
120:
121: }
122:
123: /* hcreate - create a hash table initially of size power(2,logsize) */
124: htab *hcreate(logsize)
125: word logsize; /* log base 2 of the size of the hash table */
126: {
127: ub4 i,len;
128: htab *t = (htab *)malloc(sizeof(htab));
129: if (!t) return 0;
130:
131: len = ((ub4)1<<logsize);
132: t->table = (hitem **)malloc(sizeof(hitem *)*(ub4)len);
133: if (!t->table) return 0;
134: for (i=0; i<len; ++i) t->table[i] = (hitem *)0;
135: t->logsize = logsize;
136: t->mask = len-1;
137: t->count = 0;
138: t->apos = (ub4)0;
139: t->ipos = (hitem *)0;
140: t->space = remkroot(sizeof(hitem));
141: if (!t->space) return 0;
142: t->bcount = 0;
143: return t;
144: }
145:
146: /* hdestroy - destroy the hash table and free all its memory */
147: void hdestroy( t)
148: htab *t; /* the table */
149: {
150: refree(t->space);
151: free((char *)t->table);
152: free((char *)t);
153: }
154:
155: /* hcount() is a macro, see hashtab.h */
156: /* hkey() is a macro, see hashtab.h */
157: /* hkeyl() is a macro, see hashtab.h */
158: /* hstuff() is a macro, see hashtab.h */
159:
160: /* hfind - find an item with a given key in a hash table */
161: word hfind( t, key, keyl )
162: htab *t; /* table */
163: ub1 *key; /* key to find */
164: ub4 keyl; /* key length */
165: {
166: hitem *h;
167: ub4 x = lookup(key,keyl,0);
168: ub4 y;
169: for (h = t->table[y=(x&t->mask)]; h; h = h->next)
170: {
171: if ((x == h->hval) &&
172: (keyl == h->keyl) &&
173: !memcmp(key, h->key, keyl))
174: {
175: t->apos = y;
176: t->ipos = h;
177: return TRUE;
178: }
179: }
180: return FALSE;
181: }
182:
183: /*
184: * hadd - add an item to a hash table.
185: * return FALSE if the key is already there, otherwise TRUE.
186: */
187: word hadd( t, key, keyl, stuff)
188: htab *t; /* table */
189: ub1 *key; /* key to add to hash table */
190: ub4 keyl; /* key length */
191: void *stuff; /* stuff to associate with this key */
192: {
193: register hitem *h,**hp;
194: register ub4 y, x = lookup(key,keyl,0);
195:
196: /* make sure the key is not already there */
197: for (h = t->table[(y=(x&t->mask))]; h; h = h->next)
198: {
199: if ((x == h->hval) &&
200: (keyl == h->keyl) &&
201: !memcmp(key, h->key, keyl))
202: {
203: t->apos = y;
204: t->ipos = h;
205: return FALSE;
206: }
207: }
208:
209: /* find space for a new item */
210: h = (hitem *)renew(t->space);
211: if (!h) return -1;
212:
213: /* make the hash table bigger if it is getting full */
214: if (++t->count > (ub4)1<<(t->logsize))
215: {
216: hgrow(t);
217: y = (x&t->mask);
218: }
219:
220: /* add the new key to the table */
221: h->key = key;
222: h->keyl = keyl;
223: h->stuff = stuff;
224: h->hval = x;
225: hp = &t->table[y];
226: h->next = *hp;
227: *hp = h;
228: t->ipos = h;
229: t->apos = y;
230:
231: #ifdef DEBUG
232: hsanity(t);
233: #endif /* DEBUG */
234:
235: return TRUE;
236: }
237:
238: /* hdel - delete the item at the current position */
239: word hdel(t)
240: htab *t; /* the hash table */
241: {
242: hitem *h; /* item being deleted */
243: hitem **ip; /* a counter */
244:
245: /* check for item not existing */
246: if (!(h = t->ipos)) return FALSE;
247:
248: /* remove item from its list */
249: for (ip = &t->table[t->apos]; *ip != h; ip = &(*ip)->next)
250: ;
251: *ip = (*ip)->next;
252: --(t->count);
253:
254: /* adjust position to something that exists */
255: if (!(t->ipos = h->next)) hnbucket(t);
256:
257: /* recycle the deleted hitem node */
258: redel(t->space, h);
259:
260: #ifdef DEBUG
261: hsanity(t);
262: #endif /* DEBUG */
263:
264: return TRUE;
265: }
266:
267: /* hfirst - position on the first element in the table */
268: word hfirst(t)
269: htab *t; /* the hash table */
270: {
271: t->apos = t->mask;
272: (void)hnbucket(t);
273: return (t->ipos != (hitem *)0);
274: }
275:
276: /* hnext() is a macro, see hashtab.h */
277:
278: /*
279: * hnbucket - Move position to the first item in the next bucket.
280: * Return TRUE if we did not wrap around to the beginning of the table
281: */
282: word hnbucket(t)
283: htab *t;
284: {
285: ub4 oldapos = t->apos;
286: ub4 end = (ub4)1<<(t->logsize);
287: ub4 i;
288:
289: /* see if the element can be found without wrapping around */
290: for (i=oldapos+1; i<end; ++i)
291: {
292: if (t->table[i&t->mask])
293: {
294: t->apos = i;
295: t->ipos = t->table[i];
296: return TRUE;
297: }
298: }
299:
300: /* must have to wrap around to find the last element */
301: for (i=0; i<=oldapos; ++i)
302: {
303: if (t->table[i])
304: {
305: t->apos = i;
306: t->ipos = t->table[i];
307: return FALSE;
308: }
309: }
310:
311: return FALSE;
312: }
313:
314: void hstat(fp, t)
315: FILE *fp;
316: htab *t;
317: {
318: ub4 i,j;
319: double total = 0.0;
320: hitem *h;
321: hitem *walk, *walk2, *stat = (hitem *)0;
322:
323: /* in stat, keyl will store length of list, hval the number of buckets */
324: for (i=0; i<=t->mask; ++i)
325: {
326: for (h=t->table[i], j=0; h; ++j, h=h->next)
327: ;
328: for (walk=stat; walk && (walk->keyl != j); walk=walk->next)
329: ;
330: if (walk)
331: {
332: ++(walk->hval);
333: }
334: else
335: {
336: walk = (hitem *)renew(t->space);
337: if (!walk) {
338: fprintf(fp, "renew: Can't allocate memory?\n");
339: return;
340: }
341: walk->keyl = j;
342: walk->hval = 1;
343: if (!stat || stat->keyl > j) {walk->next=stat; stat=walk;}
344: else
345: {
346: for (walk2=stat;
347: walk2->next && (walk2->next->keyl<j);
348: walk2=walk2->next)
349: ;
350: walk->next = walk2->next;
351: walk2->next = walk;
352: }
353: }
354: }
355:
356: /* figure out average list length for existing elements */
357: for (walk=stat; walk; walk=walk->next)
358: {
359: total+=(double)walk->hval*(double)walk->keyl*(double)walk->keyl;
360: }
361: if (t->count) total /= (double)t->count;
362: else total = (double)0;
363:
364: /* print statistics */
365: fprintf(fp, "\n");
366: for (walk=stat; walk; walk=walk->next)
367: {
368: fprintf(fp, "items %ld: %ld buckets\n", walk->keyl, walk->hval);
369: }
370: fprintf(fp, "\nbuckets: %ld items: %ld existing: %g\n\n",
371: ((ub4)1<<t->logsize), t->count, total);
372:
373: /* clean up */
374: while (stat)
375: {
376: walk = stat->next;
377: redel(t->space, stat);
378: stat = walk;
379: }
380: }
381:
382:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hashtab.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / trafshow