Annotation of embedaddon/trafshow/hashtab.c, revision 1.1
1.1 ! misho 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