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