root/ext/mbstring/oniguruma/st.c

DEFINITIONS

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