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     tbl->type = type;
 160     tbl->num_entries = 0;
 161     tbl->num_bins = size;
 162     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
 163
 164     return tbl;
 165 }
 166
 167 st_table*
 168 st_init_table(type)
 169     struct st_hash_type *type;
 170 {
 171     return st_init_table_with_size(type, 0);
 172 }
 173
 174 st_table*
 175 st_init_numtable(void)
 176 {
 177     return st_init_table(&type_numhash);
 178 }
 179
 180 st_table*
 181 st_init_numtable_with_size(size)
 182     int size;
 183 {
 184     return st_init_table_with_size(&type_numhash, size);
 185 }
 186
 187 st_table*
 188 st_init_strtable(void)
 189 {
 190     return st_init_table(&type_strhash);
 191 }
 192
 193 st_table*
 194 st_init_strtable_with_size(size)
 195     int size;
 196 {
 197     return st_init_table_with_size(&type_strhash, size);
 198 }
 199
 200 void
 201 st_free_table(table)
 202     st_table *table;
 203 {
 204     register st_table_entry *ptr, *next;
 205     int i;
 206
 207     for(i = 0; i < table->num_bins; i++) {
 208         ptr = table->bins[i];
 209         while (ptr != 0) {
 210             next = ptr->next;
 211             free(ptr);
 212             ptr = next;
 213         }
 214     }
 215     free(table->bins);
 216     free(table);
 217 }
 218
 219 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
 220 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
 221
 222 #ifdef HASH_LOG
 223 #define COLLISION collision++
 224 #else
 225 #define COLLISION
 226 #endif
 227
 228 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
 229     bin_pos = hash_val%(table)->num_bins;\
 230     ptr = (table)->bins[bin_pos];\
 231     if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
 232         COLLISION;\
 233         while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
 234             ptr = ptr->next;\
 235         }\
 236         ptr = ptr->next;\
 237     }\
 238 } while (0)
 239
 240 int
 241 st_lookup(table, key, value)
 242     st_table *table;
 243     register st_data_t key;
 244     st_data_t *value;
 245 {
 246     unsigned int hash_val, bin_pos;
 247     register st_table_entry *ptr;
 248
 249     hash_val = do_hash(key, table);
 250     FIND_ENTRY(table, ptr, hash_val, bin_pos);
 251
 252     if (ptr == 0) {
 253         return 0;
 254     }
 255     else {
 256         if (value != 0)  *value = ptr->record;
 257         return 1;
 258     }
 259 }
 260
 261 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
 262 do {\
 263     st_table_entry *entry;\
 264     if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
 265         rehash(table);\
 266         bin_pos = hash_val % table->num_bins;\
 267     }\
 268     \
 269     entry = alloc(st_table_entry);\
 270     \
 271     entry->hash = hash_val;\
 272     entry->key = key;\
 273     entry->record = value;\
 274     entry->next = table->bins[bin_pos];\
 275     table->bins[bin_pos] = entry;\
 276     table->num_entries++;\
 277 } while (0)
 278
 279 int
 280 st_insert(table, key, value)
 281     register st_table *table;
 282     register st_data_t key;
 283     st_data_t value;
 284 {
 285     unsigned int hash_val, bin_pos;
 286     register st_table_entry *ptr;
 287
 288     hash_val = do_hash(key, table);
 289     FIND_ENTRY(table, ptr, hash_val, bin_pos);
 290
 291     if (ptr == 0) {
 292         ADD_DIRECT(table, key, value, hash_val, bin_pos);
 293         return 0;
 294     }
 295     else {
 296         ptr->record = value;
 297         return 1;
 298     }
 299 }
 300
 301 void
 302 st_add_direct(table, key, value)
 303     st_table *table;
 304     st_data_t key;
 305     st_data_t value;
 306 {
 307     unsigned int hash_val, bin_pos;
 308
 309     hash_val = do_hash(key, table);
 310     bin_pos = hash_val % table->num_bins;
 311     ADD_DIRECT(table, key, value, hash_val, bin_pos);
 312 }
 313
 314 static void
 315 rehash(table)
 316     register st_table *table;
 317 {
 318     register st_table_entry *ptr, *next, **new_bins;
 319     int i, old_num_bins = table->num_bins, new_num_bins;
 320     unsigned int hash_val;
 321
 322     new_num_bins = new_size(old_num_bins+1);
 323     new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
 324
 325     for(i = 0; i < old_num_bins; i++) {
 326         ptr = table->bins[i];
 327         while (ptr != 0) {
 328             next = ptr->next;
 329             hash_val = ptr->hash % new_num_bins;
 330             ptr->next = new_bins[hash_val];
 331             new_bins[hash_val] = ptr;
 332             ptr = next;
 333         }
 334     }
 335     free(table->bins);
 336     table->num_bins = new_num_bins;
 337     table->bins = new_bins;
 338 }
 339
 340 st_table*
 341 st_copy(old_table)
 342     st_table *old_table;
 343 {
 344     st_table *new_table;
 345     st_table_entry *ptr, *entry;
 346     int i, num_bins = old_table->num_bins;
 347
 348     new_table = alloc(st_table);
 349     if (new_table == 0) {
 350         return 0;
 351     }
 352
 353     *new_table = *old_table;
 354     new_table->bins = (st_table_entry**)
 355         Calloc((unsigned)num_bins, sizeof(st_table_entry*));
 356
 357     if (new_table->bins == 0) {
 358         free(new_table);
 359         return 0;
 360     }
 361
 362     for(i = 0; i < num_bins; i++) {
 363         new_table->bins[i] = 0;
 364         ptr = old_table->bins[i];
 365         while (ptr != 0) {
 366             entry = alloc(st_table_entry);
 367             if (entry == 0) {
 368                 free(new_table->bins);
 369                 free(new_table);
 370                 return 0;
 371             }
 372             *entry = *ptr;
 373             entry->next = new_table->bins[i];
 374             new_table->bins[i] = entry;
 375             ptr = ptr->next;
 376         }
 377     }
 378     return new_table;
 379 }
 380
 381 int
 382 st_delete(table, key, value)
 383     register st_table *table;
 384     register st_data_t *key;
 385     st_data_t *value;
 386 {
 387     unsigned int hash_val;
 388     st_table_entry *tmp;
 389     register st_table_entry *ptr;
 390
 391     hash_val = do_hash_bin(*key, table);
 392     ptr = table->bins[hash_val];
 393
 394     if (ptr == 0) {
 395         if (value != 0) *value = 0;
 396         return 0;
 397     }
 398
 399     if (EQUAL(table, *key, ptr->key)) {
 400         table->bins[hash_val] = ptr->next;
 401         table->num_entries--;
 402         if (value != 0) *value = ptr->record;
 403         *key = ptr->key;
 404         free(ptr);
 405         return 1;
 406     }
 407
 408     for(; ptr->next != 0; ptr = ptr->next) {
 409         if (EQUAL(table, ptr->next->key, *key)) {
 410             tmp = ptr->next;
 411             ptr->next = ptr->next->next;
 412             table->num_entries--;
 413             if (value != 0) *value = tmp->record;
 414             *key = tmp->key;
 415             free(tmp);
 416             return 1;
 417         }
 418     }
 419
 420     return 0;
 421 }
 422
 423 int
 424 st_delete_safe(table, key, value, never)
 425     register st_table *table;
 426     register st_data_t *key;
 427     st_data_t *value;
 428     st_data_t never;
 429 {
 430     unsigned int hash_val;
 431     register st_table_entry *ptr;
 432
 433     hash_val = do_hash_bin(*key, table);
 434     ptr = table->bins[hash_val];
 435
 436     if (ptr == 0) {
 437         if (value != 0) *value = 0;
 438         return 0;
 439     }
 440
 441     for(; ptr != 0; ptr = ptr->next) {
 442         if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
 443             table->num_entries--;
 444             *key = ptr->key;
 445             if (value != 0) *value = ptr->record;
 446             ptr->key = ptr->record = never;
 447             return 1;
 448         }
 449     }
 450
 451     return 0;
 452 }
 453
 454 static int
 455 #if defined(__GNUC__)
 456 delete_never(st_data_t key __attribute__ ((unused)), st_data_t value,
 457              st_data_t never)
 458 #else
 459 delete_never(key, value, never)
 460     st_data_t key, value, never;
 461 #endif
 462 {
 463     if (value == never) return ST_DELETE;
 464     return ST_CONTINUE;
 465 }
 466
 467 void
 468 st_cleanup_safe(table, never)
 469     st_table *table;
 470     st_data_t never;
 471 {
 472     int num_entries = table->num_entries;
 473
 474     st_foreach(table, delete_never, never);
 475     table->num_entries = num_entries;
 476 }
 477
 478 int
 479 st_foreach(table, func, arg)
 480     st_table *table;
 481     int (*func)();
 482     st_data_t arg;
 483 {
 484     st_table_entry *ptr, *last, *tmp;
 485     enum st_retval retval;
 486     int i;
 487
 488     for(i = 0; i < table->num_bins; i++) {
 489         last = 0;
 490         for(ptr = table->bins[i]; ptr != 0;) {
 491             retval = (*func)(ptr->key, ptr->record, arg);
 492             switch (retval) {
 493             case ST_CHECK:      /* check if hash is modified during iteration */
 494                 tmp = 0;
 495                 if (i < table->num_bins) {
 496                     for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
 497                         if (tmp == ptr) break;
 498                     }
 499                 }
 500                 if (!tmp) {
 501                     /* call func with error notice */
 502                     return 1;
 503                 }
 504                 /* fall through */
 505             case ST_CONTINUE:
 506                 last = ptr;
 507                 ptr = ptr->next;
 508                 break;
 509             case ST_STOP:
 510                 return 0;
 511             case ST_DELETE:
 512                 tmp = ptr;
 513                 if (last == 0) {
 514                     table->bins[i] = ptr->next;
 515                 }
 516                 else {
 517                     last->next = ptr->next;
 518                 }
 519                 ptr = ptr->next;
 520                 free(tmp);
 521                 table->num_entries--;
 522             }
 523         }
 524     }
 525     return 0;
 526 }
 527
 528 static int
 529 strhash(string)
 530     register const char *string;
 531 {
 532     register int c;
 533
 534 #ifdef HASH_ELFHASH
 535     register unsigned int h = 0, g;
 536
 537     while ((c = *string++) != '\0') {
 538         h = ( h << 4 ) + c;
 539         if ( g = h & 0xF0000000 )
 540             h ^= g >> 24;
 541         h &= ~g;
 542     }
 543     return h;
 544 #elif HASH_PERL
 545     register int val = 0;
 546
 547     while ((c = *string++) != '\0') {
 548         val += c;
 549         val += (val << 10);
 550         val ^= (val >> 6);
 551     }
 552     val += (val << 3);
 553     val ^= (val >> 11);
 554
 555     return val + (val << 15);
 556 #else
 557     register int val = 0;
 558
 559     while ((c = *string++) != '\0') {
 560         val = val*997 + c;
 561     }
 562
 563     return val + (val>>5);
 564 #endif
 565 }
 566
 567 static int
 568 numcmp(x, y)
 569     long x, y;
 570 {
 571     return x != y;
 572 }
 573
 574 static int
 575 numhash(n)
 576     long n;
 577 {
 578     return n;
 579 }