1 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */ 2 3 /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */ 4 5 #ifndef NEED_TO_INCLUDE_STDIO 6 #define NEED_TO_INCLUDE_STDIO 7 #endif 8 9 #include "regint.h" 10 #include "st.h" 11 12 13 typedef struct st_table_entry st_table_entry; 14 15 struct st_table_entry { 16 unsigned int hash; 17 st_data_t key; 18 st_data_t record; 19 st_table_entry *next; 20 }; 21 22 #define ST_DEFAULT_MAX_DENSITY 5 23 #define ST_DEFAULT_INIT_TABLE_SIZE 11 24 25 /* 26 * DEFAULT_MAX_DENSITY is the default for the largest we allow the 27 * average number of items per bin before increasing the number of 28 * bins 29 * 30 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 31 * allocated initially 32 * 33 */ 34 35 static int numcmp(long, long); 36 static int numhash(long); 37 static struct st_hash_type type_numhash = { 38 numcmp, 39 numhash, 40 }; 41 42 /* extern int strcmp(const char *, const char *); */ 43 static int strhash(const char *); 44 static struct st_hash_type type_strhash = { 45 strcmp, 46 strhash, 47 }; 48 49 static void rehash(st_table *); 50 51 #define alloc(type) (type*)xmalloc((unsigned)sizeof(type)) 52 #define Calloc(n,s) (char*)xcalloc((n),(s)) 53 54 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0) 55 56 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key)) 57 #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins) 58 59 /* 60 * MINSIZE is the minimum size of a dictionary. 61 */ 62 63 #define MINSIZE 8 64 65 /* 66 Table of prime numbers 2^n+a, 2<=n<=30. 67 */ 68 static const long primes[] = { 69 8 + 3, 70 16 + 3, 71 32 + 5, 72 64 + 3, 73 128 + 3, 74 256 + 27, 75 512 + 9, 76 1024 + 9, 77 2048 + 5, 78 4096 + 3, 79 8192 + 27, 80 16384 + 43, 81 32768 + 3, 82 65536 + 45, 83 131072 + 29, 84 262144 + 3, 85 524288 + 21, 86 1048576 + 7, 87 2097152 + 17, 88 4194304 + 15, 89 8388608 + 9, 90 16777216 + 43, 91 33554432 + 35, 92 67108864 + 15, 93 134217728 + 29, 94 268435456 + 3, 95 536870912 + 11, 96 1073741824 + 85, 97 0 98 }; 99 100 static int 101 new_size(size) 102 int size; 103 { 104 int i; 105 106 #if 0 107 for (i=3; i<31; i++) { 108 if ((1<<i) > size) return 1<<i; 109 } 110 return -1; 111 #else 112 int newsize; 113 114 for (i = 0, newsize = MINSIZE; 115 i < (int )(sizeof(primes)/sizeof(primes[0])); 116 i++, newsize <<= 1) { 117 if (newsize > size) return primes[i]; 118 } 119 /* Ran out of polynomials */ 120 return -1; /* should raise exception */ 121 #endif 122 } 123 124 #ifdef HASH_LOG 125 static int collision = 0; 126 static int init_st = 0; 127 128 static void 129 stat_col(void) 130 { 131 FILE *f = fopen("/tmp/col", "w"); 132 if (f == 0) return ; 133 134 (void) fprintf(f, "collision: %d\n", collision); 135 (void) fclose(f); 136 } 137 #endif 138 139 st_table* 140 st_init_table_with_size(type, size) 141 struct st_hash_type *type; 142 int size; 143 { 144 st_table *tbl; 145 146 #ifdef HASH_LOG 147 if (init_st == 0) { 148 init_st = 1; 149 atexit(stat_col); 150 } 151 #endif 152 153 size = new_size(size); /* round up to prime number */ 154 if (size <= 0) return 0; 155 156 tbl = alloc(st_table); 157 if (tbl == 0) return 0; 158 159 tbl->type = type; 160 tbl->num_entries = 0; 161 tbl->num_bins = size; 162 tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); 163 if (tbl->bins == 0) { 164 free(tbl); 165 return 0; 166 } 167 168 return tbl; 169 } 170 171 st_table* 172 st_init_table(type) 173 struct st_hash_type *type; 174 { 175 return st_init_table_with_size(type, 0); 176 } 177 178 st_table* 179 st_init_numtable(void) 180 { 181 return st_init_table(&type_numhash); 182 } 183 184 st_table* 185 st_init_numtable_with_size(size) 186 int size; 187 { 188 return st_init_table_with_size(&type_numhash, size); 189 } 190 191 st_table* 192 st_init_strtable(void) 193 { 194 return st_init_table(&type_strhash); 195 } 196 197 st_table* 198 st_init_strtable_with_size(size) 199 int size; 200 { 201 return st_init_table_with_size(&type_strhash, size); 202 } 203 204 void 205 st_free_table(table) 206 st_table *table; 207 { 208 register st_table_entry *ptr, *next; 209 int i; 210 211 for(i = 0; i < table->num_bins; i++) { 212 ptr = table->bins[i]; 213 while (ptr != 0) { 214 next = ptr->next; 215 free(ptr); 216 ptr = next; 217 } 218 } 219 free(table->bins); 220 free(table); 221 } 222 223 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 224 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 225 226 #ifdef HASH_LOG 227 #define COLLISION collision++ 228 #else 229 #define COLLISION 230 #endif 231 232 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 233 bin_pos = hash_val%(table)->num_bins;\ 234 ptr = (table)->bins[bin_pos];\ 235 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ 236 COLLISION;\ 237 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ 238 ptr = ptr->next;\ 239 }\ 240 ptr = ptr->next;\ 241 }\ 242 } while (0) 243 244 int 245 st_lookup(table, key, value) 246 st_table *table; 247 register st_data_t key; 248 st_data_t *value; 249 { 250 unsigned int hash_val, bin_pos; 251 register st_table_entry *ptr; 252 253 hash_val = do_hash(key, table); 254 FIND_ENTRY(table, ptr, hash_val, bin_pos); 255 256 if (ptr == 0) { 257 return 0; 258 } 259 else { 260 if (value != 0) *value = ptr->record; 261 return 1; 262 } 263 } 264 265 #define ADD_DIRECT(table, key, value, hash_val, bin_pos, ret) \ 266 do {\ 267 st_table_entry *entry;\ 268 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\ 269 rehash(table);\ 270 bin_pos = hash_val % table->num_bins;\ 271 }\ 272 entry = alloc(st_table_entry);\ 273 if (IS_NULL(entry)) return ret;\ 274 entry->hash = hash_val;\ 275 entry->key = key;\ 276 entry->record = value;\ 277 entry->next = table->bins[bin_pos];\ 278 table->bins[bin_pos] = entry;\ 279 table->num_entries++;\ 280 } while (0) 281 282 int 283 st_insert(table, key, value) 284 register st_table *table; 285 register st_data_t key; 286 st_data_t value; 287 { 288 unsigned int hash_val, bin_pos; 289 register st_table_entry *ptr; 290 291 hash_val = do_hash(key, table); 292 FIND_ENTRY(table, ptr, hash_val, bin_pos); 293 294 if (ptr == 0) { 295 ADD_DIRECT(table, key, value, hash_val, bin_pos, ONIGERR_MEMORY); 296 return 0; 297 } 298 else { 299 ptr->record = value; 300 return 1; 301 } 302 } 303 304 void 305 st_add_direct(table, key, value) 306 st_table *table; 307 st_data_t key; 308 st_data_t value; 309 { 310 unsigned int hash_val, bin_pos; 311 312 hash_val = do_hash(key, table); 313 bin_pos = hash_val % table->num_bins; 314 ADD_DIRECT(table, key, value, hash_val, bin_pos,); 315 } 316 317 static void 318 rehash(table) 319 register st_table *table; 320 { 321 register st_table_entry *ptr, *next, **new_bins; 322 int i, new_num_bins, old_num_bins; 323 unsigned int hash_val; 324 325 old_num_bins = table->num_bins; 326 new_num_bins = new_size(old_num_bins + 1); 327 if (new_num_bins <= 0) return ; 328 329 new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*)); 330 if (new_bins == 0) { 331 return ; 332 } 333 334 for(i = 0; i < old_num_bins; i++) { 335 ptr = table->bins[i]; 336 while (ptr != 0) { 337 next = ptr->next; 338 hash_val = ptr->hash % new_num_bins; 339 ptr->next = new_bins[hash_val]; 340 new_bins[hash_val] = ptr; 341 ptr = next; 342 } 343 } 344 free(table->bins); 345 table->num_bins = new_num_bins; 346 table->bins = new_bins; 347 } 348 349 st_table* 350 st_copy(old_table) 351 st_table *old_table; 352 { 353 st_table *new_table; 354 st_table_entry *ptr, *entry; 355 int i, num_bins = old_table->num_bins; 356 357 new_table = alloc(st_table); 358 if (new_table == 0) { 359 return 0; 360 } 361 362 *new_table = *old_table; 363 new_table->bins = (st_table_entry**) 364 Calloc((unsigned)num_bins, sizeof(st_table_entry*)); 365 366 if (new_table->bins == 0) { 367 free(new_table); 368 return 0; 369 } 370 371 for(i = 0; i < num_bins; i++) { 372 new_table->bins[i] = 0; 373 ptr = old_table->bins[i]; 374 while (ptr != 0) { 375 entry = alloc(st_table_entry); 376 if (entry == 0) { 377 free(new_table->bins); 378 free(new_table); 379 return 0; 380 } 381 *entry = *ptr; 382 entry->next = new_table->bins[i]; 383 new_table->bins[i] = entry; 384 ptr = ptr->next; 385 } 386 } 387 return new_table; 388 } 389 390 int 391 st_delete(table, key, value) 392 register st_table *table; 393 register st_data_t *key; 394 st_data_t *value; 395 { 396 unsigned int hash_val; 397 st_table_entry *tmp; 398 register st_table_entry *ptr; 399 400 hash_val = do_hash_bin(*key, table); 401 ptr = table->bins[hash_val]; 402 403 if (ptr == 0) { 404 if (value != 0) *value = 0; 405 return 0; 406 } 407 408 if (EQUAL(table, *key, ptr->key)) { 409 table->bins[hash_val] = ptr->next; 410 table->num_entries--; 411 if (value != 0) *value = ptr->record; 412 *key = ptr->key; 413 free(ptr); 414 return 1; 415 } 416 417 for(; ptr->next != 0; ptr = ptr->next) { 418 if (EQUAL(table, ptr->next->key, *key)) { 419 tmp = ptr->next; 420 ptr->next = ptr->next->next; 421 table->num_entries--; 422 if (value != 0) *value = tmp->record; 423 *key = tmp->key; 424 free(tmp); 425 return 1; 426 } 427 } 428 429 return 0; 430 } 431 432 int 433 st_delete_safe(table, key, value, never) 434 register st_table *table; 435 register st_data_t *key; 436 st_data_t *value; 437 st_data_t never; 438 { 439 unsigned int hash_val; 440 register st_table_entry *ptr; 441 442 hash_val = do_hash_bin(*key, table); 443 ptr = table->bins[hash_val]; 444 445 if (ptr == 0) { 446 if (value != 0) *value = 0; 447 return 0; 448 } 449 450 for(; ptr != 0; ptr = ptr->next) { 451 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 452 table->num_entries--; 453 *key = ptr->key; 454 if (value != 0) *value = ptr->record; 455 ptr->key = ptr->record = never; 456 return 1; 457 } 458 } 459 460 return 0; 461 } 462 463 static int 464 #if defined(__GNUC__) 465 delete_never(st_data_t key __attribute__ ((unused)), st_data_t value, 466 st_data_t never) 467 #else 468 delete_never(key, value, never) 469 st_data_t key, value, never; 470 #endif 471 { 472 if (value == never) return ST_DELETE; 473 return ST_CONTINUE; 474 } 475 476 void 477 st_cleanup_safe(table, never) 478 st_table *table; 479 st_data_t never; 480 { 481 int num_entries = table->num_entries; 482 483 st_foreach(table, delete_never, never); 484 table->num_entries = num_entries; 485 } 486 487 int 488 st_foreach(table, func, arg) 489 st_table *table; 490 int (*func)(); 491 st_data_t arg; 492 { 493 st_table_entry *ptr, *last, *tmp; 494 enum st_retval retval; 495 int i; 496 497 for(i = 0; i < table->num_bins; i++) { 498 last = 0; 499 for(ptr = table->bins[i]; ptr != 0;) { 500 retval = (*func)(ptr->key, ptr->record, arg); 501 switch (retval) { 502 case ST_CHECK: /* check if hash is modified during iteration */ 503 tmp = 0; 504 if (i < table->num_bins) { 505 for (tmp = table->bins[i]; tmp; tmp=tmp->next) { 506 if (tmp == ptr) break; 507 } 508 } 509 if (!tmp) { 510 /* call func with error notice */ 511 return 1; 512 } 513 /* fall through */ 514 case ST_CONTINUE: 515 last = ptr; 516 ptr = ptr->next; 517 break; 518 case ST_STOP: 519 return 0; 520 case ST_DELETE: 521 tmp = ptr; 522 if (last == 0) { 523 table->bins[i] = ptr->next; 524 } 525 else { 526 last->next = ptr->next; 527 } 528 ptr = ptr->next; 529 free(tmp); 530 table->num_entries--; 531 } 532 } 533 } 534 return 0; 535 } 536 537 static int 538 strhash(string) 539 register const char *string; 540 { 541 register int c; 542 543 #ifdef HASH_ELFHASH 544 register unsigned int h = 0, g; 545 546 while ((c = *string++) != '\0') { 547 h = ( h << 4 ) + c; 548 if ( g = h & 0xF0000000 ) 549 h ^= g >> 24; 550 h &= ~g; 551 } 552 return h; 553 #elif HASH_PERL 554 register int val = 0; 555 556 while ((c = *string++) != '\0') { 557 val += c; 558 val += (val << 10); 559 val ^= (val >> 6); 560 } 561 val += (val << 3); 562 val ^= (val >> 11); 563 564 return val + (val << 15); 565 #else 566 register int val = 0; 567 568 while ((c = *string++) != '\0') { 569 val = val*997 + c; 570 } 571 572 return val + (val>>5); 573 #endif 574 } 575 576 static int 577 numcmp(x, y) 578 long x, y; 579 { 580 return x != y; 581 } 582 583 static int 584 numhash(n) 585 long n; 586 { 587 return n; 588 } 589