xref: /PHP-5.6/ext/mbstring/oniguruma/st.c (revision fe92d64a)
1 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
2 
3 /* static	char	sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
4 
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 
9 #ifdef _WIN32
10 #include <malloc.h>
11 #endif
12 
13 #include "regint.h"
14 #include "st.h"
15 
16 typedef struct st_table_entry st_table_entry;
17 
18 struct st_table_entry {
19     unsigned int hash;
20     st_data_t key;
21     st_data_t record;
22     st_table_entry *next;
23 };
24 
25 #define ST_DEFAULT_MAX_DENSITY 5
26 #define ST_DEFAULT_INIT_TABLE_SIZE 11
27 
28     /*
29      * DEFAULT_MAX_DENSITY is the default for the largest we allow the
30      * average number of items per bin before increasing the number of
31      * bins
32      *
33      * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
34      * allocated initially
35      *
36      */
37 
38 static int numcmp(long, long);
39 static int numhash(long);
40 static struct st_hash_type type_numhash = {
41     numcmp,
42     numhash,
43 };
44 
45 /* extern int strcmp(const char *, const char *); */
46 static int strhash(const char *);
47 static struct st_hash_type type_strhash = {
48     strcmp,
49     strhash,
50 };
51 
52 static void rehash(st_table *);
53 
54 #define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
55 #define Calloc(n,s) (char*)xcalloc((n),(s))
56 
57 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
58 
59 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
60 #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
61 
62 /*
63  * MINSIZE is the minimum size of a dictionary.
64  */
65 
66 #define MINSIZE 8
67 
68 /*
69 Table of prime numbers 2^n+a, 2<=n<=30.
70 */
71 static const long primes[] = {
72 	8 + 3,
73 	16 + 3,
74 	32 + 5,
75 	64 + 3,
76 	128 + 3,
77 	256 + 27,
78 	512 + 9,
79 	1024 + 9,
80 	2048 + 5,
81 	4096 + 3,
82 	8192 + 27,
83 	16384 + 43,
84 	32768 + 3,
85 	65536 + 45,
86 	131072 + 29,
87 	262144 + 3,
88 	524288 + 21,
89 	1048576 + 7,
90 	2097152 + 17,
91 	4194304 + 15,
92 	8388608 + 9,
93 	16777216 + 43,
94 	33554432 + 35,
95 	67108864 + 15,
96 	134217728 + 29,
97 	268435456 + 3,
98 	536870912 + 11,
99 	1073741824 + 85,
100 	0
101 };
102 
103 static int
new_size(size)104 new_size(size)
105     int size;
106 {
107     int i;
108 
109 #if 0
110     for (i=3; i<31; i++) {
111 	if ((1<<i) > size) return 1<<i;
112     }
113     return -1;
114 #else
115     int newsize;
116 
117     for (i = 0, newsize = MINSIZE;
118 	 i < (int )(sizeof(primes)/sizeof(primes[0]));
119 	 i++, newsize <<= 1)
120     {
121 	if (newsize > size) return primes[i];
122     }
123     /* Ran out of polynomials */
124     return -1;			/* should raise exception */
125 #endif
126 }
127 
128 #ifdef HASH_LOG
129 static int collision = 0;
130 static int init_st = 0;
131 
132 static void
stat_col()133 stat_col()
134 {
135     FILE *f = fopen("/tmp/col", "w");
136     fprintf(f, "collision: %d\n", collision);
137     fclose(f);
138 }
139 #endif
140 
141 st_table*
st_init_table_with_size(type,size)142 st_init_table_with_size(type, size)
143     struct st_hash_type *type;
144     int size;
145 {
146     st_table *tbl;
147 
148 #ifdef HASH_LOG
149     if (init_st == 0) {
150 	init_st = 1;
151 	atexit(stat_col);
152     }
153 #endif
154 
155     size = new_size(size);	/* round up to prime number */
156 
157     tbl = alloc(st_table);
158     tbl->type = type;
159     tbl->num_entries = 0;
160     tbl->num_bins = size;
161     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
162 
163     return tbl;
164 }
165 
166 st_table*
st_init_table(type)167 st_init_table(type)
168     struct st_hash_type *type;
169 {
170     return st_init_table_with_size(type, 0);
171 }
172 
173 st_table*
st_init_numtable(void)174 st_init_numtable(void)
175 {
176     return st_init_table(&type_numhash);
177 }
178 
179 st_table*
st_init_numtable_with_size(size)180 st_init_numtable_with_size(size)
181     int size;
182 {
183     return st_init_table_with_size(&type_numhash, size);
184 }
185 
186 st_table*
st_init_strtable(void)187 st_init_strtable(void)
188 {
189     return st_init_table(&type_strhash);
190 }
191 
192 st_table*
st_init_strtable_with_size(size)193 st_init_strtable_with_size(size)
194     int size;
195 {
196     return st_init_table_with_size(&type_strhash, size);
197 }
198 
199 void
st_free_table(table)200 st_free_table(table)
201     st_table *table;
202 {
203     register st_table_entry *ptr, *next;
204     int i;
205 
206     for(i = 0; i < table->num_bins; i++) {
207 	ptr = table->bins[i];
208 	while (ptr != 0) {
209 	    next = ptr->next;
210 	    free(ptr);
211 	    ptr = next;
212 	}
213     }
214     free(table->bins);
215     free(table);
216 }
217 
218 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
219 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
220 
221 #ifdef HASH_LOG
222 #define COLLISION collision++
223 #else
224 #define COLLISION
225 #endif
226 
227 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
228     bin_pos = hash_val%(table)->num_bins;\
229     ptr = (table)->bins[bin_pos];\
230     if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
231 	COLLISION;\
232 	while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
233 	    ptr = ptr->next;\
234 	}\
235 	ptr = ptr->next;\
236     }\
237 } while (0)
238 
239 int
st_lookup(table,key,value)240 st_lookup(table, key, value)
241     st_table *table;
242     register st_data_t key;
243     st_data_t *value;
244 {
245     unsigned int hash_val, bin_pos;
246     register st_table_entry *ptr;
247 
248     hash_val = do_hash(key, table);
249     FIND_ENTRY(table, ptr, hash_val, bin_pos);
250 
251     if (ptr == 0) {
252 	return 0;
253     }
254     else {
255 	if (value != 0)  *value = ptr->record;
256 	return 1;
257     }
258 }
259 
260 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
261 do {\
262     st_table_entry *entry;\
263     if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
264 	rehash(table);\
265         bin_pos = hash_val % table->num_bins;\
266     }\
267     \
268     entry = alloc(st_table_entry);\
269     \
270     entry->hash = hash_val;\
271     entry->key = key;\
272     entry->record = value;\
273     entry->next = table->bins[bin_pos];\
274     table->bins[bin_pos] = entry;\
275     table->num_entries++;\
276 } while (0)
277 
278 int
st_insert(table,key,value)279 st_insert(table, key, value)
280     register st_table *table;
281     register st_data_t key;
282     st_data_t value;
283 {
284     unsigned int hash_val, bin_pos;
285     register st_table_entry *ptr;
286 
287     hash_val = do_hash(key, table);
288     FIND_ENTRY(table, ptr, hash_val, bin_pos);
289 
290     if (ptr == 0) {
291 	ADD_DIRECT(table, key, value, hash_val, bin_pos);
292 	return 0;
293     }
294     else {
295 	ptr->record = value;
296 	return 1;
297     }
298 }
299 
300 void
st_add_direct(table,key,value)301 st_add_direct(table, key, value)
302     st_table *table;
303     st_data_t key;
304     st_data_t value;
305 {
306     unsigned int hash_val, bin_pos;
307 
308     hash_val = do_hash(key, table);
309     bin_pos = hash_val % table->num_bins;
310     ADD_DIRECT(table, key, value, hash_val, bin_pos);
311 }
312 
313 static void
rehash(table)314 rehash(table)
315     register st_table *table;
316 {
317     register st_table_entry *ptr, *next, **new_bins;
318     int i, old_num_bins = table->num_bins, new_num_bins;
319     unsigned int hash_val;
320 
321     new_num_bins = new_size(old_num_bins+1);
322     new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
323 
324     for(i = 0; i < old_num_bins; i++) {
325 	ptr = table->bins[i];
326 	while (ptr != 0) {
327 	    next = ptr->next;
328 	    hash_val = ptr->hash % new_num_bins;
329 	    ptr->next = new_bins[hash_val];
330 	    new_bins[hash_val] = ptr;
331 	    ptr = next;
332 	}
333     }
334     free(table->bins);
335     table->num_bins = new_num_bins;
336     table->bins = new_bins;
337 }
338 
339 st_table*
st_copy(old_table)340 st_copy(old_table)
341     st_table *old_table;
342 {
343     st_table *new_table;
344     st_table_entry *ptr, *entry;
345     int i, num_bins = old_table->num_bins;
346 
347     new_table = alloc(st_table);
348     if (new_table == 0) {
349 	return 0;
350     }
351 
352     *new_table = *old_table;
353     new_table->bins = (st_table_entry**)
354 	Calloc((unsigned)num_bins, sizeof(st_table_entry*));
355 
356     if (new_table->bins == 0) {
357 	free(new_table);
358 	return 0;
359     }
360 
361     for(i = 0; i < num_bins; i++) {
362 	new_table->bins[i] = 0;
363 	ptr = old_table->bins[i];
364 	while (ptr != 0) {
365 	    entry = alloc(st_table_entry);
366 	    if (entry == 0) {
367 		free(new_table->bins);
368 		free(new_table);
369 		return 0;
370 	    }
371 	    *entry = *ptr;
372 	    entry->next = new_table->bins[i];
373 	    new_table->bins[i] = entry;
374 	    ptr = ptr->next;
375 	}
376     }
377     return new_table;
378 }
379 
380 int
st_delete(table,key,value)381 st_delete(table, key, value)
382     register st_table *table;
383     register st_data_t *key;
384     st_data_t *value;
385 {
386     unsigned int hash_val;
387     st_table_entry *tmp;
388     register st_table_entry *ptr;
389 
390     hash_val = do_hash_bin(*key, table);
391     ptr = table->bins[hash_val];
392 
393     if (ptr == 0) {
394 	if (value != 0) *value = 0;
395 	return 0;
396     }
397 
398     if (EQUAL(table, *key, ptr->key)) {
399 	table->bins[hash_val] = ptr->next;
400 	table->num_entries--;
401 	if (value != 0) *value = ptr->record;
402 	*key = ptr->key;
403 	free(ptr);
404 	return 1;
405     }
406 
407     for(; ptr->next != 0; ptr = ptr->next) {
408 	if (EQUAL(table, ptr->next->key, *key)) {
409 	    tmp = ptr->next;
410 	    ptr->next = ptr->next->next;
411 	    table->num_entries--;
412 	    if (value != 0) *value = tmp->record;
413 	    *key = tmp->key;
414 	    free(tmp);
415 	    return 1;
416 	}
417     }
418 
419     return 0;
420 }
421 
422 int
st_delete_safe(table,key,value,never)423 st_delete_safe(table, key, value, never)
424     register st_table *table;
425     register st_data_t *key;
426     st_data_t *value;
427     st_data_t never;
428 {
429     unsigned int hash_val;
430     register st_table_entry *ptr;
431 
432     hash_val = do_hash_bin(*key, table);
433     ptr = table->bins[hash_val];
434 
435     if (ptr == 0) {
436 	if (value != 0) *value = 0;
437 	return 0;
438     }
439 
440     for(; ptr != 0; ptr = ptr->next) {
441 	if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
442 	    table->num_entries--;
443 	    *key = ptr->key;
444 	    if (value != 0) *value = ptr->record;
445 	    ptr->key = ptr->record = never;
446 	    return 1;
447 	}
448     }
449 
450     return 0;
451 }
452 
453 static int
454 #if defined(__GNUC__)
delete_never(st_data_t key,st_data_t value,st_data_t never)455 delete_never(st_data_t key __attribute__ ((unused)), st_data_t value,
456 	     st_data_t never)
457 #else
458 delete_never(key, value, never)
459     st_data_t key, value, never;
460 #endif
461 {
462     if (value == never) return ST_DELETE;
463     return ST_CONTINUE;
464 }
465 
466 void
st_cleanup_safe(table,never)467 st_cleanup_safe(table, never)
468     st_table *table;
469     st_data_t never;
470 {
471     int num_entries = table->num_entries;
472 
473     st_foreach(table, delete_never, never);
474     table->num_entries = num_entries;
475 }
476 
477 int
st_foreach(table,func,arg)478 st_foreach(table, func, arg)
479     st_table *table;
480     int (*func)();
481     st_data_t arg;
482 {
483     st_table_entry *ptr, *last, *tmp;
484     enum st_retval retval;
485     int i;
486 
487     for(i = 0; i < table->num_bins; i++) {
488 	last = 0;
489 	for(ptr = table->bins[i]; ptr != 0;) {
490 	    retval = (*func)(ptr->key, ptr->record, arg);
491 	    switch (retval) {
492 	    case ST_CHECK:	/* check if hash is modified during iteration */
493 	        tmp = 0;
494 		if (i < table->num_bins) {
495 		    for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
496 			if (tmp == ptr) break;
497 		    }
498 		}
499 		if (!tmp) {
500 		    /* call func with error notice */
501 		    return 1;
502 		}
503 		/* fall through */
504 	    case ST_CONTINUE:
505 		last = ptr;
506 		ptr = ptr->next;
507 		break;
508 	    case ST_STOP:
509 	        return 0;
510 	    case ST_DELETE:
511 		tmp = ptr;
512 		if (last == 0) {
513 		    table->bins[i] = ptr->next;
514 		}
515 		else {
516 		    last->next = ptr->next;
517 		}
518 		ptr = ptr->next;
519 		free(tmp);
520 		table->num_entries--;
521 	    }
522 	}
523     }
524     return 0;
525 }
526 
527 static int
strhash(string)528 strhash(string)
529     register const char *string;
530 {
531     register int c;
532 
533 #ifdef HASH_ELFHASH
534     register unsigned int h = 0, g;
535 
536     while ((c = *string++) != '\0') {
537 	h = ( h << 4 ) + c;
538 	if ( g = h & 0xF0000000 )
539 	    h ^= g >> 24;
540 	h &= ~g;
541     }
542     return h;
543 #elif HASH_PERL
544     register int val = 0;
545 
546     while ((c = *string++) != '\0') {
547 	val += c;
548 	val += (val << 10);
549 	val ^= (val >> 6);
550     }
551     val += (val << 3);
552     val ^= (val >> 11);
553 
554     return val + (val << 15);
555 #else
556     register int val = 0;
557 
558     while ((c = *string++) != '\0') {
559 	val = val*997 + c;
560     }
561 
562     return val + (val>>5);
563 #endif
564 }
565 
566 static int
numcmp(x,y)567 numcmp(x, y)
568     long x, y;
569 {
570     return x != y;
571 }
572 
573 static int
numhash(n)574 numhash(n)
575     long n;
576 {
577     return n;
578 }
579