1 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
3 /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
8 #include "OnigurumaUefiPort.h"
17 typedef struct st_table_entry st_table_entry
;
19 struct st_table_entry
{
26 #define ST_DEFAULT_MAX_DENSITY 5
27 #define ST_DEFAULT_INIT_TABLE_SIZE 11
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
34 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
39 static int numcmp(long, long);
40 static int numhash(long);
41 static struct st_hash_type type_numhash
= {
46 /* extern int strcmp(const char *, const char *); */
47 static int strhash(const char *);
48 static struct st_hash_type type_strhash
= {
53 static void rehash(st_table
*);
55 #define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
56 #define Calloc(n,s) (char*)xcalloc((n),(s))
58 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
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)
64 * MINSIZE is the minimum size of a dictionary.
70 Table of prime numbers 2^n+a, 2<=n<=30.
72 static const long primes
[] = {
111 for (i
=3; i
<31; i
++) {
112 if ((1<<i
) > size
) return 1<<i
;
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
];
123 /* Ran out of polynomials */
124 return -1; /* should raise exception */
129 static int collision
= 0;
130 static int init_st
= 0;
135 FILE *f
= fopen("/tmp/col", "w");
138 (void) fprintf(f
, "collision: %d\n", collision
);
144 st_init_table_with_size(type
, size
)
145 struct st_hash_type
*type
;
157 size
= new_size(size
); /* round up to prime number */
159 tbl
= alloc(st_table
);
160 if (tbl
== 0) return 0;
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) {
176 struct st_hash_type
*type
;
178 return st_init_table_with_size(type
, 0);
182 st_init_numtable(void)
184 return st_init_table(&type_numhash
);
188 st_init_numtable_with_size(size
)
191 return st_init_table_with_size(&type_numhash
, size
);
195 st_init_strtable(void)
197 return st_init_table(&type_strhash
);
201 st_init_strtable_with_size(size
)
204 return st_init_table_with_size(&type_strhash
, size
);
211 register st_table_entry
*ptr
, *next
;
214 for(i
= 0; i
< table
->num_bins
; i
++) {
215 ptr
= table
->bins
[i
];
226 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
227 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
230 #define COLLISION collision++
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)) {\
240 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
248 st_lookup(table
, key
, value
)
250 register st_data_t key
;
253 unsigned int hash_val
, bin_pos
;
254 register st_table_entry
*ptr
;
256 hash_val
= do_hash(key
, table
);
257 FIND_ENTRY(table
, ptr
, hash_val
, bin_pos
);
263 if (value
!= 0) *value
= ptr
->record
;
268 #define ADD_DIRECT(table, key, value, hash_val, bin_pos, ret) \
270 st_table_entry *entry;\
271 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
273 bin_pos = hash_val % table->num_bins;\
275 entry = alloc(st_table_entry);\
276 if (IS_NULL(entry)) return ret;\
277 entry->hash = hash_val;\
279 entry->record = value;\
280 entry->next = table->bins[bin_pos];\
281 table->bins[bin_pos] = entry;\
282 table->num_entries++;\
286 st_insert(table
, key
, value
)
287 register st_table
*table
;
288 register st_data_t key
;
291 unsigned int hash_val
, bin_pos
;
292 register st_table_entry
*ptr
;
294 hash_val
= do_hash(key
, table
);
295 FIND_ENTRY(table
, ptr
, hash_val
, bin_pos
);
298 ADD_DIRECT(table
, key
, value
, hash_val
, bin_pos
, ONIGERR_MEMORY
);
308 st_add_direct(table
, key
, value
)
313 unsigned int hash_val
, bin_pos
;
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
,);
322 register st_table
*table
;
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
;
328 new_num_bins
= new_size(old_num_bins
+1);
329 new_bins
= (st_table_entry
**)Calloc(new_num_bins
, sizeof(st_table_entry
*));
334 for(i
= 0; i
< old_num_bins
; i
++) {
335 ptr
= table
->bins
[i
];
338 hash_val
= ptr
->hash
% new_num_bins
;
339 ptr
->next
= new_bins
[hash_val
];
340 new_bins
[hash_val
] = ptr
;
345 table
->num_bins
= new_num_bins
;
346 table
->bins
= new_bins
;
354 st_table_entry
*ptr
, *entry
;
355 int i
, num_bins
= old_table
->num_bins
;
357 new_table
= alloc(st_table
);
358 if (new_table
== 0) {
362 *new_table
= *old_table
;
363 new_table
->bins
= (st_table_entry
**)
364 Calloc((unsigned)num_bins
, sizeof(st_table_entry
*));
366 if (new_table
->bins
== 0) {
371 for(i
= 0; i
< num_bins
; i
++) {
372 new_table
->bins
[i
] = 0;
373 ptr
= old_table
->bins
[i
];
375 entry
= alloc(st_table_entry
);
377 free(new_table
->bins
);
382 entry
->next
= new_table
->bins
[i
];
383 new_table
->bins
[i
] = entry
;
391 st_delete(table
, key
, value
)
392 register st_table
*table
;
393 register st_data_t
*key
;
396 unsigned int hash_val
;
398 register st_table_entry
*ptr
;
400 hash_val
= do_hash_bin(*key
, table
);
401 ptr
= table
->bins
[hash_val
];
404 if (value
!= 0) *value
= 0;
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
;
417 for(; ptr
->next
!= 0; ptr
= ptr
->next
) {
418 if (EQUAL(table
, ptr
->next
->key
, *key
)) {
420 ptr
->next
= ptr
->next
->next
;
421 table
->num_entries
--;
422 if (value
!= 0) *value
= tmp
->record
;
433 st_delete_safe(table
, key
, value
, never
)
434 register st_table
*table
;
435 register st_data_t
*key
;
439 unsigned int hash_val
;
440 register st_table_entry
*ptr
;
442 hash_val
= do_hash_bin(*key
, table
);
443 ptr
= table
->bins
[hash_val
];
446 if (value
!= 0) *value
= 0;
450 for(; ptr
!= 0; ptr
= ptr
->next
) {
451 if ((ptr
->key
!= never
) && EQUAL(table
, ptr
->key
, *key
)) {
452 table
->num_entries
--;
454 if (value
!= 0) *value
= ptr
->record
;
455 ptr
->key
= ptr
->record
= never
;
464 #if defined(__GNUC__)
465 delete_never(st_data_t key
__attribute__ ((unused
)), st_data_t value
,
468 delete_never(key
, value
, never
)
469 st_data_t key
, value
, never
;
472 if (value
== never
) return ST_DELETE
;
477 st_cleanup_safe(table
, never
)
481 int num_entries
= table
->num_entries
;
483 st_foreach(table
, delete_never
, never
);
484 table
->num_entries
= num_entries
;
488 st_foreach(table
, func
, arg
)
493 st_table_entry
*ptr
, *last
, *tmp
;
494 enum st_retval retval
;
497 for(i
= 0; i
< table
->num_bins
; i
++) {
499 for(ptr
= table
->bins
[i
]; ptr
!= 0;) {
500 retval
= (*func
)(ptr
->key
, ptr
->record
, arg
);
502 case ST_CHECK
: /* check if hash is modified during iteration */
504 if (i
< table
->num_bins
) {
505 for (tmp
= table
->bins
[i
]; tmp
; tmp
=tmp
->next
) {
506 if (tmp
== ptr
) break;
510 /* call func with error notice */
523 table
->bins
[i
] = ptr
->next
;
526 last
->next
= ptr
->next
;
530 table
->num_entries
--;
539 register const char *string
;
544 register unsigned int h
= 0, g
;
546 while ((c
= *string
++) != '\0') {
548 if ( g
= h
& 0xF0000000 )
554 register int val
= 0;
556 while ((c
= *string
++) != '\0') {
564 return val
+ (val
<< 15);
566 register int val
= 0;
568 while ((c
= *string
++) != '\0') {
572 return val
+ (val
>>5);