\r
#if 0\r
for (i=3; i<31; i++) {\r
- if ((1<<i) > size) return 1<<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
+ 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
static int init_st = 0;\r
\r
static void\r
-stat_col()\r
+stat_col(void)\r
{\r
- FILE *f = fopen("/tmp/col", "w");\r
- fprintf(f, "collision: %d\n", collision);\r
- fclose(f);\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
struct st_hash_type *type;\r
int size;\r
{\r
- st_table *tbl;\r
+ st_table *tbl;\r
\r
#ifdef HASH_LOG\r
- if (init_st == 0) {\r
- init_st = 1;\r
- atexit(stat_col);\r
- }\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
+ 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
+ tbl = alloc(st_table);\r
+ if (tbl == 0) return 0;\r
\r
- 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
+ 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
+ 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
+ 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
+ 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
+ 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
+ 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
+ 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
+ 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
+ free(table->bins);\r
+ free(table);\r
}\r
\r
#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \\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
+ 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
+ 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
+ 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
+ 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
+ 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
+#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
- \\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
+ 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
+ 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
+ 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
+ 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
+ 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
+ st_table *table;\r
+ st_data_t key;\r
+ st_data_t value;\r
{\r
- unsigned int hash_val, bin_pos;\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
+ 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
+ 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
+ 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
+ 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
+ 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
+ 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
+ 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
+ *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
+ 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
+ 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
+ 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
+ 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
+ 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
+ unsigned int hash_val;\r
+ st_table_entry *tmp;\r
+ register st_table_entry *ptr;\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
+ hash_val = do_hash_bin(*key, table);\r
+ ptr = table->bins[hash_val];\r
\r
- for(; ptr->next != 0; ptr = ptr->next) {\r
- if (EQUAL(table, ptr->next->key, *key)) {\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
*key = tmp->key;\r
free(tmp);\r
return 1;\r
- }\r
}\r
+ }\r
\r
- return 0;\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
+ 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
+ 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
+ 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
+ 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
+ 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
\r
- return 0;\r
+ return 0;\r
}\r
\r
static int\r
\r
void\r
st_cleanup_safe(table, never)\r
- st_table *table;\r
- st_data_t never;\r
+ st_table *table;\r
+ st_data_t never;\r
{\r
- int num_entries = table->num_entries;\r
+ int num_entries = table->num_entries;\r
\r
- st_foreach(table, delete_never, never);\r
- table->num_entries = num_entries;\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
+ 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
+ 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
+ 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
+ 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
+ last = ptr;\r
+ ptr = ptr->next;\r
+ break;\r
case ST_STOP:\r
- return 0;\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
+ 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
+ return 0;\r
}\r
\r
static int\r
strhash(string)\r
- register const char *string;\r
+ register const char *string;\r
{\r
- register int c;\r
+ register int c;\r
\r
#ifdef HASH_ELFHASH\r
- register unsigned int h = 0, g;\r
+ register unsigned int h = 0, g;\r
\r
- while ((c = *string++) != '\0') {\r
- h = ( h << 4 ) + c;\r
- if ( g = h & 0xF0000000 )\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
+ h &= ~g;\r
+ }\r
+ return h;\r
#elif HASH_PERL\r
- register int val = 0;\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
+ 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
+ return val + (val << 15);\r
#else\r
- register int val = 0;\r
+ register int val = 0;\r
\r
- while ((c = *string++) != '\0') {\r
- val = val*997 + c;\r
- }\r
+ while ((c = *string++) != '\0') {\r
+ val = val*997 + c;\r
+ }\r
\r
- return val + (val>>5);\r
+ return val + (val>>5);\r
#endif\r
}\r
\r
static int\r
numcmp(x, y)\r
- long x, y;\r
+ long x, y;\r
{\r
- return x != y;\r
+ return x != y;\r
}\r
\r
static int\r
numhash(n)\r
- long n;\r
+ long n;\r
{\r
- return n;\r
+ return n;\r
}\r
projects / mirror_edk2.git / blobdiff