MdeModulePkg: Delete useless case code

[mirror_edk2.git] / MdeModulePkg / Universal / RegularExpressionDxe / Oniguruma / st.c

/* 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
    CHECK_NULL_RETURN(tbl);\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
    if (entry == NULL) {\\r
      break;\\r
    }\\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
    if (new_bins == NULL) {\r
      return;\r
    }\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