MdeModulePkg RegularExpressionDxe: Update Oniguruma to 6.9.0

[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
      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(void)\r
{\r
  FILE *f = fopen("/tmp/col", "w");\r
  if (f == 0) return ;\r
\r
  (void) fprintf(f, "collision: %d\n", collision);\r
  (void) 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
  if (tbl == 0) return 0;\r
\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
  if (tbl->bins == 0) {\r
    free(tbl);\r
    return 0;\r
  }\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, ret) \\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
  entry = alloc(st_table_entry);\\r
  if (IS_NULL(entry)) return ret;\\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, ONIGERR_MEMORY);\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 == 0) {\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