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