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#include "config.h" 6#include <stdio.h> 7#include <stdlib.h> 8#include "syck_st.h" 9 10#ifdef NT 11#include <malloc.h> 12#endif 13 14#define SIZE32 4 15#if SIZEOF_LONG == SIZE32 16typedef long I32; 17typedef unsigned long U32; 18#define NUM2I32(x) NUM2LONG(x) 19#define NUM2U32(x) NUM2ULONG(x) 20#elif SIZEOF_INT == SIZE32 21typedef int I32; 22typedef unsigned int U32; 23#define NUM2I32(x) NUM2INT(x) 24#define NUM2U32(x) NUM2UINT(x) 25#endif 26 27typedef struct st_table_entry st_table_entry; 28 29struct st_table_entry { 30 unsigned int hash; 31 char *key; 32 char *record; 33 st_table_entry *next; 34}; 35 36#define ST_DEFAULT_MAX_DENSITY 5 37#define ST_DEFAULT_INIT_TABLE_SIZE 11 38 39 /* 40 * DEFAULT_MAX_DENSITY is the default for the largest we allow the 41 * average number of items per bin before increasing the number of 42 * bins 43 * 44 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 45 * allocated initially 46 * 47 */ 48static int numcmp(); 49static int numhash(); 50static struct st_hash_type type_numhash = { 51 numcmp, 52 numhash, 53}; 54 55extern int strcmp(); 56static int strhash(); 57static struct st_hash_type type_strhash = { 58 strcmp, 59 strhash, 60}; 61 62static void rehash(); 63 64#define alloc(type) (type*)malloc((unsigned)sizeof(type)) 65#define Calloc(n,s) (char*)calloc((n),(s)) 66 67#define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0) 68 69#define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key)) 70#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins) 71 72/* 73 * MINSIZE is the minimum size of a dictionary. 74 */ 75 76#define MINSIZE 8 77 78/* 79Table of prime numbers 2^n+a, 2<=n<=30. 80*/ 81static long primes[] = { 82 8 + 3, 83 16 + 3, 84 32 + 5, 85 64 + 3, 86 128 + 3, 87 256 + 27, 88 512 + 9, 89 1024 + 9, 90 2048 + 5, 91 4096 + 3, 92 8192 + 27, 93 16384 + 43, 94 32768 + 3, 95 65536 + 45, 96 131072 + 29, 97 262144 + 3, 98 524288 + 21, 99 1048576 + 7, 100 2097152 + 17, 101 4194304 + 15, 102 8388608 + 9, 103 16777216 + 43, 104 33554432 + 35, 105 67108864 + 15, 106 134217728 + 29, 107 268435456 + 3, 108 536870912 + 11, 109 1073741824 + 85, 110 0 111}; 112 113static int 114new_size(size) 115 int size; 116{ 117 int i; 118 119#if 0 120 for (i=3; i<31; i++) { 121 if ((1<<i) > size) return 1<<i; 122 } 123 return -1; 124#else 125 int newsize; 126 127 for (i = 0, newsize = MINSIZE; 128 i < sizeof(primes)/sizeof(primes[0]); 129 i++, newsize <<= 1) 130 { 131 if (newsize > size) return primes[i]; 132 } 133 /* Ran out of polynomials */ 134 return -1; /* should raise exception */ 135#endif 136} 137 138#ifdef HASH_LOG 139static int collision = 0; 140static int init_st = 0; 141 142static void 143stat_col() 144{ 145 FILE *f = fopen("/tmp/col", "w"); 146 fprintf(f, "collision: %d\n", collision); 147 fclose(f); 148} 149#endif 150 151st_table* 152st_init_table_with_size(type, size) 153 struct st_hash_type *type; 154 int size; 155{ 156 st_table *tbl; 157 158#ifdef HASH_LOG 159 if (init_st == 0) { 160 init_st = 1; 161 atexit(stat_col); 162 } 163#endif 164 165 size = new_size(size); /* round up to prime number */ 166 167 tbl = alloc(st_table); 168 tbl->type = type; 169 tbl->num_entries = 0; 170 tbl->num_bins = size; 171 tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); 172 173 return tbl; 174} 175 176st_table* 177st_init_table(type) 178 struct st_hash_type *type; 179{ 180 return st_init_table_with_size(type, 0); 181} 182 183st_table* 184st_init_numtable() 185{ 186 return st_init_table(&type_numhash); 187} 188 189st_table* 190st_init_numtable_with_size(size) 191 int size; 192{ 193 return st_init_table_with_size(&type_numhash, size); 194} 195 196st_table* 197st_init_strtable() 198{ 199 return st_init_table(&type_strhash); 200} 201 202st_table* 203st_init_strtable_with_size(size) 204 int size; 205{ 206 return st_init_table_with_size(&type_strhash, size); 207} 208 209void 210st_free_table(table) 211 st_table *table; 212{ 213 register st_table_entry *ptr, *next; 214 int i; 215 216 for(i = 0; i < table->num_bins; i++) { 217 ptr = table->bins[i]; 218 while (ptr != 0) { 219 next = ptr->next; 220 free(ptr); 221 ptr = next; 222 } 223 } 224 free(table->bins); 225 free(table); 226} 227 228#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 229((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 230 231#ifdef HASH_LOG 232#define COLLISION collision++ 233#else 234#define COLLISION 235#endif 236 237#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ 238 bin_pos = hash_val%(table)->num_bins;\ 239 ptr = (table)->bins[bin_pos];\ 240 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ 241 COLLISION;\ 242 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ 243 ptr = ptr->next;\ 244 }\ 245 ptr = ptr->next;\ 246 }\ 247} while (0) 248 249int 250st_lookup(table, key, value) 251 st_table *table; 252 register char *key; 253 char **value; 254{ 255 unsigned int hash_val, bin_pos; 256 register st_table_entry *ptr; 257 258 hash_val = do_hash(key, table); 259 FIND_ENTRY(table, ptr, hash_val, bin_pos); 260 261 if (ptr == 0) { 262 return 0; 263 } 264 else { 265 if (value != 0) *value = ptr->record; 266 return 1; 267 } 268} 269 270#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ 271do {\ 272 st_table_entry *entry;\ 273 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\ 274 rehash(table);\ 275 bin_pos = hash_val % table->num_bins;\ 276 }\ 277 \ 278 entry = alloc(st_table_entry);\ 279 \ 280 entry->hash = hash_val;\ 281 entry->key = key;\ 282 entry->record = value;\ 283 entry->next = table->bins[bin_pos];\ 284 table->bins[bin_pos] = entry;\ 285 table->num_entries++;\ 286} while (0) 287 288int 289st_insert(table, key, value) 290 register st_table *table; 291 register char *key; 292 char *value; 293{ 294 unsigned int hash_val, bin_pos; 295 register st_table_entry *ptr; 296 297 hash_val = do_hash(key, table); 298 FIND_ENTRY(table, ptr, hash_val, bin_pos); 299 300 if (ptr == 0) { 301 ADD_DIRECT(table, key, value, hash_val, bin_pos); 302 return 0; 303 } 304 else { 305 ptr->record = value; 306 return 1; 307 } 308} 309 310void 311st_add_direct(table, key, value) 312 st_table *table; 313 char *key; 314 char *value; 315{ 316 unsigned int hash_val, bin_pos; 317 318 hash_val = do_hash(key, table); 319 bin_pos = hash_val % table->num_bins; 320 ADD_DIRECT(table, key, value, hash_val, bin_pos); 321} 322 323static void 324rehash(table) 325 register st_table *table; 326{ 327 register st_table_entry *ptr, *next, **new_bins; 328 int i, old_num_bins = table->num_bins, new_num_bins; 329 unsigned int hash_val; 330 331 new_num_bins = new_size(old_num_bins+1); 332 new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*)); 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 349st_table* 350st_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 390int 391st_delete(table, key, value) 392 register st_table *table; 393 register char **key; 394 char **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 432int 433st_delete_safe(table, key, value, never) 434 register st_table *table; 435 register char **key; 436 char **value; 437 char *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 463static int 464delete_never(key, value, never) 465 char *key, *value, *never; 466{ 467 if (value == never) return ST_DELETE; 468 return ST_CONTINUE; 469} 470 471void 472st_cleanup_safe(table, never) 473 st_table *table; 474 char *never; 475{ 476 int num_entries = table->num_entries; 477 478 st_foreach(table, (enum st_retval (*)())delete_never, never); 479 table->num_entries = num_entries; 480} 481 482void 483st_foreach(table, func, arg) 484 st_table *table; 485 enum st_retval (*func)(); 486 char *arg; 487{ 488 st_table_entry *ptr, *last, *tmp; 489 enum st_retval retval; 490 int i; 491 492 for(i = 0; i < table->num_bins; i++) { 493 last = 0; 494 for(ptr = table->bins[i]; ptr != 0;) { 495 retval = (*func)(ptr->key, ptr->record, arg); 496 switch (retval) { 497 case ST_CONTINUE: 498 last = ptr; 499 ptr = ptr->next; 500 break; 501 case ST_STOP: 502 return; 503 case ST_DELETE: 504 tmp = ptr; 505 if (last == 0) { 506 table->bins[i] = ptr->next; 507 } 508 else { 509 last->next = ptr->next; 510 } 511 ptr = ptr->next; 512 free(tmp); 513 table->num_entries--; 514 } 515 } 516 } 517} 518 519static int 520strhash(string) 521 register char *string; 522{ 523 register int c; 524 525#ifdef HASH_ELFHASH 526 register unsigned int h = 0, g; 527 528 while ((c = *string++) != '\0') { 529 h = ( h << 4 ) + c; 530 if ( g = h & 0xF0000000 ) 531 h ^= g >> 24; 532 h &= ~g; 533 } 534 return h; 535#elif HASH_PERL 536 register int val = 0; 537 538 while ((c = *string++) != '\0') { 539 val = val*33 + c; 540 } 541 542 return val + (val>>5); 543#elif HASH_JENKINS 544 register const unsigned char *s_PeRlHaSh = (const unsigned char *)string; 545 register U32 hash_PeRlHaSh = 0; 546 while ((c = *s_PeRlHaSh++) != '\0') { 547 hash_PeRlHaSh += c; 548 hash_PeRlHaSh += (hash_PeRlHaSh << 10); 549 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); 550 } 551 hash_PeRlHaSh += (hash_PeRlHaSh << 3); 552 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); 553 return (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); 554#else 555 register int val = 0; 556 557 while ((c = *string++) != '\0') { 558 val = val*997 + c; 559 } 560 561 return val + (val>>5); 562#endif 563} 564 565static int 566numcmp(x, y) 567 long x, y; 568{ 569 return x != y; 570} 571 572static int 573numhash(n) 574 long n; 575{ 576 return n; 577} 578