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#ifdef NOT_RUBY 6#include "regint.h" 7#include "st.h" 8#else 9#include "ruby/ruby.h" 10#endif 11 12#include <stdio.h> 13#ifdef HAVE_STDLIB_H 14#include <stdlib.h> 15#endif 16#include <string.h> 17 18typedef struct st_table_entry st_table_entry; 19 20struct st_table_entry { 21 st_index_t hash; 22 st_data_t key; 23 st_data_t record; 24 st_table_entry *next; 25 st_table_entry *fore, *back; 26}; 27 28typedef struct st_packed_entry { 29 st_index_t hash; 30 st_data_t key, val; 31} st_packed_entry; 32 33#define STATIC_ASSERT(name, expr) typedef int static_assert_##name##_check[(expr) ? 1 : -1]; 34 35#define ST_DEFAULT_MAX_DENSITY 5 36#define ST_DEFAULT_INIT_TABLE_SIZE 11 37#define ST_DEFAULT_SECOND_TABLE_SIZE 19 38#define ST_DEFAULT_PACKED_TABLE_SIZE 18 39#define PACKED_UNIT (int)(sizeof(st_packed_entry) / sizeof(st_table_entry*)) 40#define MAX_PACKED_HASH (int)(ST_DEFAULT_PACKED_TABLE_SIZE * sizeof(st_table_entry*) / sizeof(st_packed_entry)) 41 42STATIC_ASSERT(st_packed_entry, sizeof(st_packed_entry) == sizeof(st_table_entry*[PACKED_UNIT])) 43STATIC_ASSERT(st_packed_bins, sizeof(st_packed_entry[MAX_PACKED_HASH]) <= sizeof(st_table_entry*[ST_DEFAULT_PACKED_TABLE_SIZE])) 44 45 /* 46 * DEFAULT_MAX_DENSITY is the default for the largest we allow the 47 * average number of items per bin before increasing the number of 48 * bins 49 * 50 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins 51 * allocated initially 52 * 53 */ 54 55#define type_numhash st_hashtype_num 56const struct st_hash_type st_hashtype_num = { 57 st_numcmp, 58 st_numhash, 59}; 60 61/* extern int strcmp(const char *, const char *); */ 62static st_index_t strhash(st_data_t); 63static const struct st_hash_type type_strhash = { 64 strcmp, 65 strhash, 66}; 67 68static st_index_t strcasehash(st_data_t); 69static const struct st_hash_type type_strcasehash = { 70 st_strcasecmp, 71 strcasehash, 72}; 73 74static void rehash(st_table *); 75 76#ifdef RUBY 77#define malloc xmalloc 78#define calloc xcalloc 79#define realloc xrealloc 80#define free(x) xfree(x) 81#endif 82 83#define numberof(array) (int)(sizeof(array) / sizeof((array)[0])) 84 85#define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0) 86 87#define do_hash(key,table) (st_index_t)(*(table)->type->hash)((key)) 88#define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins) 89 90/* preparation for possible allocation improvements */ 91#define st_alloc_entry() (st_table_entry *)malloc(sizeof(st_table_entry)) 92#define st_free_entry(entry) free(entry) 93#define st_alloc_table() (st_table *)malloc(sizeof(st_table)) 94#define st_dealloc_table(table) free(table) 95#define st_alloc_bins(size) (st_table_entry **)calloc(size, sizeof(st_table_entry *)) 96#define st_free_bins(bins, size) free(bins) 97static inline st_table_entry** 98st_realloc_bins(st_table_entry **bins, st_index_t newsize, st_index_t oldsize) 99{ 100 bins = (st_table_entry **)realloc(bins, newsize * sizeof(st_table_entry *)); 101 MEMZERO(bins, st_table_entry*, newsize); 102 return bins; 103} 104 105/* Shortage */ 106#define bins as.big.bins 107#define head as.big.head 108#define tail as.big.tail 109#define real_entries as.packed.real_entries 110 111/* preparation for possible packing improvements */ 112#define PACKED_BINS(table) ((table)->as.packed.entries) 113#define PACKED_ENT(table, i) PACKED_BINS(table)[i] 114#define PKEY(table, i) PACKED_ENT((table), (i)).key 115#define PVAL(table, i) PACKED_ENT((table), (i)).val 116#define PHASH(table, i) PACKED_ENT((table), (i)).hash 117#define PKEY_SET(table, i, v) (PKEY((table), (i)) = (v)) 118#define PVAL_SET(table, i, v) (PVAL((table), (i)) = (v)) 119#define PHASH_SET(table, i, v) (PHASH((table), (i)) = (v)) 120 121/* this function depends much on packed layout, so that it placed here */ 122static inline void 123remove_packed_entry(st_table *table, st_index_t i) 124{ 125 table->real_entries--; 126 table->num_entries--; 127 if (i < table->real_entries) { 128 MEMMOVE(&PACKED_ENT(table, i), &PACKED_ENT(table, i+1), 129 st_packed_entry, table->real_entries - i); 130 } 131} 132 133static inline void 134remove_safe_packed_entry(st_table *table, st_index_t i, st_data_t never) 135{ 136 table->num_entries--; 137 PKEY_SET(table, i, never); 138 PVAL_SET(table, i, never); 139 PHASH_SET(table, i, 0); 140} 141 142/* 143 * MINSIZE is the minimum size of a dictionary. 144 */ 145 146#define MINSIZE 8 147 148/* 149Table of prime numbers 2^n+a, 2<=n<=30. 150*/ 151static const unsigned int primes[] = { 152 ST_DEFAULT_INIT_TABLE_SIZE, 153 ST_DEFAULT_SECOND_TABLE_SIZE, 154 32 + 5, 155 64 + 3, 156 128 + 3, 157 256 + 27, 158 512 + 9, 159 1024 + 9, 160 2048 + 5, 161 4096 + 3, 162 8192 + 27, 163 16384 + 43, 164 32768 + 3, 165 65536 + 45, 166 131072 + 29, 167 262144 + 3, 168 524288 + 21, 169 1048576 + 7, 170 2097152 + 17, 171 4194304 + 15, 172 8388608 + 9, 173 16777216 + 43, 174 33554432 + 35, 175 67108864 + 15, 176 134217728 + 29, 177 268435456 + 3, 178 536870912 + 11, 179 1073741824 + 85, 180 0 181}; 182 183static st_index_t 184new_size(st_index_t size) 185{ 186 int i; 187 188#if 0 189 for (i=3; i<31; i++) { 190 if ((1<<i) > size) return 1<<i; 191 } 192 return -1; 193#else 194 st_index_t newsize; 195 196 for (i = 0, newsize = MINSIZE; i < numberof(primes); i++, newsize <<= 1) { 197 if (newsize > size) return primes[i]; 198 } 199 /* Ran out of polynomials */ 200#ifndef NOT_RUBY 201 rb_raise(rb_eRuntimeError, "st_table too big"); 202#endif 203 return -1; /* should raise exception */ 204#endif 205} 206 207#ifdef HASH_LOG 208#ifdef HAVE_UNISTD_H 209#include <unistd.h> 210#endif 211static struct { 212 int all, total, num, str, strcase; 213} collision; 214static int init_st = 0; 215 216static void 217stat_col(void) 218{ 219 char fname[10+sizeof(long)*3]; 220 FILE *f = fopen((snprintf(fname, sizeof(fname), "/tmp/col%ld", (long)getpid()), fname), "w"); 221 fprintf(f, "collision: %d / %d (%6.2f)\n", collision.all, collision.total, 222 ((double)collision.all / (collision.total)) * 100); 223 fprintf(f, "num: %d, str: %d, strcase: %d\n", collision.num, collision.str, collision.strcase); 224 fclose(f); 225} 226#endif 227 228st_table* 229st_init_table_with_size(const struct st_hash_type *type, st_index_t size) 230{ 231 st_table *tbl; 232 233#ifdef HASH_LOG 234# if HASH_LOG+0 < 0 235 { 236 const char *e = getenv("ST_HASH_LOG"); 237 if (!e || !*e) init_st = 1; 238 } 239# endif 240 if (init_st == 0) { 241 init_st = 1; 242 atexit(stat_col); 243 } 244#endif 245 246 247 tbl = st_alloc_table(); 248 tbl->type = type; 249 tbl->num_entries = 0; 250 tbl->entries_packed = size <= MAX_PACKED_HASH; 251 if (tbl->entries_packed) { 252 size = ST_DEFAULT_PACKED_TABLE_SIZE; 253 } 254 else { 255 size = new_size(size); /* round up to prime number */ 256 } 257 tbl->num_bins = size; 258 tbl->bins = st_alloc_bins(size); 259 tbl->head = 0; 260 tbl->tail = 0; 261 262 return tbl; 263} 264 265st_table* 266st_init_table(const struct st_hash_type *type) 267{ 268 return st_init_table_with_size(type, 0); 269} 270 271st_table* 272st_init_numtable(void) 273{ 274 return st_init_table(&type_numhash); 275} 276 277st_table* 278st_init_numtable_with_size(st_index_t size) 279{ 280 return st_init_table_with_size(&type_numhash, size); 281} 282 283st_table* 284st_init_strtable(void) 285{ 286 return st_init_table(&type_strhash); 287} 288 289st_table* 290st_init_strtable_with_size(st_index_t size) 291{ 292 return st_init_table_with_size(&type_strhash, size); 293} 294 295st_table* 296st_init_strcasetable(void) 297{ 298 return st_init_table(&type_strcasehash); 299} 300 301st_table* 302st_init_strcasetable_with_size(st_index_t size) 303{ 304 return st_init_table_with_size(&type_strcasehash, size); 305} 306 307void 308st_clear(st_table *table) 309{ 310 register st_table_entry *ptr, *next; 311 st_index_t i; 312 313 if (table->entries_packed) { 314 table->num_entries = 0; 315 table->real_entries = 0; 316 return; 317 } 318 319 for (i = 0; i < table->num_bins; i++) { 320 ptr = table->bins[i]; 321 table->bins[i] = 0; 322 while (ptr != 0) { 323 next = ptr->next; 324 st_free_entry(ptr); 325 ptr = next; 326 } 327 } 328 table->num_entries = 0; 329 table->head = 0; 330 table->tail = 0; 331} 332 333void 334st_free_table(st_table *table) 335{ 336 st_clear(table); 337 st_free_bins(table->bins, table->num_bins); 338 st_dealloc_table(table); 339} 340 341size_t 342st_memsize(const st_table *table) 343{ 344 if (table->entries_packed) { 345 return table->num_bins * sizeof (void *) + sizeof(st_table); 346 } 347 else { 348 return table->num_entries * sizeof(struct st_table_entry) + table->num_bins * sizeof (void *) + sizeof(st_table); 349 } 350} 351 352#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ 353((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) 354 355#ifdef HASH_LOG 356static void 357count_collision(const struct st_hash_type *type) 358{ 359 collision.all++; 360 if (type == &type_numhash) { 361 collision.num++; 362 } 363 else if (type == &type_strhash) { 364 collision.strcase++; 365 } 366 else if (type == &type_strcasehash) { 367 collision.str++; 368 } 369} 370#define COLLISION (collision_check ? count_collision(table->type) : (void)0) 371#define FOUND_ENTRY (collision_check ? collision.total++ : (void)0) 372#else 373#define COLLISION 374#define FOUND_ENTRY 375#endif 376 377#define FIND_ENTRY(table, ptr, hash_val, bin_pos) \ 378 ((ptr) = find_entry((table), key, (hash_val), ((bin_pos) = (hash_val)%(table)->num_bins))) 379 380static st_table_entry * 381find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_pos) 382{ 383 register st_table_entry *ptr = table->bins[bin_pos]; 384 FOUND_ENTRY; 385 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) { 386 COLLISION; 387 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) { 388 ptr = ptr->next; 389 } 390 ptr = ptr->next; 391 } 392 return ptr; 393} 394 395static inline st_index_t 396find_packed_index(st_table *table, st_index_t hash_val, st_data_t key) 397{ 398 st_index_t i = 0; 399 while (i < table->real_entries && 400 (PHASH(table, i) != hash_val || !EQUAL(table, key, PKEY(table, i)))) { 401 i++; 402 } 403 return i; 404} 405 406#define collision_check 0 407 408int 409st_lookup(st_table *table, register st_data_t key, st_data_t *value) 410{ 411 st_index_t hash_val; 412 register st_table_entry *ptr; 413 414 hash_val = do_hash(key, table); 415 416 if (table->entries_packed) { 417 st_index_t i = find_packed_index(table, hash_val, key); 418 if (i < table->real_entries) { 419 if (value != 0) *value = PVAL(table, i); 420 return 1; 421 } 422 return 0; 423 } 424 425 ptr = find_entry(table, key, hash_val, hash_val % table->num_bins); 426 427 if (ptr == 0) { 428 return 0; 429 } 430 else { 431 if (value != 0) *value = ptr->record; 432 return 1; 433 } 434} 435 436int 437st_get_key(st_table *table, register st_data_t key, st_data_t *result) 438{ 439 st_index_t hash_val; 440 register st_table_entry *ptr; 441 442 hash_val = do_hash(key, table); 443 444 if (table->entries_packed) { 445 st_index_t i = find_packed_index(table, hash_val, key); 446 if (i < table->real_entries) { 447 if (result != 0) *result = PKEY(table, i); 448 return 1; 449 } 450 return 0; 451 } 452 453 ptr = find_entry(table, key, hash_val, hash_val % table->num_bins); 454 455 if (ptr == 0) { 456 return 0; 457 } 458 else { 459 if (result != 0) *result = ptr->key; 460 return 1; 461 } 462} 463 464#undef collision_check 465#define collision_check 1 466 467static inline st_table_entry * 468new_entry(st_table * table, st_data_t key, st_data_t value, 469 st_index_t hash_val, register st_index_t bin_pos) 470{ 471 register st_table_entry *entry = st_alloc_entry(); 472 473 entry->next = table->bins[bin_pos]; 474 table->bins[bin_pos] = entry; 475 entry->hash = hash_val; 476 entry->key = key; 477 entry->record = value; 478 479 return entry; 480} 481 482static inline void 483add_direct(st_table *table, st_data_t key, st_data_t value, 484 st_index_t hash_val, register st_index_t bin_pos) 485{ 486 register st_table_entry *entry; 487 if (table->num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins) { 488 rehash(table); 489 bin_pos = hash_val % table->num_bins; 490 } 491 492 entry = new_entry(table, key, value, hash_val, bin_pos); 493 494 if (table->head != 0) { 495 entry->fore = 0; 496 (entry->back = table->tail)->fore = entry; 497 table->tail = entry; 498 } 499 else { 500 table->head = table->tail = entry; 501 entry->fore = entry->back = 0; 502 } 503 table->num_entries++; 504} 505 506static void 507unpack_entries(register st_table *table) 508{ 509 st_index_t i; 510 st_packed_entry packed_bins[MAX_PACKED_HASH]; 511 register st_table_entry *entry, *preventry = 0, **chain; 512 st_table tmp_table = *table; 513 514 MEMCPY(packed_bins, PACKED_BINS(table), st_packed_entry, MAX_PACKED_HASH); 515 table->as.packed.entries = packed_bins; 516 tmp_table.entries_packed = 0; 517#if ST_DEFAULT_INIT_TABLE_SIZE == ST_DEFAULT_PACKED_TABLE_SIZE 518 MEMZERO(tmp_table.bins, st_table_entry*, tmp_table.num_bins); 519#else 520 tmp_table.bins = st_realloc_bins(tmp_table.bins, ST_DEFAULT_INIT_TABLE_SIZE, tmp_table.num_bins); 521 tmp_table.num_bins = ST_DEFAULT_INIT_TABLE_SIZE; 522#endif 523 i = 0; 524 chain = &tmp_table.head; 525 do { 526 st_data_t key = packed_bins[i].key; 527 st_data_t val = packed_bins[i].val; 528 st_index_t hash = packed_bins[i].hash; 529 entry = new_entry(&tmp_table, key, val, hash, 530 hash % ST_DEFAULT_INIT_TABLE_SIZE); 531 *chain = entry; 532 entry->back = preventry; 533 preventry = entry; 534 chain = &entry->fore; 535 } while (++i < MAX_PACKED_HASH); 536 *chain = NULL; 537 tmp_table.tail = entry; 538 *table = tmp_table; 539} 540 541static void 542add_packed_direct(st_table *table, st_data_t key, st_data_t value, st_index_t hash_val) 543{ 544 if (table->real_entries < MAX_PACKED_HASH) { 545 st_index_t i = table->real_entries++; 546 PKEY_SET(table, i, key); 547 PVAL_SET(table, i, value); 548 PHASH_SET(table, i, hash_val); 549 table->num_entries++; 550 } 551 else { 552 unpack_entries(table); 553 add_direct(table, key, value, hash_val, hash_val % table->num_bins); 554 } 555} 556 557 558int 559st_insert(register st_table *table, register st_data_t key, st_data_t value) 560{ 561 st_index_t hash_val; 562 register st_index_t bin_pos; 563 register st_table_entry *ptr; 564 565 hash_val = do_hash(key, table); 566 567 if (table->entries_packed) { 568 st_index_t i = find_packed_index(table, hash_val, key); 569 if (i < table->real_entries) { 570 PVAL_SET(table, i, value); 571 return 1; 572 } 573 add_packed_direct(table, key, value, hash_val); 574 return 0; 575 } 576 577 FIND_ENTRY(table, ptr, hash_val, bin_pos); 578 579 if (ptr == 0) { 580 add_direct(table, key, value, hash_val, bin_pos); 581 return 0; 582 } 583 else { 584 ptr->record = value; 585 return 1; 586 } 587} 588 589int 590st_insert2(register st_table *table, register st_data_t key, st_data_t value, 591 st_data_t (*func)(st_data_t)) 592{ 593 st_index_t hash_val; 594 register st_index_t bin_pos; 595 register st_table_entry *ptr; 596 597 hash_val = do_hash(key, table); 598 599 if (table->entries_packed) { 600 st_index_t i = find_packed_index(table, hash_val, key); 601 if (i < table->real_entries) { 602 PVAL_SET(table, i, value); 603 return 1; 604 } 605 key = (*func)(key); 606 add_packed_direct(table, key, value, hash_val); 607 return 0; 608 } 609 610 FIND_ENTRY(table, ptr, hash_val, bin_pos); 611 612 if (ptr == 0) { 613 key = (*func)(key); 614 add_direct(table, key, value, hash_val, bin_pos); 615 return 0; 616 } 617 else { 618 ptr->record = value; 619 return 1; 620 } 621} 622 623void 624st_add_direct(st_table *table, st_data_t key, st_data_t value) 625{ 626 st_index_t hash_val; 627 628 hash_val = do_hash(key, table); 629 if (table->entries_packed) { 630 add_packed_direct(table, key, value, hash_val); 631 return; 632 } 633 634 add_direct(table, key, value, hash_val, hash_val % table->num_bins); 635} 636 637static void 638rehash(register st_table *table) 639{ 640 register st_table_entry *ptr, **new_bins; 641 st_index_t new_num_bins, hash_val; 642 643 new_num_bins = new_size(table->num_bins+1); 644 new_bins = st_realloc_bins(table->bins, new_num_bins, table->num_bins); 645 table->num_bins = new_num_bins; 646 table->bins = new_bins; 647 648 if ((ptr = table->head) != 0) { 649 do { 650 hash_val = ptr->hash % new_num_bins; 651 ptr->next = new_bins[hash_val]; 652 new_bins[hash_val] = ptr; 653 } while ((ptr = ptr->fore) != 0); 654 } 655} 656 657st_table* 658st_copy(st_table *old_table) 659{ 660 st_table *new_table; 661 st_table_entry *ptr, *entry, *prev, **tailp; 662 st_index_t num_bins = old_table->num_bins; 663 st_index_t hash_val; 664 665 new_table = st_alloc_table(); 666 if (new_table == 0) { 667 return 0; 668 } 669 670 *new_table = *old_table; 671 new_table->bins = st_alloc_bins(num_bins); 672 673 if (new_table->bins == 0) { 674 st_dealloc_table(new_table); 675 return 0; 676 } 677 678 if (old_table->entries_packed) { 679 MEMCPY(new_table->bins, old_table->bins, st_table_entry*, old_table->num_bins); 680 return new_table; 681 } 682 683 if ((ptr = old_table->head) != 0) { 684 prev = 0; 685 tailp = &new_table->head; 686 do { 687 entry = st_alloc_entry(); 688 if (entry == 0) { 689 st_free_table(new_table); 690 return 0; 691 } 692 *entry = *ptr; 693 hash_val = entry->hash % num_bins; 694 entry->next = new_table->bins[hash_val]; 695 new_table->bins[hash_val] = entry; 696 entry->back = prev; 697 *tailp = prev = entry; 698 tailp = &entry->fore; 699 } while ((ptr = ptr->fore) != 0); 700 new_table->tail = prev; 701 } 702 703 return new_table; 704} 705 706static inline void 707remove_entry(st_table *table, st_table_entry *ptr) 708{ 709 if (ptr->fore == 0 && ptr->back == 0) { 710 table->head = 0; 711 table->tail = 0; 712 } 713 else { 714 st_table_entry *fore = ptr->fore, *back = ptr->back; 715 if (fore) fore->back = back; 716 if (back) back->fore = fore; 717 if (ptr == table->head) table->head = fore; 718 if (ptr == table->tail) table->tail = back; 719 } 720 table->num_entries--; 721} 722 723int 724st_delete(register st_table *table, register st_data_t *key, st_data_t *value) 725{ 726 st_index_t hash_val; 727 st_table_entry **prev; 728 register st_table_entry *ptr; 729 730 hash_val = do_hash(*key, table); 731 732 if (table->entries_packed) { 733 st_index_t i = find_packed_index(table, hash_val, *key); 734 if (i < table->real_entries) { 735 if (value != 0) *value = PVAL(table, i); 736 *key = PKEY(table, i); 737 remove_packed_entry(table, i); 738 return 1; 739 } 740 if (value != 0) *value = 0; 741 return 0; 742 } 743 744 prev = &table->bins[hash_val % table->num_bins]; 745 for (;(ptr = *prev) != 0; prev = &ptr->next) { 746 if (EQUAL(table, *key, ptr->key)) { 747 *prev = ptr->next; 748 remove_entry(table, ptr); 749 if (value != 0) *value = ptr->record; 750 *key = ptr->key; 751 st_free_entry(ptr); 752 return 1; 753 } 754 } 755 756 if (value != 0) *value = 0; 757 return 0; 758} 759 760int 761st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never) 762{ 763 st_index_t hash_val; 764 register st_table_entry *ptr; 765 766 hash_val = do_hash(*key, table); 767 768 if (table->entries_packed) { 769 st_index_t i = find_packed_index(table, hash_val, *key); 770 if (i < table->real_entries) { 771 if (value != 0) *value = PVAL(table, i); 772 *key = PKEY(table, i); 773 remove_safe_packed_entry(table, i, never); 774 return 1; 775 } 776 if (value != 0) *value = 0; 777 return 0; 778 } 779 780 ptr = table->bins[hash_val % table->num_bins]; 781 782 for (; ptr != 0; ptr = ptr->next) { 783 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { 784 remove_entry(table, ptr); 785 *key = ptr->key; 786 if (value != 0) *value = ptr->record; 787 ptr->key = ptr->record = never; 788 return 1; 789 } 790 } 791 792 if (value != 0) *value = 0; 793 return 0; 794} 795 796void 797st_cleanup_safe(st_table *table, st_data_t never) 798{ 799 st_table_entry *ptr, **last, *tmp; 800 st_index_t i; 801 802 if (table->entries_packed) { 803 st_index_t i = 0, j = 0; 804 while (PKEY(table, i) != never) { 805 if (i++ == table->real_entries) return; 806 } 807 for (j = i; ++i < table->real_entries;) { 808 if (PKEY(table, i) == never) continue; 809 PACKED_ENT(table, j) = PACKED_ENT(table, i); 810 j++; 811 } 812 table->real_entries = j; 813 /* table->num_entries really should be equal j at this moment, but let set it anyway */ 814 table->num_entries = j; 815 return; 816 } 817 818 for (i = 0; i < table->num_bins; i++) { 819 ptr = *(last = &table->bins[i]); 820 while (ptr != 0) { 821 if (ptr->key == never) { 822 tmp = ptr; 823 *last = ptr = ptr->next; 824 st_free_entry(tmp); 825 } 826 else { 827 ptr = *(last = &ptr->next); 828 } 829 } 830 } 831} 832 833int 834st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data_t arg) 835{ 836 st_index_t hash_val, bin_pos; 837 register st_table_entry *ptr, **last, *tmp; 838 st_data_t value = 0; 839 int retval, existing = 0; 840 841 hash_val = do_hash(key, table); 842 843 if (table->entries_packed) { 844 st_index_t i = find_packed_index(table, hash_val, key); 845 if (i < table->real_entries) { 846 key = PKEY(table, i); 847 value = PVAL(table, i); 848 existing = 1; 849 } 850 { 851 retval = (*func)(&key, &value, arg, existing); 852 if (!table->entries_packed) { 853 FIND_ENTRY(table, ptr, hash_val, bin_pos); 854 goto unpacked; 855 } 856 switch (retval) { 857 case ST_CONTINUE: 858 if (!existing) { 859 add_packed_direct(table, key, value, hash_val); 860 break; 861 } 862 PVAL_SET(table, i, value); 863 break; 864 case ST_DELETE: 865 if (!existing) break; 866 remove_packed_entry(table, i); 867 } 868 } 869 return existing; 870 } 871 872 FIND_ENTRY(table, ptr, hash_val, bin_pos); 873 874 if (ptr != 0) { 875 key = ptr->key; 876 value = ptr->record; 877 existing = 1; 878 } 879 { 880 retval = (*func)(&key, &value, arg, existing); 881 unpacked: 882 switch (retval) { 883 case ST_CONTINUE: 884 if (!existing) { 885 add_direct(table, key, value, hash_val, hash_val % table->num_bins); 886 break; 887 } 888 ptr->record = value; 889 break; 890 case ST_DELETE: 891 if (!existing) break; 892 last = &table->bins[bin_pos]; 893 for (; (tmp = *last) != 0; last = &tmp->next) { 894 if (ptr == tmp) { 895 tmp = ptr->fore; 896 *last = ptr->next; 897 remove_entry(table, ptr); 898 st_free_entry(ptr); 899 break; 900 } 901 } 902 break; 903 } 904 return existing; 905 } 906} 907 908int 909st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t never) 910{ 911 st_table_entry *ptr, **last, *tmp; 912 enum st_retval retval; 913 st_index_t i; 914 915 if (table->entries_packed) { 916 for (i = 0; i < table->real_entries; i++) { 917 st_data_t key, val; 918 st_index_t hash; 919 key = PKEY(table, i); 920 val = PVAL(table, i); 921 hash = PHASH(table, i); 922 if (key == never) continue; 923 retval = (*func)(key, val, arg); 924 if (!table->entries_packed) { 925 FIND_ENTRY(table, ptr, hash, i); 926 if (retval == ST_CHECK) { 927 if (!ptr) goto deleted; 928 goto unpacked_continue; 929 } 930 goto unpacked; 931 } 932 switch (retval) { 933 case ST_CHECK: /* check if hash is modified during iteration */ 934 if (PHASH(table, i) == 0 && PKEY(table, i) == never) { 935 break; 936 } 937 i = find_packed_index(table, hash, key); 938 if (i == table->real_entries) { 939 goto deleted; 940 } 941 /* fall through */ 942 case ST_CONTINUE: 943 break; 944 case ST_STOP: 945 return 0; 946 case ST_DELETE: 947 remove_safe_packed_entry(table, i, never); 948 break; 949 } 950 } 951 return 0; 952 } 953 else { 954 ptr = table->head; 955 } 956 957 if (ptr != 0) { 958 do { 959 if (ptr->key == never) 960 goto unpacked_continue; 961 i = ptr->hash % table->num_bins; 962 retval = (*func)(ptr->key, ptr->record, arg); 963 unpacked: 964 switch (retval) { 965 case ST_CHECK: /* check if hash is modified during iteration */ 966 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { 967 if (!tmp) { 968 deleted: 969 /* call func with error notice */ 970 retval = (*func)(0, 0, arg, 1); 971 return 1; 972 } 973 } 974 /* fall through */ 975 case ST_CONTINUE: 976 unpacked_continue: 977 ptr = ptr->fore; 978 break; 979 case ST_STOP: 980 return 0; 981 case ST_DELETE: 982 last = &table->bins[ptr->hash % table->num_bins]; 983 for (; (tmp = *last) != 0; last = &tmp->next) { 984 if (ptr == tmp) { 985 tmp = ptr->fore; 986 remove_entry(table, ptr); 987 ptr->key = ptr->record = never; 988 ptr->hash = 0; 989 ptr = tmp; 990 break; 991 } 992 } 993 } 994 } while (ptr && table->head); 995 } 996 return 0; 997} 998 999int 1000st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) 1001{ 1002 st_table_entry *ptr, **last, *tmp; 1003 enum st_retval retval; 1004 st_index_t i; 1005 1006 if (table->entries_packed) { 1007 for (i = 0; i < table->real_entries; i++) { 1008 st_data_t key, val, hash; 1009 key = PKEY(table, i); 1010 val = PVAL(table, i); 1011 hash = PHASH(table, i); 1012 retval = (*func)(key, val, arg); 1013 if (!table->entries_packed) { 1014 FIND_ENTRY(table, ptr, hash, i); 1015 if (!ptr) return 0; 1016 goto unpacked; 1017 } 1018 switch (retval) { 1019 case ST_CONTINUE: 1020 break; 1021 case ST_CHECK: 1022 case ST_STOP: 1023 return 0; 1024 case ST_DELETE: 1025 remove_packed_entry(table, i); 1026 i--; 1027 break; 1028 } 1029 } 1030 return 0; 1031 } 1032 else { 1033 ptr = table->head; 1034 } 1035 1036 if (ptr != 0) { 1037 do { 1038 i = ptr->hash % table->num_bins; 1039 retval = (*func)(ptr->key, ptr->record, arg); 1040 unpacked: 1041 switch (retval) { 1042 case ST_CONTINUE: 1043 ptr = ptr->fore; 1044 break; 1045 case ST_CHECK: 1046 case ST_STOP: 1047 return 0; 1048 case ST_DELETE: 1049 last = &table->bins[ptr->hash % table->num_bins]; 1050 for (; (tmp = *last) != 0; last = &tmp->next) { 1051 if (ptr == tmp) { 1052 tmp = ptr->fore; 1053 *last = ptr->next; 1054 remove_entry(table, ptr); 1055 st_free_entry(ptr); 1056 ptr = tmp; 1057 break; 1058 } 1059 } 1060 } 1061 } while (ptr && table->head); 1062 } 1063 return 0; 1064} 1065 1066#if 0 /* unused right now */ 1067int 1068st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) 1069{ 1070 st_table_entry *ptr, **last, *tmp; 1071 enum st_retval retval; 1072 int i; 1073 1074 if (table->entries_packed) { 1075 for (i = table->num_entries-1; 0 <= i; i--) { 1076 int j; 1077 st_data_t key, val; 1078 key = PKEY(table, i); 1079 val = PVAL(table, i); 1080 retval = (*func)(key, val, arg); 1081 switch (retval) { 1082 case ST_CHECK: /* check if hash is modified during iteration */ 1083 for (j = 0; j < table->num_entries; j++) { 1084 if (PKEY(table, j) == key) 1085 break; 1086 } 1087 if (j == table->num_entries) { 1088 /* call func with error notice */ 1089 retval = (*func)(0, 0, arg, 1); 1090 return 1; 1091 } 1092 /* fall through */ 1093 case ST_CONTINUE: 1094 break; 1095 case ST_STOP: 1096 return 0; 1097 case ST_DELETE: 1098 remove_packed_entry(table, i); 1099 break; 1100 } 1101 } 1102 return 0; 1103 } 1104 1105 if ((ptr = table->head) != 0) { 1106 ptr = ptr->back; 1107 do { 1108 retval = (*func)(ptr->key, ptr->record, arg, 0); 1109 switch (retval) { 1110 case ST_CHECK: /* check if hash is modified during iteration */ 1111 i = ptr->hash % table->num_bins; 1112 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { 1113 if (!tmp) { 1114 /* call func with error notice */ 1115 retval = (*func)(0, 0, arg, 1); 1116 return 1; 1117 } 1118 } 1119 /* fall through */ 1120 case ST_CONTINUE: 1121 ptr = ptr->back; 1122 break; 1123 case ST_STOP: 1124 return 0; 1125 case ST_DELETE: 1126 last = &table->bins[ptr->hash % table->num_bins]; 1127 for (; (tmp = *last) != 0; last = &tmp->next) { 1128 if (ptr == tmp) { 1129 tmp = ptr->back; 1130 *last = ptr->next; 1131 remove_entry(table, ptr); 1132 st_free_entry(ptr); 1133 ptr = tmp; 1134 break; 1135 } 1136 } 1137 ptr = ptr->next; 1138 free(tmp); 1139 table->num_entries--; 1140 } 1141 } while (ptr && table->head); 1142 } 1143 return 0; 1144} 1145#endif 1146 1147/* 1148 * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code 1149 * 1150 * @(#) $Hash32: Revision: 1.1 $ 1151 * @(#) $Hash32: Id: hash_32a.c,v 1.1 2003/10/03 20:38:53 chongo Exp $ 1152 * @(#) $Hash32: Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $ 1153 * 1154 *** 1155 * 1156 * Fowler/Noll/Vo hash 1157 * 1158 * The basis of this hash algorithm was taken from an idea sent 1159 * as reviewer comments to the IEEE POSIX P1003.2 committee by: 1160 * 1161 * Phong Vo (http://www.research.att.com/info/kpv/) 1162 * Glenn Fowler (http://www.research.att.com/~gsf/) 1163 * 1164 * In a subsequent ballot round: 1165 * 1166 * Landon Curt Noll (http://www.isthe.com/chongo/) 1167 * 1168 * improved on their algorithm. Some people tried this hash 1169 * and found that it worked rather well. In an EMail message 1170 * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash. 1171 * 1172 * FNV hashes are designed to be fast while maintaining a low 1173 * collision rate. The FNV speed allows one to quickly hash lots 1174 * of data while maintaining a reasonable collision rate. See: 1175 * 1176 * http://www.isthe.com/chongo/tech/comp/fnv/index.html 1177 * 1178 * for more details as well as other forms of the FNV hash. 1179 *** 1180 * 1181 * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the 1182 * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str(). 1183 * 1184 *** 1185 * 1186 * Please do not copyright this code. This code is in the public domain. 1187 * 1188 * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 1189 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO 1190 * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR 1191 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF 1192 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR 1193 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 1194 * PERFORMANCE OF THIS SOFTWARE. 1195 * 1196 * By: 1197 * chongo <Landon Curt Noll> /\oo/\ 1198 * http://www.isthe.com/chongo/ 1199 * 1200 * Share and Enjoy! :-) 1201 */ 1202 1203/* 1204 * 32 bit FNV-1 and FNV-1a non-zero initial basis 1205 * 1206 * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets: 1207 * 1208 * chongo <Landon Curt Noll> /\../\ 1209 * 1210 * NOTE: The \'s above are not back-slashing escape characters. 1211 * They are literal ASCII backslash 0x5c characters. 1212 * 1213 * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition. 1214 */ 1215#define FNV1_32A_INIT 0x811c9dc5 1216 1217/* 1218 * 32 bit magic FNV-1a prime 1219 */ 1220#define FNV_32_PRIME 0x01000193 1221 1222#ifdef ST_USE_FNV1 1223static st_index_t 1224strhash(st_data_t arg) 1225{ 1226 register const char *string = (const char *)arg; 1227 register st_index_t hval = FNV1_32A_INIT; 1228 1229 /* 1230 * FNV-1a hash each octet in the buffer 1231 */ 1232 while (*string) { 1233 /* xor the bottom with the current octet */ 1234 hval ^= (unsigned int)*string++; 1235 1236 /* multiply by the 32 bit FNV magic prime mod 2^32 */ 1237 hval *= FNV_32_PRIME; 1238 } 1239 return hval; 1240} 1241#else 1242 1243#ifndef UNALIGNED_WORD_ACCESS 1244# if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \ 1245 defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD86) || \ 1246 defined(__mc68020__) 1247# define UNALIGNED_WORD_ACCESS 1 1248# endif 1249#endif 1250#ifndef UNALIGNED_WORD_ACCESS 1251# define UNALIGNED_WORD_ACCESS 0 1252#endif 1253 1254/* MurmurHash described in http://murmurhash.googlepages.com/ */ 1255#ifndef MURMUR 1256#define MURMUR 2 1257#endif 1258 1259#define MurmurMagic_1 (st_index_t)0xc6a4a793 1260#define MurmurMagic_2 (st_index_t)0x5bd1e995 1261#if MURMUR == 1 1262#define MurmurMagic MurmurMagic_1 1263#elif MURMUR == 2 1264#if SIZEOF_ST_INDEX_T > 4 1265#define MurmurMagic ((MurmurMagic_1 << 32) | MurmurMagic_2) 1266#else 1267#define MurmurMagic MurmurMagic_2 1268#endif 1269#endif 1270 1271static inline st_index_t 1272murmur(st_index_t h, st_index_t k, int r) 1273{ 1274 const st_index_t m = MurmurMagic; 1275#if MURMUR == 1 1276 h += k; 1277 h *= m; 1278 h ^= h >> r; 1279#elif MURMUR == 2 1280 k *= m; 1281 k ^= k >> r; 1282 k *= m; 1283 1284 h *= m; 1285 h ^= k; 1286#endif 1287 return h; 1288} 1289 1290static inline st_index_t 1291murmur_finish(st_index_t h) 1292{ 1293#if MURMUR == 1 1294 h = murmur(h, 0, 10); 1295 h = murmur(h, 0, 17); 1296#elif MURMUR == 2 1297 h ^= h >> 13; 1298 h *= MurmurMagic; 1299 h ^= h >> 15; 1300#endif 1301 return h; 1302} 1303 1304#define murmur_step(h, k) murmur((h), (k), 16) 1305 1306#if MURMUR == 1 1307#define murmur1(h) murmur_step((h), 16) 1308#else 1309#define murmur1(h) murmur_step((h), 24) 1310#endif 1311 1312st_index_t 1313st_hash(const void *ptr, size_t len, st_index_t h) 1314{ 1315 const char *data = ptr; 1316 st_index_t t = 0; 1317 1318 h += 0xdeadbeef; 1319 1320#define data_at(n) (st_index_t)((unsigned char)data[(n)]) 1321#define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0) 1322#if SIZEOF_ST_INDEX_T > 4 1323#define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4 1324#if SIZEOF_ST_INDEX_T > 8 1325#define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \ 1326 UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8 1327#define UNALIGNED_ADD_ALL UNALIGNED_ADD_16 1328#endif 1329#define UNALIGNED_ADD_ALL UNALIGNED_ADD_8 1330#else 1331#define UNALIGNED_ADD_ALL UNALIGNED_ADD_4 1332#endif 1333 if (len >= sizeof(st_index_t)) { 1334#if !UNALIGNED_WORD_ACCESS 1335 int align = (int)((st_data_t)data % sizeof(st_index_t)); 1336 if (align) { 1337 st_index_t d = 0; 1338 int sl, sr, pack; 1339 1340 switch (align) { 1341#ifdef WORDS_BIGENDIAN 1342# define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \ 1343 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2) 1344#else 1345# define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \ 1346 t |= data_at(n) << CHAR_BIT*(n) 1347#endif 1348 UNALIGNED_ADD_ALL; 1349#undef UNALIGNED_ADD 1350 } 1351 1352#ifdef WORDS_BIGENDIAN 1353 t >>= (CHAR_BIT * align) - CHAR_BIT; 1354#else 1355 t <<= (CHAR_BIT * align); 1356#endif 1357 1358 data += sizeof(st_index_t)-align; 1359 len -= sizeof(st_index_t)-align; 1360 1361 sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align); 1362 sr = CHAR_BIT * align; 1363 1364 while (len >= sizeof(st_index_t)) { 1365 d = *(st_index_t *)data; 1366#ifdef WORDS_BIGENDIAN 1367 t = (t << sr) | (d >> sl); 1368#else 1369 t = (t >> sr) | (d << sl); 1370#endif 1371 h = murmur_step(h, t); 1372 t = d; 1373 data += sizeof(st_index_t); 1374 len -= sizeof(st_index_t); 1375 } 1376 1377 pack = len < (size_t)align ? (int)len : align; 1378 d = 0; 1379 switch (pack) { 1380#ifdef WORDS_BIGENDIAN 1381# define UNALIGNED_ADD(n) case (n) + 1: \ 1382 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1) 1383#else 1384# define UNALIGNED_ADD(n) case (n) + 1: \ 1385 d |= data_at(n) << CHAR_BIT*(n) 1386#endif 1387 UNALIGNED_ADD_ALL; 1388#undef UNALIGNED_ADD 1389 } 1390#ifdef WORDS_BIGENDIAN 1391 t = (t << sr) | (d >> sl); 1392#else 1393 t = (t >> sr) | (d << sl); 1394#endif 1395 1396#if MURMUR == 2 1397 if (len < (size_t)align) goto skip_tail; 1398#endif 1399 h = murmur_step(h, t); 1400 data += pack; 1401 len -= pack; 1402 } 1403 else 1404#endif 1405 { 1406 do { 1407 h = murmur_step(h, *(st_index_t *)data); 1408 data += sizeof(st_index_t); 1409 len -= sizeof(st_index_t); 1410 } while (len >= sizeof(st_index_t)); 1411 } 1412 } 1413 1414 t = 0; 1415 switch (len) { 1416#ifdef WORDS_BIGENDIAN 1417# define UNALIGNED_ADD(n) case (n) + 1: \ 1418 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1) 1419#else 1420# define UNALIGNED_ADD(n) case (n) + 1: \ 1421 t |= data_at(n) << CHAR_BIT*(n) 1422#endif 1423 UNALIGNED_ADD_ALL; 1424#undef UNALIGNED_ADD 1425#if MURMUR == 1 1426 h = murmur_step(h, t); 1427#elif MURMUR == 2 1428# if !UNALIGNED_WORD_ACCESS 1429 skip_tail: 1430# endif 1431 h ^= t; 1432 h *= MurmurMagic; 1433#endif 1434 } 1435 1436 return murmur_finish(h); 1437} 1438 1439st_index_t 1440st_hash_uint32(st_index_t h, uint32_t i) 1441{ 1442 return murmur_step(h + i, 16); 1443} 1444 1445st_index_t 1446st_hash_uint(st_index_t h, st_index_t i) 1447{ 1448 st_index_t v = 0; 1449 h += i; 1450#ifdef WORDS_BIGENDIAN 1451#if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8 1452 v = murmur1(v + (h >> 12*8)); 1453#endif 1454#if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8 1455 v = murmur1(v + (h >> 8*8)); 1456#endif 1457#if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8 1458 v = murmur1(v + (h >> 4*8)); 1459#endif 1460#endif 1461 v = murmur1(v + h); 1462#ifndef WORDS_BIGENDIAN 1463#if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8 1464 v = murmur1(v + (h >> 4*8)); 1465#endif 1466#if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8 1467 v = murmur1(v + (h >> 8*8)); 1468#endif 1469#if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8 1470 v = murmur1(v + (h >> 12*8)); 1471#endif 1472#endif 1473 return v; 1474} 1475 1476st_index_t 1477st_hash_end(st_index_t h) 1478{ 1479 h = murmur_step(h, 10); 1480 h = murmur_step(h, 17); 1481 return h; 1482} 1483 1484#undef st_hash_start 1485st_index_t 1486st_hash_start(st_index_t h) 1487{ 1488 return h; 1489} 1490 1491static st_index_t 1492strhash(st_data_t arg) 1493{ 1494 register const char *string = (const char *)arg; 1495 return st_hash(string, strlen(string), FNV1_32A_INIT); 1496} 1497#endif 1498 1499int 1500st_strcasecmp(const char *s1, const char *s2) 1501{ 1502 unsigned int c1, c2; 1503 1504 while (1) { 1505 c1 = (unsigned char)*s1++; 1506 c2 = (unsigned char)*s2++; 1507 if (c1 == '\0' || c2 == '\0') { 1508 if (c1 != '\0') return 1; 1509 if (c2 != '\0') return -1; 1510 return 0; 1511 } 1512 if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A'; 1513 if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A'; 1514 if (c1 != c2) { 1515 if (c1 > c2) 1516 return 1; 1517 else 1518 return -1; 1519 } 1520 } 1521} 1522 1523int 1524st_strncasecmp(const char *s1, const char *s2, size_t n) 1525{ 1526 unsigned int c1, c2; 1527 1528 while (n--) { 1529 c1 = (unsigned char)*s1++; 1530 c2 = (unsigned char)*s2++; 1531 if (c1 == '\0' || c2 == '\0') { 1532 if (c1 != '\0') return 1; 1533 if (c2 != '\0') return -1; 1534 return 0; 1535 } 1536 if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A'; 1537 if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A'; 1538 if (c1 != c2) { 1539 if (c1 > c2) 1540 return 1; 1541 else 1542 return -1; 1543 } 1544 } 1545 return 0; 1546} 1547 1548static st_index_t 1549strcasehash(st_data_t arg) 1550{ 1551 register const char *string = (const char *)arg; 1552 register st_index_t hval = FNV1_32A_INIT; 1553 1554 /* 1555 * FNV-1a hash each octet in the buffer 1556 */ 1557 while (*string) { 1558 unsigned int c = (unsigned char)*string++; 1559 if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A'; 1560 hval ^= c; 1561 1562 /* multiply by the 32 bit FNV magic prime mod 2^32 */ 1563 hval *= FNV_32_PRIME; 1564 } 1565 return hval; 1566} 1567 1568int 1569st_numcmp(st_data_t x, st_data_t y) 1570{ 1571 return x != y; 1572} 1573 1574st_index_t 1575st_numhash(st_data_t n) 1576{ 1577 return (st_index_t)n; 1578} 1579