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