+++ /dev/null
-/* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */\r
-\r
-/* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */\r
-\r
-//#include <stdio.h>\r
-//#include <stdlib.h>\r
-//#include <string.h>\r
-#include "OnigurumaUefiPort.h"\r
-\r
-#ifdef _WIN32\r
-#include <malloc.h>\r
-#endif\r
-\r
-#include "regint.h"\r
-#include "st.h"\r
-\r
-typedef struct st_table_entry st_table_entry;\r
-\r
-struct st_table_entry {\r
- unsigned int hash;\r
- st_data_t key;\r
- st_data_t record;\r
- st_table_entry *next;\r
-};\r
-\r
-#define ST_DEFAULT_MAX_DENSITY 5\r
-#define ST_DEFAULT_INIT_TABLE_SIZE 11\r
-\r
- /*\r
- * DEFAULT_MAX_DENSITY is the default for the largest we allow the\r
- * average number of items per bin before increasing the number of\r
- * bins\r
- *\r
- * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins\r
- * allocated initially\r
- *\r
- */\r
-\r
-static int numcmp(long, long);\r
-static int numhash(long);\r
-static struct st_hash_type type_numhash = {\r
- numcmp,\r
- numhash,\r
-};\r
-\r
-/* extern int strcmp(const char *, const char *); */\r
-static int strhash(const char *);\r
-static struct st_hash_type type_strhash = {\r
- strcmp,\r
- strhash,\r
-};\r
-\r
-static void rehash(st_table *);\r
-\r
-#define alloc(type) (type*)xmalloc((unsigned)sizeof(type))\r
-#define Calloc(n,s) (char*)xcalloc((n),(s))\r
-\r
-#define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)\r
-\r
-#define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))\r
-#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)\r
-\r
-/*\r
- * MINSIZE is the minimum size of a dictionary.\r
- */\r
-\r
-#define MINSIZE 8\r
-\r
-/*\r
-Table of prime numbers 2^n+a, 2<=n<=30.\r
-*/\r
-static const long primes[] = {\r
- 8 + 3,\r
- 16 + 3,\r
- 32 + 5,\r
- 64 + 3,\r
- 128 + 3,\r
- 256 + 27,\r
- 512 + 9,\r
- 1024 + 9,\r
- 2048 + 5,\r
- 4096 + 3,\r
- 8192 + 27,\r
- 16384 + 43,\r
- 32768 + 3,\r
- 65536 + 45,\r
- 131072 + 29,\r
- 262144 + 3,\r
- 524288 + 21,\r
- 1048576 + 7,\r
- 2097152 + 17,\r
- 4194304 + 15,\r
- 8388608 + 9,\r
- 16777216 + 43,\r
- 33554432 + 35,\r
- 67108864 + 15,\r
- 134217728 + 29,\r
- 268435456 + 3,\r
- 536870912 + 11,\r
- 1073741824 + 85,\r
- 0\r
-};\r
-\r
-static int\r
-new_size(size)\r
- int size;\r
-{\r
- int i;\r
-\r
-#if 0\r
- for (i=3; i<31; i++) {\r
- if ((1<<i) > size) return 1<<i;\r
- }\r
- return -1;\r
-#else\r
- int newsize;\r
-\r
- for (i = 0, newsize = MINSIZE;\r
- i < (int )(sizeof(primes)/sizeof(primes[0]));\r
- i++, newsize <<= 1)\r
- {\r
- if (newsize > size) return primes[i];\r
- }\r
- /* Ran out of polynomials */\r
- return -1; /* should raise exception */\r
-#endif\r
-}\r
-\r
-#ifdef HASH_LOG\r
-static int collision = 0;\r
-static int init_st = 0;\r
-\r
-static void\r
-stat_col()\r
-{\r
- FILE *f = fopen("/tmp/col", "w");\r
- fprintf(f, "collision: %d\n", collision);\r
- fclose(f);\r
-}\r
-#endif\r
-\r
-st_table*\r
-st_init_table_with_size(type, size)\r
- struct st_hash_type *type;\r
- int size;\r
-{\r
- st_table *tbl;\r
-\r
-#ifdef HASH_LOG\r
- if (init_st == 0) {\r
- init_st = 1;\r
- atexit(stat_col);\r
- }\r
-#endif\r
-\r
- size = new_size(size); /* round up to prime number */\r
-\r
- tbl = alloc(st_table);\r
- tbl->type = type;\r
- tbl->num_entries = 0;\r
- tbl->num_bins = size;\r
- tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));\r
-\r
- return tbl;\r
-}\r
-\r
-st_table*\r
-st_init_table(type)\r
- struct st_hash_type *type;\r
-{\r
- return st_init_table_with_size(type, 0);\r
-}\r
-\r
-st_table*\r
-st_init_numtable(void)\r
-{\r
- return st_init_table(&type_numhash);\r
-}\r
-\r
-st_table*\r
-st_init_numtable_with_size(size)\r
- int size;\r
-{\r
- return st_init_table_with_size(&type_numhash, size);\r
-}\r
-\r
-st_table*\r
-st_init_strtable(void)\r
-{\r
- return st_init_table(&type_strhash);\r
-}\r
-\r
-st_table*\r
-st_init_strtable_with_size(size)\r
- int size;\r
-{\r
- return st_init_table_with_size(&type_strhash, size);\r
-}\r
-\r
-void\r
-st_free_table(table)\r
- st_table *table;\r
-{\r
- register st_table_entry *ptr, *next;\r
- int i;\r
-\r
- for(i = 0; i < table->num_bins; i++) {\r
- ptr = table->bins[i];\r
- while (ptr != 0) {\r
- next = ptr->next;\r
- free(ptr);\r
- ptr = next;\r
- }\r
- }\r
- free(table->bins);\r
- free(table);\r
-}\r
-\r
-#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \\r
-((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))\r
-\r
-#ifdef HASH_LOG\r
-#define COLLISION collision++\r
-#else\r
-#define COLLISION\r
-#endif\r
-\r
-#define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\\r
- bin_pos = hash_val%(table)->num_bins;\\r
- ptr = (table)->bins[bin_pos];\\r
- if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\\r
- COLLISION;\\r
- while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\\r
- ptr = ptr->next;\\r
- }\\r
- ptr = ptr->next;\\r
- }\\r
-} while (0)\r
-\r
-int\r
-st_lookup(table, key, value)\r
- st_table *table;\r
- register st_data_t key;\r
- st_data_t *value;\r
-{\r
- unsigned int hash_val, bin_pos;\r
- register st_table_entry *ptr;\r
-\r
- hash_val = do_hash(key, table);\r
- FIND_ENTRY(table, ptr, hash_val, bin_pos);\r
-\r
- if (ptr == 0) {\r
- return 0;\r
- }\r
- else {\r
- if (value != 0) *value = ptr->record;\r
- return 1;\r
- }\r
-}\r
-\r
-#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\\r
-do {\\r
- st_table_entry *entry;\\r
- if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\\r
- rehash(table);\\r
- bin_pos = hash_val % table->num_bins;\\r
- }\\r
- \\r
- entry = alloc(st_table_entry);\\r
- \\r
- entry->hash = hash_val;\\r
- entry->key = key;\\r
- entry->record = value;\\r
- entry->next = table->bins[bin_pos];\\r
- table->bins[bin_pos] = entry;\\r
- table->num_entries++;\\r
-} while (0)\r
-\r
-int\r
-st_insert(table, key, value)\r
- register st_table *table;\r
- register st_data_t key;\r
- st_data_t value;\r
-{\r
- unsigned int hash_val, bin_pos;\r
- register st_table_entry *ptr;\r
-\r
- hash_val = do_hash(key, table);\r
- FIND_ENTRY(table, ptr, hash_val, bin_pos);\r
-\r
- if (ptr == 0) {\r
- ADD_DIRECT(table, key, value, hash_val, bin_pos);\r
- return 0;\r
- }\r
- else {\r
- ptr->record = value;\r
- return 1;\r
- }\r
-}\r
-\r
-void\r
-st_add_direct(table, key, value)\r
- st_table *table;\r
- st_data_t key;\r
- st_data_t value;\r
-{\r
- unsigned int hash_val, bin_pos;\r
-\r
- hash_val = do_hash(key, table);\r
- bin_pos = hash_val % table->num_bins;\r
- ADD_DIRECT(table, key, value, hash_val, bin_pos);\r
-}\r
-\r
-static void\r
-rehash(table)\r
- register st_table *table;\r
-{\r
- register st_table_entry *ptr, *next, **new_bins;\r
- int i, old_num_bins = table->num_bins, new_num_bins;\r
- unsigned int hash_val;\r
-\r
- new_num_bins = new_size(old_num_bins+1);\r
- new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));\r
-\r
- for(i = 0; i < old_num_bins; i++) {\r
- ptr = table->bins[i];\r
- while (ptr != 0) {\r
- next = ptr->next;\r
- hash_val = ptr->hash % new_num_bins;\r
- ptr->next = new_bins[hash_val];\r
- new_bins[hash_val] = ptr;\r
- ptr = next;\r
- }\r
- }\r
- free(table->bins);\r
- table->num_bins = new_num_bins;\r
- table->bins = new_bins;\r
-}\r
-\r
-st_table*\r
-st_copy(old_table)\r
- st_table *old_table;\r
-{\r
- st_table *new_table;\r
- st_table_entry *ptr, *entry;\r
- int i, num_bins = old_table->num_bins;\r
-\r
- new_table = alloc(st_table);\r
- if (new_table == 0) {\r
- return 0;\r
- }\r
-\r
- *new_table = *old_table;\r
- new_table->bins = (st_table_entry**)\r
- Calloc((unsigned)num_bins, sizeof(st_table_entry*));\r
-\r
- if (new_table->bins == 0) {\r
- free(new_table);\r
- return 0;\r
- }\r
-\r
- for(i = 0; i < num_bins; i++) {\r
- new_table->bins[i] = 0;\r
- ptr = old_table->bins[i];\r
- while (ptr != 0) {\r
- entry = alloc(st_table_entry);\r
- if (entry == 0) {\r
- free(new_table->bins);\r
- free(new_table);\r
- return 0;\r
- }\r
- *entry = *ptr;\r
- entry->next = new_table->bins[i];\r
- new_table->bins[i] = entry;\r
- ptr = ptr->next;\r
- }\r
- }\r
- return new_table;\r
-}\r
-\r
-int\r
-st_delete(table, key, value)\r
- register st_table *table;\r
- register st_data_t *key;\r
- st_data_t *value;\r
-{\r
- unsigned int hash_val;\r
- st_table_entry *tmp;\r
- register st_table_entry *ptr;\r
-\r
- hash_val = do_hash_bin(*key, table);\r
- ptr = table->bins[hash_val];\r
-\r
- if (ptr == 0) {\r
- if (value != 0) *value = 0;\r
- return 0;\r
- }\r
-\r
- if (EQUAL(table, *key, ptr->key)) {\r
- table->bins[hash_val] = ptr->next;\r
- table->num_entries--;\r
- if (value != 0) *value = ptr->record;\r
- *key = ptr->key;\r
- free(ptr);\r
- return 1;\r
- }\r
-\r
- for(; ptr->next != 0; ptr = ptr->next) {\r
- if (EQUAL(table, ptr->next->key, *key)) {\r
- tmp = ptr->next;\r
- ptr->next = ptr->next->next;\r
- table->num_entries--;\r
- if (value != 0) *value = tmp->record;\r
- *key = tmp->key;\r
- free(tmp);\r
- return 1;\r
- }\r
- }\r
-\r
- return 0;\r
-}\r
-\r
-int\r
-st_delete_safe(table, key, value, never)\r
- register st_table *table;\r
- register st_data_t *key;\r
- st_data_t *value;\r
- st_data_t never;\r
-{\r
- unsigned int hash_val;\r
- register st_table_entry *ptr;\r
-\r
- hash_val = do_hash_bin(*key, table);\r
- ptr = table->bins[hash_val];\r
-\r
- if (ptr == 0) {\r
- if (value != 0) *value = 0;\r
- return 0;\r
- }\r
-\r
- for(; ptr != 0; ptr = ptr->next) {\r
- if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {\r
- table->num_entries--;\r
- *key = ptr->key;\r
- if (value != 0) *value = ptr->record;\r
- ptr->key = ptr->record = never;\r
- return 1;\r
- }\r
- }\r
-\r
- return 0;\r
-}\r
-\r
-static int\r
-#if defined(__GNUC__)\r
-delete_never(st_data_t key __attribute__ ((unused)), st_data_t value,\r
- st_data_t never)\r
-#else\r
-delete_never(key, value, never)\r
- st_data_t key, value, never;\r
-#endif\r
-{\r
- if (value == never) return ST_DELETE;\r
- return ST_CONTINUE;\r
-}\r
-\r
-void\r
-st_cleanup_safe(table, never)\r
- st_table *table;\r
- st_data_t never;\r
-{\r
- int num_entries = table->num_entries;\r
-\r
- st_foreach(table, delete_never, never);\r
- table->num_entries = num_entries;\r
-}\r
-\r
-int\r
-st_foreach(table, func, arg)\r
- st_table *table;\r
- int (*func)();\r
- st_data_t arg;\r
-{\r
- st_table_entry *ptr, *last, *tmp;\r
- enum st_retval retval;\r
- int i;\r
-\r
- for(i = 0; i < table->num_bins; i++) {\r
- last = 0;\r
- for(ptr = table->bins[i]; ptr != 0;) {\r
- retval = (*func)(ptr->key, ptr->record, arg);\r
- switch (retval) {\r
- case ST_CHECK: /* check if hash is modified during iteration */\r
- tmp = 0;\r
- if (i < table->num_bins) {\r
- for (tmp = table->bins[i]; tmp; tmp=tmp->next) {\r
- if (tmp == ptr) break;\r
- }\r
- }\r
- if (!tmp) {\r
- /* call func with error notice */\r
- return 1;\r
- }\r
- /* fall through */\r
- case ST_CONTINUE:\r
- last = ptr;\r
- ptr = ptr->next;\r
- break;\r
- case ST_STOP:\r
- return 0;\r
- case ST_DELETE:\r
- tmp = ptr;\r
- if (last == 0) {\r
- table->bins[i] = ptr->next;\r
- }\r
- else {\r
- last->next = ptr->next;\r
- }\r
- ptr = ptr->next;\r
- free(tmp);\r
- table->num_entries--;\r
- }\r
- }\r
- }\r
- return 0;\r
-}\r
-\r
-static int\r
-strhash(string)\r
- register const char *string;\r
-{\r
- register int c;\r
-\r
-#ifdef HASH_ELFHASH\r
- register unsigned int h = 0, g;\r
-\r
- while ((c = *string++) != '\0') {\r
- h = ( h << 4 ) + c;\r
- if ( g = h & 0xF0000000 )\r
- h ^= g >> 24;\r
- h &= ~g;\r
- }\r
- return h;\r
-#elif HASH_PERL\r
- register int val = 0;\r
-\r
- while ((c = *string++) != '\0') {\r
- val += c;\r
- val += (val << 10);\r
- val ^= (val >> 6);\r
- }\r
- val += (val << 3);\r
- val ^= (val >> 11);\r
-\r
- return val + (val << 15);\r
-#else\r
- register int val = 0;\r
-\r
- while ((c = *string++) != '\0') {\r
- val = val*997 + c;\r
- }\r
-\r
- return val + (val>>5);\r
-#endif\r
-}\r
-\r
-static int\r
-numcmp(x, y)\r
- long x, y;\r
-{\r
- return x != y;\r
-}\r
-\r
-static int\r
-numhash(n)\r
- long n;\r
-{\r
- return n;\r
-}\r
projects / mirror_edk2.git / blobdiff