st.c

   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/config.h"
  10 #include "ruby/defines.h"
  11 #include "ruby/st.h"
  12 #endif
  13
  14 #include <stdio.h>
  15 #ifdef HAVE_STDLIB_H
  16 #include <stdlib.h>
  17 #endif
  18 #include <string.h>
  19
  20 typedef struct st_table_entry st_table_entry;
  21
  22 struct st_table_entry {
  23     unsigned int hash;
  24     st_data_t key;
  25     st_data_t record;
  26     st_table_entry *next;
  27     st_table_entry *fore, *back;
  28 };
  29
  30 #define ST_DEFAULT_MAX_DENSITY 5
  31 #define ST_DEFAULT_INIT_TABLE_SIZE 11
  32
  33     /*
  34      * DEFAULT_MAX_DENSITY is the default for the largest we allow the
  35      * average number of items per bin before increasing the number of
  36      * bins
  37      *
  38      * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
  39      * allocated initially
  40      *
  41      */
  42
  43 static const struct st_hash_type type_numhash = {
  44     st_numcmp,
  45     st_numhash,
  46 };
  47
  48 /* extern int strcmp(const char *, const char *); */
  49 static int strhash(const char *);
  50 static const struct st_hash_type type_strhash = {
  51     strcmp,
  52     strhash,
  53 };
  54
  55 static int strcasehash(const char *);
  56 static const struct st_hash_type type_strcasehash = {
  57     st_strcasecmp,
  58     strcasehash,
  59 };
  60
  61 static void rehash(st_table *);
  62
  63 #ifdef RUBY
  64 #define malloc xmalloc
  65 #define calloc xcalloc
  66 #define free(x) xfree(x)
  67 #endif
  68
  69 #define alloc(type) (type*)malloc((size_t)sizeof(type))
  70 #define Calloc(n,s) (char*)calloc((n),(s))
  71
  72 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
  73
  74 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
  75 #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
  76
  77 /*
  78  * MINSIZE is the minimum size of a dictionary.
  79  */
  80
  81 #define MINSIZE 8
  82
  83 /*
  84 Table of prime numbers 2^n+a, 2<=n<=30.
  85 */
  86 static const long primes[] = {
  87         8 + 3,
  88         16 + 3,
  89         32 + 5,
  90         64 + 3,
  91         128 + 3,
  92         256 + 27,
  93         512 + 9,
  94         1024 + 9,
  95         2048 + 5,
  96         4096 + 3,
  97         8192 + 27,
  98         16384 + 43,
  99         32768 + 3,
 100         65536 + 45,
 101         131072 + 29,
 102         262144 + 3,
 103         524288 + 21,
 104         1048576 + 7,
 105         2097152 + 17,
 106         4194304 + 15,
 107         8388608 + 9,
 108         16777216 + 43,
 109         33554432 + 35,
 110         67108864 + 15,
 111         134217728 + 29,
 112         268435456 + 3,
 113         536870912 + 11,
 114         1073741824 + 85,
 115         0
 116 };
 117
 118 static int
 119 new_size(int size)
 120 {
 121     int i;
 122
 123 #if 0
 124     for (i=3; i<31; i++) {
 125         if ((1<<i) > size) return 1<<i;
 126     }
 127     return -1;
 128 #else
 129     int newsize;
 130
 131     for (i = 0, newsize = MINSIZE;
 132          i < (int )(sizeof(primes)/sizeof(primes[0]));
 133          i++, newsize <<= 1)
 134     {
 135         if (newsize > size) return primes[i];
 136     }
 137     /* Ran out of polynomials */
 138     return -1;                  /* should raise exception */
 139 #endif
 140 }
 141
 142 #ifdef HASH_LOG
 143 static int collision = 0;
 144 static int init_st = 0;
 145
 146 static void
 147 stat_col()
 148 {
 149     FILE *f = fopen("/tmp/col", "w");
 150     fprintf(f, "collision: %d\n", collision);
 151     fclose(f);
 152 }
 153 #endif
 154
 155 #define MAX_PACKED_NUMHASH 5
 156
 157 st_table*
 158 st_init_table_with_size(const struct st_hash_type *type, int size)
 159 {
 160     st_table *tbl;
 161
 162 #ifdef HASH_LOG
 163     if (init_st == 0) {
 164         init_st = 1;
 165         atexit(stat_col);
 166     }
 167 #endif
 168
 169     size = new_size(size);      /* round up to prime number */
 170
 171     tbl = alloc(st_table);
 172     tbl->type = type;
 173     tbl->num_entries = 0;
 174     tbl->entries_packed = type == &type_numhash && size/2 <= MAX_PACKED_NUMHASH;
 175     tbl->num_bins = size;
 176     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
 177     tbl->head = 0;
 178
 179     return tbl;
 180 }
 181
 182 st_table*
 183 st_init_table(const struct st_hash_type *type)
 184 {
 185     return st_init_table_with_size(type, 0);
 186 }
 187
 188 st_table*
 189 st_init_numtable(void)
 190 {
 191     return st_init_table(&type_numhash);
 192 }
 193
 194 st_table*
 195 st_init_numtable_with_size(int size)
 196 {
 197     return st_init_table_with_size(&type_numhash, size);
 198 }
 199
 200 st_table*
 201 st_init_strtable(void)
 202 {
 203     return st_init_table(&type_strhash);
 204 }
 205
 206 st_table*
 207 st_init_strtable_with_size(int size)
 208 {
 209     return st_init_table_with_size(&type_strhash, size);
 210 }
 211
 212 st_table*
 213 st_init_strcasetable(void)
 214 {
 215     return st_init_table(&type_strcasehash);
 216 }
 217
 218 st_table*
 219 st_init_strcasetable_with_size(int size)
 220 {
 221     return st_init_table_with_size(&type_strcasehash, size);
 222 }
 223
 224 void
 225 st_clear(st_table *table)
 226 {
 227     register st_table_entry *ptr, *next;
 228     int i;
 229
 230     if (table->entries_packed) {
 231         table->num_entries = 0;
 232         return;
 233     }
 234
 235     for(i = 0; i < table->num_bins; i++) {
 236         ptr = table->bins[i];
 237         table->bins[i] = 0;
 238         while (ptr != 0) {
 239             next = ptr->next;
 240             free(ptr);
 241             ptr = next;
 242         }
 243     }
 244     table->num_entries = 0;
 245     table->head = 0;
 246 }
 247
 248 void
 249 st_free_table(st_table *table)
 250 {
 251     st_clear(table);
 252     free(table->bins);
 253     free(table);
 254 }
 255
 256 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
 257 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
 258
 259 #ifdef HASH_LOG
 260 #define COLLISION collision++
 261 #else
 262 #define COLLISION
 263 #endif
 264
 265 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
 266     bin_pos = hash_val%(table)->num_bins;\
 267     ptr = (table)->bins[bin_pos];\
 268     if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
 269         COLLISION;\
 270         while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
 271             ptr = ptr->next;\
 272         }\
 273         ptr = ptr->next;\
 274     }\
 275 } while (0)
 276
 277 int
 278 st_lookup(st_table *table, register st_data_t key, st_data_t *value)
 279 {
 280     unsigned int hash_val, bin_pos;
 281     register st_table_entry *ptr;
 282
 283     if (table->entries_packed) {
 284         int i;
 285         for (i = 0; i < table->num_entries; i++) {
 286             if ((st_data_t)table->bins[i*2] == key) {
 287                 if (value !=0) *value = (st_data_t)table->bins[i*2+1];
 288                 return 1;
 289             }
 290         }
 291         return 0;
 292     }
 293
 294     hash_val = do_hash(key, table);
 295     FIND_ENTRY(table, ptr, hash_val, bin_pos);
 296
 297     if (ptr == 0) {
 298         return 0;
 299     }
 300     else {
 301         if (value != 0)  *value = ptr->record;
 302         return 1;
 303     }
 304 }
 305
 306 int
 307 st_get_key(st_table *table, register st_data_t key, st_data_t *result)
 308 {
 309     unsigned int hash_val, bin_pos;
 310     register st_table_entry *ptr;
 311
 312     if (table->entries_packed) {
 313         int i;
 314         for (i = 0; i < table->num_entries; i++) {
 315             if ((st_data_t)table->bins[i*2] == key) {
 316                 if (result !=0) *result = (st_data_t)table->bins[i*2];
 317                 return 1;
 318             }
 319         }
 320         return 0;
 321     }
 322
 323     hash_val = do_hash(key, table);
 324     FIND_ENTRY(table, ptr, hash_val, bin_pos);
 325
 326     if (ptr == 0) {
 327         return 0;
 328     }
 329     else {
 330         if (result != 0)  *result = ptr->key;
 331         return 1;
 332     }
 333 }
 334
 335 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
 336 do {\
 337     st_table_entry *entry, *head;\
 338     if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
 339         rehash(table);\
 340         bin_pos = hash_val % table->num_bins;\
 341     }\
 342     \
 343     entry = alloc(st_table_entry);\
 344     \
 345     entry->hash = hash_val;\
 346     entry->key = key;\
 347     entry->record = value;\
 348     entry->next = table->bins[bin_pos];\
 349     if ((head = table->head) != 0) {\
 350         entry->fore = head;\
 351         (entry->back = head->back)->fore = entry;\
 352         head->back = entry;\
 353     }\
 354     else {\
 355         table->head = entry->fore = entry->back = entry;\
 356     }\
 357     table->bins[bin_pos] = entry;\
 358     table->num_entries++;\
 359 } while (0)
 360
 361 static void
 362 unpack_entries(register st_table *table)
 363 {
 364     int i;
 365     struct st_table_entry *packed_bins[MAX_PACKED_NUMHASH*2];
 366     int num_entries = table->num_entries;
 367
 368     memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * num_entries*2);
 369     table->entries_packed = 0;
 370     table->num_entries = 0;
 371     memset(table->bins, 0, sizeof(struct st_table_entry *) * table->num_bins);
 372     for (i = 0; i < num_entries; i++) {
 373         st_insert(table, (st_data_t)packed_bins[i*2], (st_data_t)packed_bins[i*2+1]);
 374     }
 375 }
 376
 377 int
 378 st_insert(register st_table *table, register st_data_t key, st_data_t value)
 379 {
 380     unsigned int hash_val, bin_pos;
 381     register st_table_entry *ptr;
 382
 383     if (table->entries_packed) {
 384         int i;
 385         for (i = 0; i < table->num_entries; i++) {
 386             if ((st_data_t)table->bins[i*2] == key) {
 387                 table->bins[i*2+1] = (struct st_table_entry*)value;
 388                 return 1;
 389             }
 390         }
 391         if ((table->num_entries+1) * 2 <= table->num_bins && table->num_entries+1 <= MAX_PACKED_NUMHASH) {
 392             i = table->num_entries++;
 393             table->bins[i*2] = (struct st_table_entry*)key;
 394             table->bins[i*2+1] = (struct st_table_entry*)value;
 395             return 0;
 396         }
 397         else {
 398             unpack_entries(table);
 399         }
 400     }
 401
 402     hash_val = do_hash(key, table);
 403     FIND_ENTRY(table, ptr, hash_val, bin_pos);
 404
 405     if (ptr == 0) {
 406         ADD_DIRECT(table, key, value, hash_val, bin_pos);
 407         return 0;
 408     }
 409     else {
 410         ptr->record = value;
 411         return 1;
 412     }
 413 }
 414
 415 void
 416 st_add_direct(st_table *table, st_data_t key, st_data_t value)
 417 {
 418     unsigned int hash_val, bin_pos;
 419
 420     if (table->entries_packed) {
 421         int i;
 422         if ((table->num_entries+1) * 2 <= table->num_bins && table->num_entries+1 <= MAX_PACKED_NUMHASH) {
 423             i = table->num_entries++;
 424             table->bins[i*2] = (struct st_table_entry*)key;
 425             table->bins[i*2+1] = (struct st_table_entry*)value;
 426             return;
 427         }
 428         else {
 429             unpack_entries(table);
 430         }
 431     }
 432
 433     hash_val = do_hash(key, table);
 434     bin_pos = hash_val % table->num_bins;
 435     ADD_DIRECT(table, key, value, hash_val, bin_pos);
 436 }
 437
 438 static void
 439 rehash(register st_table *table)
 440 {
 441     register st_table_entry *ptr, **new_bins;
 442     int i, new_num_bins;
 443     unsigned int hash_val;
 444
 445     new_num_bins = new_size(table->num_bins+1);
 446     new_bins = (st_table_entry**)
 447         xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*));
 448     for (i = 0; i < new_num_bins; ++i) new_bins[i] = 0;
 449     table->num_bins = new_num_bins;
 450     table->bins = new_bins;
 451
 452     if ((ptr = table->head) != 0) {
 453         do {
 454             hash_val = ptr->hash % new_num_bins;
 455             ptr->next = new_bins[hash_val];
 456             new_bins[hash_val] = ptr;
 457         } while ((ptr = ptr->fore) != table->head);
 458     }
 459 }
 460
 461 st_table*
 462 st_copy(st_table *old_table)
 463 {
 464     st_table *new_table;
 465     st_table_entry *ptr, *entry, *prev, **tail;
 466     int num_bins = old_table->num_bins;
 467     unsigned int hash_val;
 468
 469     new_table = alloc(st_table);
 470     if (new_table == 0) {
 471         return 0;
 472     }
 473
 474     *new_table = *old_table;
 475     new_table->bins = (st_table_entry**)
 476         Calloc((unsigned)num_bins, sizeof(st_table_entry*));
 477
 478     if (new_table->bins == 0) {
 479         free(new_table);
 480         return 0;
 481     }
 482
 483     if (old_table->entries_packed) {
 484         memcpy(new_table->bins, old_table->bins, sizeof(struct st_table_entry *) * old_table->num_bins);
 485         return new_table;
 486     }
 487
 488     if ((ptr = old_table->head) != 0) {
 489         prev = 0;
 490         tail = &new_table->head;
 491         do {
 492             entry = alloc(st_table_entry);
 493             if (entry == 0) {
 494                 st_free_table(new_table);
 495                 return 0;
 496             }
 497             *entry = *ptr;
 498             hash_val = entry->hash % num_bins;
 499             entry->next = new_table->bins[hash_val];
 500             new_table->bins[hash_val] = entry;
 501             entry->back = prev;
 502             *tail = prev = entry;
 503             tail = &entry->fore;
 504         } while ((ptr = ptr->fore) != old_table->head);
 505         entry = new_table->head;
 506         entry->back = prev;
 507         *tail = entry;
 508     }
 509
 510     return new_table;
 511 }
 512
 513 #define REMOVE_ENTRY(table, ptr) do                                     \
 514     {                                                                   \
 515         if (ptr == ptr->fore) {                                         \
 516             table->head = 0;                                            \
 517         }                                                               \
 518         else {                                                          \
 519             st_table_entry *fore = ptr->fore, *back = ptr->back;        \
 520             fore->back = back;                                          \
 521             back->fore = fore;                                          \
 522             if (ptr == table->head) table->head = fore;                 \
 523         }                                                               \
 524         table->num_entries--;                                           \
 525     } while (0)
 526
 527 int
 528 st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
 529 {
 530     unsigned int hash_val;
 531     st_table_entry **prev;
 532     register st_table_entry *ptr;
 533
 534     if (table->entries_packed) {
 535         int i;
 536         for (i = 0; i < table->num_entries; i++) {
 537             if ((st_data_t)table->bins[i*2] == *key) {
 538                 if (value != 0) *value = (st_data_t)table->bins[i*2+1];
 539                 table->num_entries--;
 540                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
 541                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
 542                 return 1;
 543             }
 544         }
 545         if (value != 0) *value = 0;
 546         return 0;
 547     }
 548
 549     hash_val = do_hash_bin(*key, table);
 550
 551     for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) {
 552         if (EQUAL(table, *key, ptr->key)) {
 553             *prev = ptr->next;
 554             REMOVE_ENTRY(table, ptr);
 555             if (value != 0) *value = ptr->record;
 556             *key = ptr->key;
 557             free(ptr);
 558             return 1;
 559         }
 560     }
 561
 562     if (value != 0) *value = 0;
 563     return 0;
 564 }
 565
 566 int
 567 st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never)
 568 {
 569     unsigned int hash_val;
 570     register st_table_entry *ptr;
 571
 572     hash_val = do_hash_bin(*key, table);
 573     ptr = table->bins[hash_val];
 574
 575     for (; ptr != 0; ptr = ptr->next) {
 576         if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
 577             REMOVE_ENTRY(table, ptr);
 578             *key = ptr->key;
 579             if (value != 0) *value = ptr->record;
 580             ptr->key = ptr->record = never;
 581             return 1;
 582         }
 583     }
 584
 585     if (value != 0) *value = 0;
 586     return 0;
 587 }
 588
 589 void
 590 st_cleanup_safe(st_table *table, st_data_t never)
 591 {
 592     st_table_entry *ptr, **last, *tmp;
 593     int i;
 594
 595     for (i = 0; i < table->num_bins; i++) {
 596         ptr = *(last = &table->bins[i]);
 597         while (ptr != 0) {
 598             if (ptr->key == never) {
 599                 tmp = ptr;
 600                 *last = ptr = ptr->next;
 601                 free(tmp);
 602             }
 603             else {
 604                 ptr = *(last = &ptr->next);
 605             }
 606         }
 607     }
 608 }
 609
 610 int
 611 st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 612 {
 613     st_table_entry *ptr, **last, *tmp;
 614     enum st_retval retval;
 615     int i, end;
 616
 617     if (table->entries_packed) {
 618         for (i = 0; i < table->num_entries; i++) {
 619             int j;
 620             st_data_t key, val;
 621             key = (st_data_t)table->bins[i*2];
 622             val = (st_data_t)table->bins[i*2+1];
 623             retval = (*func)(key, val, arg);
 624             switch (retval) {
 625               case ST_CHECK:    /* check if hash is modified during iteration */
 626                 for (j = 0; j < table->num_entries; j++) {
 627                     if ((st_data_t)table->bins[j*2] == key)
 628                         break;
 629                 }
 630                 if (j == table->num_entries) {
 631                     /* call func with error notice */
 632                     retval = (*func)(0, 0, arg, 1);
 633                     return 1;
 634                 }
 635                 /* fall through */
 636               case ST_CONTINUE:
 637                 break;
 638               case ST_STOP:
 639                 return 0;
 640               case ST_DELETE:
 641                 table->num_entries--;
 642                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
 643                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
 644                 i--;
 645                 break;
 646             }
 647         }
 648         return 0;
 649     }
 650
 651     if ((ptr = table->head) != 0) {
 652         do {
 653             end = ptr->fore == table->head;
 654             retval = (*func)(ptr->key, ptr->record, arg);
 655             switch (retval) {
 656               case ST_CHECK:    /* check if hash is modified during iteration */
 657                 i = ptr->hash % table->num_bins;
 658                 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
 659                     if (!tmp) {
 660                         /* call func with error notice */
 661                         retval = (*func)(0, 0, arg, 1);
 662                         return 1;
 663                     }
 664                 }
 665                 /* fall through */
 666               case ST_CONTINUE:
 667                 ptr = ptr->fore;
 668                 break;
 669               case ST_STOP:
 670                 return 0;
 671               case ST_DELETE:
 672                 last = &table->bins[ptr->hash % table->num_bins];
 673                 for (; (tmp = *last) != 0; last = &tmp->next) {
 674                     if (ptr == tmp) {
 675                         tmp = ptr->fore;
 676                         *last = ptr->next;
 677                         REMOVE_ENTRY(table, ptr);
 678                         free(ptr);
 679                         if (ptr == tmp) return 0;
 680                         ptr = tmp;
 681                         break;
 682                     }
 683                 }
 684             }
 685         } while (!end && table->head);
 686     }
 687     return 0;
 688 }
 689
 690 #if 0  /* unused right now */
 691 int
 692 st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 693 {
 694     st_table_entry *ptr, **last, *tmp;
 695     enum st_retval retval;
 696     int i, end;
 697
 698     if (table->entries_packed) {
 699         for (i = table->num_entries-1; 0 <= i; i--) {
 700             int j;
 701             st_data_t key, val;
 702             key = (st_data_t)table->bins[i*2];
 703             val = (st_data_t)table->bins[i*2+1];
 704             retval = (*func)(key, val, arg);
 705             switch (retval) {
 706               case ST_CHECK:    /* check if hash is modified during iteration */
 707                 for (j = 0; j < table->num_entries; j++) {
 708                     if ((st_data_t)table->bins[j*2] == key)
 709                         break;
 710                 }
 711                 if (j == table->num_entries) {
 712                     /* call func with error notice */
 713                     retval = (*func)(0, 0, arg, 1);
 714                     return 1;
 715                 }
 716                 /* fall through */
 717               case ST_CONTINUE:
 718                 break;
 719               case ST_STOP:
 720                 return 0;
 721               case ST_DELETE:
 722                 table->num_entries--;
 723                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
 724                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
 725                 break;
 726             }
 727         }
 728         return 0;
 729     }
 730
 731     if ((ptr = table->head) != 0) {
 732         ptr = ptr->back;
 733         do {
 734             end = ptr == table->head;
 735             retval = (*func)(ptr->key, ptr->record, arg, 0);
 736             switch (retval) {
 737               case ST_CHECK:    /* check if hash is modified during iteration */
 738                 i = ptr->hash % table->num_bins;
 739                 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
 740                     if (!tmp) {
 741                         /* call func with error notice */
 742                         retval = (*func)(0, 0, arg, 1);
 743                         return 1;
 744                     }
 745                 }
 746                 /* fall through */
 747               case ST_CONTINUE:
 748                 ptr = ptr->back;
 749                 break;
 750               case ST_STOP:
 751                 return 0;
 752               case ST_DELETE:
 753                 last = &table->bins[ptr->hash % table->num_bins];
 754                 for (; (tmp = *last) != 0; last = &tmp->next) {
 755                     if (ptr == tmp) {
 756                         tmp = ptr->back;
 757                         *last = ptr->next;
 758                         REMOVE_ENTRY(table, ptr);
 759                         free(ptr);
 760                         ptr = tmp;
 761                         break;
 762                     }
 763                 }
 764                 ptr = ptr->next;
 765                 free(tmp);
 766                 table->num_entries--;
 767             }
 768         } while (!end && table->head);
 769     }
 770     return 0;
 771 }
 772 #endif
 773
 774 /*
 775  * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code
 776  *
 777  * @(#) $Hash32: Revision: 1.1 $
 778  * @(#) $Hash32: Id: hash_32a.c,v 1.1 2003/10/03 20:38:53 chongo Exp $
 779  * @(#) $Hash32: Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $
 780  *
 781  ***
 782  *
 783  * Fowler/Noll/Vo hash
 784  *
 785  * The basis of this hash algorithm was taken from an idea sent
 786  * as reviewer comments to the IEEE POSIX P1003.2 committee by:
 787  *
 788  *      Phong Vo (http://www.research.att.com/info/kpv/)
 789  *      Glenn Fowler (http://www.research.att.com/~gsf/)
 790  *
 791  * In a subsequent ballot round:
 792  *
 793  *      Landon Curt Noll (http://www.isthe.com/chongo/)
 794  *
 795  * improved on their algorithm.  Some people tried this hash
 796  * and found that it worked rather well.  In an EMail message
 797  * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
 798  *
 799  * FNV hashes are designed to be fast while maintaining a low
 800  * collision rate. The FNV speed allows one to quickly hash lots
 801  * of data while maintaining a reasonable collision rate.  See:
 802  *
 803  *      http://www.isthe.com/chongo/tech/comp/fnv/index.html
 804  *
 805  * for more details as well as other forms of the FNV hash.
 806  ***
 807  *
 808  * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the
 809  * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str().
 810  *
 811  ***
 812  *
 813  * Please do not copyright this code.  This code is in the public domain.
 814  *
 815  * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 816  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
 817  * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 818  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
 819  * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
 820  * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 821  * PERFORMANCE OF THIS SOFTWARE.
 822  *
 823  * By:
 824  *      chongo <Landon Curt Noll> /\oo/\
 825  *      http://www.isthe.com/chongo/
 826  *
 827  * Share and Enjoy!     :-)
 828  */
 829
 830 /*
 831  * 32 bit FNV-1 and FNV-1a non-zero initial basis
 832  *
 833  * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets:
 834  *
 835  *              chongo <Landon Curt Noll> /\../\
 836  *
 837  * NOTE: The \'s above are not back-slashing escape characters.
 838  * They are literal ASCII  backslash 0x5c characters.
 839  *
 840  * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition.
 841  */
 842 #define FNV1_32A_INIT 0x811c9dc5
 843
 844 /*
 845  * 32 bit magic FNV-1a prime
 846  */
 847 #define FNV_32_PRIME 0x01000193
 848
 849 static int
 850 strhash(register const char *string)
 851 {
 852     register unsigned int hval = FNV1_32A_INIT;
 853
 854     /*
 855      * FNV-1a hash each octet in the buffer
 856      */
 857     while (*string) {
 858         /* xor the bottom with the current octet */
 859         hval ^= (unsigned int)*string++;
 860
 861         /* multiply by the 32 bit FNV magic prime mod 2^32 */
 862         hval *= FNV_32_PRIME;
 863     }
 864     return hval;
 865 }
 866
 867 int
 868 st_strcasecmp(const char *s1, const char *s2)
 869 {
 870     unsigned int c1, c2;
 871
 872     while (1) {
 873         c1 = (unsigned char)*s1++;
 874         c2 = (unsigned char)*s2++;
 875         if (c1 == '\0' || c2 == '\0') {
 876             if (c1 != '\0') return 1;
 877             if (c2 != '\0') return -1;
 878             return 0;
 879         }
 880         if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
 881         if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
 882         if (c1 != c2) {
 883             if (c1 > c2)
 884                 return 1;
 885             else
 886                 return -1;
 887         }
 888     }
 889 }
 890
 891 int
 892 st_strncasecmp(const char *s1, const char *s2, size_t n)
 893 {
 894     unsigned int c1, c2;
 895
 896     while (n--) {
 897         c1 = (unsigned char)*s1++;
 898         c2 = (unsigned char)*s2++;
 899         if (c1 == '\0' || c2 == '\0') {
 900             if (c1 != '\0') return 1;
 901             if (c2 != '\0') return -1;
 902             return 0;
 903         }
 904         if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
 905         if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
 906         if (c1 != c2) {
 907             if (c1 > c2)
 908                 return 1;
 909             else
 910                 return -1;
 911         }
 912     }
 913     return 0;
 914 }
 915
 916 static int
 917 strcasehash(register const char *string)
 918 {
 919     register unsigned int hval = FNV1_32A_INIT;
 920
 921     /*
 922      * FNV-1a hash each octet in the buffer
 923      */
 924     while (*string) {
 925         unsigned int c = (unsigned char)*string++;
 926         if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A';
 927         hval ^= c;
 928
 929         /* multiply by the 32 bit FNV magic prime mod 2^32 */
 930         hval *= FNV_32_PRIME;
 931     }
 932     return hval;
 933 }
 934
 935 int
 936 st_numcmp(st_data_t x, st_data_t y)
 937 {
 938     return x != y;
 939 }
 940
 941 int
 942 st_numhash(st_data_t n)
 943 {
 944     return (int)n;
 945 }