1/* ----------------------------------------------------------------------------- 2 * hash.c 3 * 4 * Implements a simple hash table object. 5 * 6 * Author(s) : David Beazley (beazley@cs.uchicago.edu) 7 * 8 * Copyright (C) 1999-2000. The University of Chicago 9 * See the file LICENSE for information on usage and redistribution. 10 * ----------------------------------------------------------------------------- */ 11 12char cvsroot_hash_c[] = "$Id: hash.c 10926 2008-11-11 22:17:40Z wsfulton $"; 13 14#include "dohint.h" 15 16extern DohObjInfo DohHashType; 17 18/* Hash node */ 19typedef struct HashNode { 20 DOH *key; 21 DOH *object; 22 struct HashNode *next; 23} HashNode; 24 25/* Hash object */ 26typedef struct Hash { 27 DOH *file; 28 int line; 29 HashNode **hashtable; 30 int hashsize; 31 int nitems; 32} Hash; 33 34/* Key interning structure */ 35typedef struct KeyValue { 36 char *cstr; 37 DOH *sstr; 38 struct KeyValue *left; 39 struct KeyValue *right; 40} KeyValue; 41 42static KeyValue *root = 0; 43 44/* Find or create a key in the interned key table */ 45static DOH *find_key(DOH *doh_c) { 46 char *c = (char *) doh_c; 47 KeyValue *r, *s; 48 int d = 0; 49 /* OK, sure, we use a binary tree for maintaining interned 50 symbols. Then we use their hash values for accessing secondary 51 hash tables. */ 52 r = root; 53 s = 0; 54 while (r) { 55 s = r; 56 d = strcmp(r->cstr, c); 57 if (d == 0) 58 return r->sstr; 59 if (d < 0) 60 r = r->left; 61 else 62 r = r->right; 63 } 64 /* fprintf(stderr,"Interning '%s'\n", c); */ 65 r = (KeyValue *) DohMalloc(sizeof(KeyValue)); 66 r->cstr = (char *) DohMalloc(strlen(c) + 1); 67 strcpy(r->cstr, c); 68 r->sstr = NewString(c); 69 DohIntern(r->sstr); 70 r->left = 0; 71 r->right = 0; 72 if (!s) { 73 root = r; 74 } else { 75 if (d < 0) 76 s->left = r; 77 else 78 s->right = r; 79 } 80 return r->sstr; 81} 82 83#define HASH_INIT_SIZE 7 84 85/* Create a new hash node */ 86static HashNode *NewNode(DOH *k, void *obj) { 87 HashNode *hn = (HashNode *) DohMalloc(sizeof(HashNode)); 88 hn->key = k; 89 Incref(hn->key); 90 hn->object = obj; 91 Incref(obj); 92 hn->next = 0; 93 return hn; 94} 95 96/* Delete a hash node */ 97static void DelNode(HashNode *hn) { 98 Delete(hn->key); 99 Delete(hn->object); 100 DohFree(hn); 101} 102 103/* ----------------------------------------------------------------------------- 104 * DelHash() 105 * 106 * Delete a hash table. 107 * ----------------------------------------------------------------------------- */ 108 109static void DelHash(DOH *ho) { 110 Hash *h = (Hash *) ObjData(ho); 111 HashNode *n, *next; 112 int i; 113 114 for (i = 0; i < h->hashsize; i++) { 115 n = h->hashtable[i]; 116 while (n) { 117 next = n->next; 118 DelNode(n); 119 n = next; 120 } 121 } 122 DohFree(h->hashtable); 123 h->hashtable = 0; 124 h->hashsize = 0; 125 DohFree(h); 126} 127 128/* ----------------------------------------------------------------------------- 129 * Hash_clear() 130 * 131 * Clear all of the entries in the hash table. 132 * ----------------------------------------------------------------------------- */ 133 134static void Hash_clear(DOH *ho) { 135 Hash *h = (Hash *) ObjData(ho); 136 HashNode *n, *next; 137 int i; 138 139 for (i = 0; i < h->hashsize; i++) { 140 n = h->hashtable[i]; 141 while (n) { 142 next = n->next; 143 DelNode(n); 144 n = next; 145 } 146 h->hashtable[i] = 0; 147 } 148 h->nitems = 0; 149} 150 151/* resize the hash table */ 152static void resize(Hash *h) { 153 HashNode *n, *next, **table; 154 int oldsize, newsize; 155 int i, p, hv; 156 157 if (h->nitems < 2 * h->hashsize) 158 return; 159 160 /* Too big. We have to rescale everything now */ 161 oldsize = h->hashsize; 162 163 /* Calculate a new size */ 164 newsize = 2 * oldsize + 1; 165 p = 3; 166 while (p < (newsize >> 1)) { 167 if (((newsize / p) * p) == newsize) { 168 newsize += 2; 169 p = 3; 170 continue; 171 } 172 p = p + 2; 173 } 174 175 table = (HashNode **) DohMalloc(newsize * sizeof(HashNode *)); 176 for (i = 0; i < newsize; i++) { 177 table[i] = 0; 178 } 179 180 /* Walk down the old set of nodes and re-place */ 181 h->hashsize = newsize; 182 for (i = 0; i < oldsize; i++) { 183 n = h->hashtable[i]; 184 while (n) { 185 hv = Hashval(n->key) % newsize; 186 next = n->next; 187 n->next = table[hv]; 188 table[hv] = n; 189 n = next; 190 } 191 } 192 DohFree(h->hashtable); 193 h->hashtable = table; 194} 195 196/* ----------------------------------------------------------------------------- 197 * Hash_setattr() 198 * 199 * Set an attribute in the hash table. Deletes the existing entry if it already 200 * exists. 201 * ----------------------------------------------------------------------------- */ 202 203static int Hash_setattr(DOH *ho, DOH *k, DOH *obj) { 204 int hv; 205 HashNode *n, *prev; 206 Hash *h = (Hash *) ObjData(ho); 207 208 if (!obj) { 209 return DohDelattr(ho, k); 210 } 211 if (!DohCheck(k)) 212 k = find_key(k); 213 if (!DohCheck(obj)) { 214 obj = NewString((char *) obj); 215 Decref(obj); 216 } 217 hv = (Hashval(k)) % h->hashsize; 218 n = h->hashtable[hv]; 219 prev = 0; 220 while (n) { 221 if (Cmp(n->key, k) == 0) { 222 /* Node already exists. Just replace its contents */ 223 if (n->object == obj) { 224 /* Whoa. Same object. Do nothing */ 225 return 1; 226 } 227 Delete(n->object); 228 n->object = obj; 229 Incref(obj); 230 return 1; /* Return 1 to indicate a replacement */ 231 } else { 232 prev = n; 233 n = n->next; 234 } 235 } 236 /* Add this to the table */ 237 n = NewNode(k, obj); 238 if (prev) 239 prev->next = n; 240 else 241 h->hashtable[hv] = n; 242 h->nitems++; 243 resize(h); 244 return 0; 245} 246 247/* ----------------------------------------------------------------------------- 248 * Hash_getattr() 249 * 250 * Get an attribute from the hash table. Returns 0 if it doesn't exist. 251 * ----------------------------------------------------------------------------- */ 252typedef int (*binop) (DOH *obj1, DOH *obj2); 253 254 255static DOH *Hash_getattr(DOH *h, DOH *k) { 256 DOH *obj = 0; 257 Hash *ho = (Hash *) ObjData(h); 258 DOH *ko = DohCheck(k) ? k : find_key(k); 259 int hv = Hashval(ko) % ho->hashsize; 260 DohObjInfo *k_type = ((DohBase*)ko)->type; 261 HashNode *n = ho->hashtable[hv]; 262 if (k_type->doh_equal) { 263 binop equal = k_type->doh_equal; 264 while (n) { 265 DohBase *nk = (DohBase *)n->key; 266 if ((k_type == nk->type) && equal(ko, nk)) obj = n->object; 267 n = n->next; 268 } 269 } else { 270 binop cmp = k_type->doh_cmp; 271 while (n) { 272 DohBase *nk = (DohBase *)n->key; 273 if ((k_type == nk->type) && (cmp(ko, nk) == 0)) obj = n->object; 274 n = n->next; 275 } 276 } 277 return obj; 278} 279 280/* ----------------------------------------------------------------------------- 281 * Hash_delattr() 282 * 283 * Delete an object from the hash table. 284 * ----------------------------------------------------------------------------- */ 285 286static int Hash_delattr(DOH *ho, DOH *k) { 287 HashNode *n, *prev; 288 int hv; 289 Hash *h = (Hash *) ObjData(ho); 290 291 if (!DohCheck(k)) 292 k = find_key(k); 293 hv = Hashval(k) % h->hashsize; 294 n = h->hashtable[hv]; 295 prev = 0; 296 while (n) { 297 if (Cmp(n->key, k) == 0) { 298 /* Found it, kill it */ 299 300 if (prev) { 301 prev->next = n->next; 302 } else { 303 h->hashtable[hv] = n->next; 304 } 305 DelNode(n); 306 h->nitems--; 307 return 1; 308 } 309 prev = n; 310 n = n->next; 311 } 312 return 0; 313} 314 315static DohIterator Hash_firstiter(DOH *ho) { 316 DohIterator iter; 317 Hash *h = (Hash *) ObjData(ho); 318 iter.object = ho; 319 iter._current = 0; 320 iter.item = 0; 321 iter.key = 0; 322 iter._index = 0; /* Index in hash table */ 323 while ((iter._index < h->hashsize) && !h->hashtable[iter._index]) 324 iter._index++; 325 326 if (iter._index >= h->hashsize) { 327 return iter; 328 } 329 iter._current = h->hashtable[iter._index]; 330 iter.item = ((HashNode *) iter._current)->object; 331 iter.key = ((HashNode *) iter._current)->key; 332 333 /* Actually save the next slot in the hash. This makes it possible to 334 delete the item being iterated over without trashing the universe */ 335 iter._current = ((HashNode *) iter._current)->next; 336 return iter; 337} 338 339static DohIterator Hash_nextiter(DohIterator iter) { 340 Hash *h = (Hash *) ObjData(iter.object); 341 if (!iter._current) { 342 iter._index++; 343 while ((iter._index < h->hashsize) && !h->hashtable[iter._index]) { 344 iter._index++; 345 } 346 if (iter._index >= h->hashsize) { 347 iter.item = 0; 348 iter.key = 0; 349 iter._current = 0; 350 return iter; 351 } 352 iter._current = h->hashtable[iter._index]; 353 } 354 iter.key = ((HashNode *) iter._current)->key; 355 iter.item = ((HashNode *) iter._current)->object; 356 357 /* Store the next node to iterator on */ 358 iter._current = ((HashNode *) iter._current)->next; 359 return iter; 360} 361 362/* ----------------------------------------------------------------------------- 363 * Hash_keys(DOH *) 364 * 365 * Return a list of keys 366 * ----------------------------------------------------------------------------- */ 367 368static DOH *Hash_keys(DOH *so) { 369 DOH *keys; 370 Iterator i; 371 372 keys = NewList(); 373 for (i = First(so); i.key; i = Next(i)) { 374 Append(keys, i.key); 375 } 376 return keys; 377} 378 379/* ----------------------------------------------------------------------------- 380 * Hash_str() 381 * 382 * Create a string representation of a hash table (mainly for debugging). 383 * ----------------------------------------------------------------------------- */ 384 385static DOH *Hash_str(DOH *ho) { 386 int i, j; 387 HashNode *n; 388 DOH *s; 389 static int indent = 4; 390 Hash *h = (Hash *) ObjData(ho); 391 392 s = NewStringEmpty(); 393 if (ObjGetMark(ho)) { 394 Printf(s, "Hash(0x%x)", ho); 395 return s; 396 } 397 ObjSetMark(ho, 1); 398 Printf(s, "Hash {\n"); 399 for (i = 0; i < h->hashsize; i++) { 400 n = h->hashtable[i]; 401 while (n) { 402 for (j = 0; j < indent; j++) 403 Putc(' ', s); 404 indent += 4; 405 Printf(s, "'%s' : %s, \n", n->key, n->object); 406 indent -= 4; 407 n = n->next; 408 } 409 } 410 for (j = 0; j < (indent - 4); j++) 411 Putc(' ', s); 412 Printf(s, "}\n"); 413 ObjSetMark(ho, 0); 414 return s; 415} 416 417/* ----------------------------------------------------------------------------- 418 * Hash_len() 419 * 420 * Return number of entries in the hash table. 421 * ----------------------------------------------------------------------------- */ 422 423static int Hash_len(DOH *ho) { 424 Hash *h = (Hash *) ObjData(ho); 425 return h->nitems; 426} 427 428/* ----------------------------------------------------------------------------- 429 * CopyHash() 430 * 431 * Make a copy of a hash table. Note: this is a shallow copy. 432 * ----------------------------------------------------------------------------- */ 433 434static DOH *CopyHash(DOH *ho) { 435 Hash *h, *nh; 436 HashNode *n; 437 DOH *nho; 438 439 int i; 440 h = (Hash *) ObjData(ho); 441 nh = (Hash *) DohMalloc(sizeof(Hash)); 442 nh->hashsize = h->hashsize; 443 nh->hashtable = (HashNode **) DohMalloc(nh->hashsize * sizeof(HashNode *)); 444 for (i = 0; i < nh->hashsize; i++) { 445 nh->hashtable[i] = 0; 446 } 447 nh->nitems = 0; 448 nh->line = h->line; 449 nh->file = h->file; 450 if (nh->file) 451 Incref(nh->file); 452 453 nho = DohObjMalloc(&DohHashType, nh); 454 for (i = 0; i < h->hashsize; i++) { 455 n = h->hashtable[i]; 456 while (n) { 457 Hash_setattr(nho, n->key, n->object); 458 n = n->next; 459 } 460 } 461 return nho; 462} 463 464 465 466static void Hash_setfile(DOH *ho, DOH *file) { 467 DOH *fo; 468 Hash *h = (Hash *) ObjData(ho); 469 470 if (!DohCheck(file)) { 471 fo = NewString(file); 472 Decref(fo); 473 } else 474 fo = file; 475 Incref(fo); 476 Delete(h->file); 477 h->file = fo; 478} 479 480static DOH *Hash_getfile(DOH *ho) { 481 Hash *h = (Hash *) ObjData(ho); 482 return h->file; 483} 484 485static void Hash_setline(DOH *ho, int line) { 486 Hash *h = (Hash *) ObjData(ho); 487 h->line = line; 488} 489 490static int Hash_getline(DOH *ho) { 491 Hash *h = (Hash *) ObjData(ho); 492 return h->line; 493} 494 495/* ----------------------------------------------------------------------------- 496 * type information 497 * ----------------------------------------------------------------------------- */ 498 499static DohHashMethods HashHashMethods = { 500 Hash_getattr, 501 Hash_setattr, 502 Hash_delattr, 503 Hash_keys, 504}; 505 506DohObjInfo DohHashType = { 507 "Hash", /* objname */ 508 DelHash, /* doh_del */ 509 CopyHash, /* doh_copy */ 510 Hash_clear, /* doh_clear */ 511 Hash_str, /* doh_str */ 512 0, /* doh_data */ 513 0, /* doh_dump */ 514 Hash_len, /* doh_len */ 515 0, /* doh_hash */ 516 0, /* doh_cmp */ 517 0, /* doh_equal */ 518 Hash_firstiter, /* doh_first */ 519 Hash_nextiter, /* doh_next */ 520 Hash_setfile, /* doh_setfile */ 521 Hash_getfile, /* doh_getfile */ 522 Hash_setline, /* doh_setline */ 523 Hash_getline, /* doh_getline */ 524 &HashHashMethods, /* doh_mapping */ 525 0, /* doh_sequence */ 526 0, /* doh_file */ 527 0, /* doh_string */ 528 0, /* doh_positional */ 529 0, 530}; 531 532/* ----------------------------------------------------------------------------- 533 * NewHash() 534 * 535 * Create a new hash table. 536 * ----------------------------------------------------------------------------- */ 537 538DOH *DohNewHash(void) { 539 Hash *h; 540 int i; 541 h = (Hash *) DohMalloc(sizeof(Hash)); 542 h->hashsize = HASH_INIT_SIZE; 543 h->hashtable = (HashNode **) DohMalloc(h->hashsize * sizeof(HashNode *)); 544 for (i = 0; i < h->hashsize; i++) { 545 h->hashtable[i] = 0; 546 } 547 h->nitems = 0; 548 h->file = 0; 549 h->line = 0; 550 return DohObjMalloc(&DohHashType, h); 551} 552