1. new_size
2. stat_col
3. st_init_table_with_size
4. st_init_table
5. st_init_numtable
6. st_init_numtable_with_size
7. st_init_strtable
8. st_init_strtable_with_size
9. st_free_table
10. st_lookup
11. st_insert
12. st_add_direct
13. rehash
14. st_copy
15. st_delete
16. st_delete_safe
17. delete_never
18. st_cleanup_safe
19. st_foreach
20. strhash
21. numcmp
22. numhash

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