1 /*
2 * Revision Control Information
3 *
4 * /projects/hsis/CVS/utilities/st/st.c,v
5 * serdar
6 * 1.1
7 * 1993/07/29 01:00:13
8 *
9 */
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13
14 #include "st.h"
15
16 ABC_NAMESPACE_IMPL_START
17
18
19 #define st__NUMCMP(x,y) ((x) != (y))
20 #define st__NUMHASH(x,size) (Abc_AbsInt((long)x)%(size))
21 //#define st__PTRHASH(x,size) ((int)((ABC_PTRUINT_T)(x)>>2)%size) // 64-bit bug fix 9/17/2007
22 #define st__PTRHASH(x,size) ((int)(((ABC_PTRUINT_T)(x)>>2)%size))
23 #define EQUAL(func, x, y) \
24 ((((func) == st__numcmp) || ((func) == st__ptrcmp)) ?\
25 (st__NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))
26
27
28 #define do_hash(key, table)\
29 ((table->hash == st__ptrhash) ? st__PTRHASH((key),(table)->num_bins) :\
30 (table->hash == st__numhash) ? st__NUMHASH((key), (table)->num_bins) :\
31 (*table->hash)((key), (table)->num_bins))
32
33 static int rehash( st__table *table);
34
35 int st__numhash(const char*, int);
36 int st__ptrhash(const char*, int);
37 int st__numcmp(const char*, const char*);
38 int st__ptrcmp(const char*, const char*);
39
40 st__table *
st__init_table_with_params(st__compare_func_type compare,st__hash_func_type hash,int size,int density,double grow_factor,int reorder_flag)41 st__init_table_with_params( st__compare_func_type compare, st__hash_func_type hash, int size, int density, double grow_factor, int reorder_flag)
42 {
43 int i;
44 st__table *newTable;
45
46 newTable = ABC_ALLOC( st__table, 1);
47 if (newTable == NULL) {
48 return NULL;
49 }
50 newTable->compare = compare;
51 newTable->hash = hash;
52 newTable->num_entries = 0;
53 newTable->max_density = density;
54 newTable->grow_factor = grow_factor;
55 newTable->reorder_flag = reorder_flag;
56 if (size <= 0) {
57 size = 1;
58 }
59 newTable->num_bins = size;
60 newTable->bins = ABC_ALLOC( st__table_entry *, size);
61 if (newTable->bins == NULL) {
62 ABC_FREE(newTable);
63 return NULL;
64 }
65 for(i = 0; i < size; i++) {
66 newTable->bins[i] = 0;
67 }
68 return newTable;
69 }
70
71 st__table *
st__init_table(st__compare_func_type compare,st__hash_func_type hash)72 st__init_table( st__compare_func_type compare, st__hash_func_type hash)
73 {
74 return st__init_table_with_params(compare, hash, st__DEFAULT_INIT_TABLE_SIZE,
75 st__DEFAULT_MAX_DENSITY,
76 st__DEFAULT_GROW_FACTOR,
77 st__DEFAULT_REORDER_FLAG);
78 }
79
80 void
st__free_table(st__table * table)81 st__free_table( st__table *table)
82 {
83 st__table_entry *ptr, *next;
84 int i;
85
86 for(i = 0; i < table->num_bins ; i++) {
87 ptr = table->bins[i];
88 while (ptr != NULL) {
89 next = ptr->next;
90 ABC_FREE(ptr);
91 ptr = next;
92 }
93 }
94 ABC_FREE(table->bins);
95 ABC_FREE(table);
96 }
97
98 #define PTR_NOT_EQUAL(table, ptr, user_key)\
99 (ptr != NULL && !EQUAL(table->compare, user_key, (ptr)->key))
100
101 #define FIND_ENTRY(table, hash_val, key, ptr, last) \
102 (last) = &(table)->bins[hash_val];\
103 (ptr) = *(last);\
104 while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
105 (last) = &(ptr)->next; (ptr) = *(last);\
106 }\
107 if ((ptr) != NULL && (table)->reorder_flag) {\
108 *(last) = (ptr)->next;\
109 (ptr)->next = (table)->bins[hash_val];\
110 (table)->bins[hash_val] = (ptr);\
111 }
112
113 int
st__lookup(st__table * table,const char * key,char ** value)114 st__lookup( st__table *table, const char *key, char **value)
115 {
116 int hash_val;
117 st__table_entry *ptr, **last;
118
119 hash_val = do_hash(key, table);
120
121 FIND_ENTRY(table, hash_val, key, ptr, last);
122
123 if (ptr == NULL) {
124 return 0;
125 } else {
126 if (value != NULL) {
127 *value = ptr->record;
128 }
129 return 1;
130 }
131 }
132
133 int
st__lookup_int(st__table * table,char * key,int * value)134 st__lookup_int( st__table *table, char *key, int *value)
135 {
136 int hash_val;
137 st__table_entry *ptr, **last;
138
139 hash_val = do_hash(key, table);
140
141 FIND_ENTRY(table, hash_val, key, ptr, last);
142
143 if (ptr == NULL) {
144 return 0;
145 } else {
146 if (value != 0) {
147 *value = (long) ptr->record;
148 }
149 return 1;
150 }
151 }
152
153 /* This macro does not check if memory allocation fails. Use at you own risk */
154 #define ADD_DIRECT(table, key, value, hash_val, new)\
155 {\
156 if (table->num_entries/table->num_bins >= table->max_density) {\
157 rehash(table);\
158 hash_val = do_hash(key,table);\
159 }\
160 \
161 new = ABC_ALLOC( st__table_entry, 1);\
162 \
163 new->key = key;\
164 new->record = value;\
165 new->next = table->bins[hash_val];\
166 table->bins[hash_val] = new;\
167 table->num_entries++;\
168 }
169
170 int
st__insert(st__table * table,const char * key,char * value)171 st__insert( st__table *table, const char *key, char *value)
172 {
173 int hash_val;
174 st__table_entry *newEntry;
175 st__table_entry *ptr, **last;
176
177 hash_val = do_hash(key, table);
178
179 FIND_ENTRY(table, hash_val, key, ptr, last);
180
181 if (ptr == NULL) {
182 if (table->num_entries/table->num_bins >= table->max_density) {
183 if (rehash(table) == st__OUT_OF_MEM) {
184 return st__OUT_OF_MEM;
185 }
186 hash_val = do_hash(key, table);
187 }
188 newEntry = ABC_ALLOC( st__table_entry, 1);
189 if (newEntry == NULL) {
190 return st__OUT_OF_MEM;
191 }
192 newEntry->key = (char *)key;
193 newEntry->record = value;
194 newEntry->next = table->bins[hash_val];
195 table->bins[hash_val] = newEntry;
196 table->num_entries++;
197 return 0;
198 } else {
199 ptr->record = value;
200 return 1;
201 }
202 }
203
204 int
st__add_direct(st__table * table,char * key,char * value)205 st__add_direct( st__table *table, char *key, char *value)
206 {
207 int hash_val;
208 st__table_entry *newEntry;
209
210 hash_val = do_hash(key, table);
211 if (table->num_entries / table->num_bins >= table->max_density) {
212 if (rehash(table) == st__OUT_OF_MEM) {
213 return st__OUT_OF_MEM;
214 }
215 }
216 hash_val = do_hash(key, table);
217 newEntry = ABC_ALLOC( st__table_entry, 1);
218 if (newEntry == NULL) {
219 return st__OUT_OF_MEM;
220 }
221 newEntry->key = key;
222 newEntry->record = value;
223 newEntry->next = table->bins[hash_val];
224 table->bins[hash_val] = newEntry;
225 table->num_entries++;
226 return 1;
227 }
228
229 int
st__find_or_add(st__table * table,char * key,char *** slot)230 st__find_or_add( st__table *table, char *key, char ***slot)
231 {
232 int hash_val;
233 st__table_entry *newEntry, *ptr, **last;
234
235 hash_val = do_hash(key, table);
236
237 FIND_ENTRY(table, hash_val, key, ptr, last);
238
239 if (ptr == NULL) {
240 if (table->num_entries / table->num_bins >= table->max_density) {
241 if (rehash(table) == st__OUT_OF_MEM) {
242 return st__OUT_OF_MEM;
243 }
244 hash_val = do_hash(key, table);
245 }
246 newEntry = ABC_ALLOC( st__table_entry, 1);
247 if (newEntry == NULL) {
248 return st__OUT_OF_MEM;
249 }
250 newEntry->key = key;
251 newEntry->record = (char *) 0;
252 newEntry->next = table->bins[hash_val];
253 table->bins[hash_val] = newEntry;
254 table->num_entries++;
255 if (slot != NULL) *slot = &newEntry->record;
256 return 0;
257 } else {
258 if (slot != NULL) *slot = &ptr->record;
259 return 1;
260 }
261 }
262
263 int
st__find(st__table * table,char * key,char *** slot)264 st__find( st__table *table, char *key, char ***slot)
265 {
266 int hash_val;
267 st__table_entry *ptr, **last;
268
269 hash_val = do_hash(key, table);
270
271 FIND_ENTRY(table, hash_val, key, ptr, last);
272
273 if (ptr == NULL) {
274 return 0;
275 } else {
276 if (slot != NULL) {
277 *slot = &ptr->record;
278 }
279 return 1;
280 }
281 }
282
283 static int
rehash(st__table * table)284 rehash( st__table *table)
285 {
286 st__table_entry *ptr, *next, **old_bins;
287 int i, old_num_bins, hash_val, old_num_entries;
288
289 /* save old values */
290 old_bins = table->bins;
291 old_num_bins = table->num_bins;
292 old_num_entries = table->num_entries;
293
294 /* rehash */
295 table->num_bins = (int)(table->grow_factor * old_num_bins);
296 if (table->num_bins % 2 == 0) {
297 table->num_bins += 1;
298 }
299 table->num_entries = 0;
300 table->bins = ABC_ALLOC( st__table_entry *, table->num_bins);
301 if (table->bins == NULL) {
302 table->bins = old_bins;
303 table->num_bins = old_num_bins;
304 table->num_entries = old_num_entries;
305 return st__OUT_OF_MEM;
306 }
307 /* initialize */
308 for (i = 0; i < table->num_bins; i++) {
309 table->bins[i] = 0;
310 }
311
312 /* copy data over */
313 for (i = 0; i < old_num_bins; i++) {
314 ptr = old_bins[i];
315 while (ptr != NULL) {
316 next = ptr->next;
317 hash_val = do_hash(ptr->key, table);
318 ptr->next = table->bins[hash_val];
319 table->bins[hash_val] = ptr;
320 table->num_entries++;
321 ptr = next;
322 }
323 }
324 ABC_FREE(old_bins);
325
326 return 1;
327 }
328
329 st__table *
st__copy(st__table * old_table)330 st__copy( st__table *old_table)
331 {
332 st__table *newEntry_table;
333 st__table_entry *ptr, *newEntryptr, *next, *newEntry;
334 int i, j, num_bins = old_table->num_bins;
335
336 newEntry_table = ABC_ALLOC( st__table, 1);
337 if (newEntry_table == NULL) {
338 return NULL;
339 }
340
341 *newEntry_table = *old_table;
342 newEntry_table->bins = ABC_ALLOC( st__table_entry *, num_bins);
343 if (newEntry_table->bins == NULL) {
344 ABC_FREE(newEntry_table);
345 return NULL;
346 }
347 for(i = 0; i < num_bins ; i++) {
348 newEntry_table->bins[i] = NULL;
349 ptr = old_table->bins[i];
350 while (ptr != NULL) {
351 newEntry = ABC_ALLOC( st__table_entry, 1);
352 if (newEntry == NULL) {
353 for (j = 0; j <= i; j++) {
354 newEntryptr = newEntry_table->bins[j];
355 while (newEntryptr != NULL) {
356 next = newEntryptr->next;
357 ABC_FREE(newEntryptr);
358 newEntryptr = next;
359 }
360 }
361 ABC_FREE(newEntry_table->bins);
362 ABC_FREE(newEntry_table);
363 return NULL;
364 }
365 *newEntry = *ptr;
366 newEntry->next = newEntry_table->bins[i];
367 newEntry_table->bins[i] = newEntry;
368 ptr = ptr->next;
369 }
370 }
371 return newEntry_table;
372 }
373
374 int
st__delete(st__table * table,const char ** keyp,char ** value)375 st__delete( st__table *table, const char **keyp, char **value)
376 {
377 int hash_val;
378 const char *key = *keyp;
379 st__table_entry *ptr, **last;
380
381 hash_val = do_hash(key, table);
382
383 FIND_ENTRY(table, hash_val, key, ptr ,last);
384
385 if (ptr == NULL) {
386 return 0;
387 }
388
389 *last = ptr->next;
390 if (value != NULL) *value = ptr->record;
391 *keyp = ptr->key;
392 ABC_FREE(ptr);
393 table->num_entries--;
394 return 1;
395 }
396
397 int
st__delete_int(st__table * table,long * keyp,char ** value)398 st__delete_int( st__table *table, long *keyp, char **value)
399 {
400 int hash_val;
401 char *key = (char *) *keyp;
402 st__table_entry *ptr, **last;
403
404 hash_val = do_hash(key, table);
405
406 FIND_ENTRY(table, hash_val, key, ptr ,last);
407
408 if (ptr == NULL) {
409 return 0;
410 }
411
412 *last = ptr->next;
413 if (value != NULL) *value = ptr->record;
414 *keyp = (long) ptr->key;
415 ABC_FREE(ptr);
416 table->num_entries--;
417 return 1;
418 }
419
420 int
st__foreach(st__table * table,enum st__retval (* func)(char *,char *,char *),char * arg)421 st__foreach( st__table *table, enum st__retval (*func)(char *, char *, char *), char *arg)
422 {
423 st__table_entry *ptr, **last;
424 enum st__retval retval;
425 int i;
426
427 for(i = 0; i < table->num_bins; i++) {
428 last = &table->bins[i]; ptr = *last;
429 while (ptr != NULL) {
430 retval = (*func)(ptr->key, ptr->record, arg);
431 switch (retval) {
432 case st__CONTINUE:
433 last = &ptr->next; ptr = *last;
434 break;
435 case st__STOP:
436 return 0;
437 case st__DELETE:
438 *last = ptr->next;
439 table->num_entries--; /* cstevens@ic */
440 ABC_FREE(ptr);
441 ptr = *last;
442 }
443 }
444 }
445 return 1;
446 }
447
448 int
st__strhash(const char * string,int modulus)449 st__strhash(const char *string, int modulus)
450 {
451 unsigned char * ustring = (unsigned char *)string;
452 unsigned c, val = 0;
453 assert( modulus > 0 );
454 while ((c = *ustring++) != '\0') {
455 val = val*997 + c;
456 }
457 return (int)(val%modulus);
458 }
459
460 int
st__numhash(const char * x,int size)461 st__numhash(const char *x, int size)
462 {
463 return st__NUMHASH(x, size);
464 }
465
466 int
st__ptrhash(const char * x,int size)467 st__ptrhash(const char *x, int size)
468 {
469 return st__PTRHASH(x, size);
470 }
471
472 int
st__numcmp(const char * x,const char * y)473 st__numcmp(const char *x, const char *y)
474 {
475 return st__NUMCMP(x, y);
476 }
477
478 int
st__ptrcmp(const char * x,const char * y)479 st__ptrcmp(const char *x, const char *y)
480 {
481 return st__NUMCMP(x, y);
482 }
483
484 st__generator *
st__init_gen(st__table * table)485 st__init_gen( st__table *table)
486 {
487 st__generator *gen;
488
489 gen = ABC_ALLOC( st__generator, 1);
490 if (gen == NULL) {
491 return NULL;
492 }
493 gen->table = table;
494 gen->entry = NULL;
495 gen->index = 0;
496 return gen;
497 }
498
499
500 int
st__gen(st__generator * gen,const char ** key_p,char ** value_p)501 st__gen( st__generator *gen, const char **key_p, char **value_p)
502 {
503 int i;
504
505 if (gen->entry == NULL) {
506 /* try to find next entry */
507 for(i = gen->index; i < gen->table->num_bins; i++) {
508 if (gen->table->bins[i] != NULL) {
509 gen->index = i+1;
510 gen->entry = gen->table->bins[i];
511 break;
512 }
513 }
514 if (gen->entry == NULL) {
515 return 0; /* that's all folks ! */
516 }
517 }
518 *key_p = gen->entry->key;
519 if (value_p != 0) {
520 *value_p = gen->entry->record;
521 }
522 gen->entry = gen->entry->next;
523 return 1;
524 }
525
526
527 int
st__gen_int(st__generator * gen,const char ** key_p,long * value_p)528 st__gen_int( st__generator *gen, const char **key_p, long *value_p)
529 {
530 int i;
531
532 if (gen->entry == NULL) {
533 /* try to find next entry */
534 for(i = gen->index; i < gen->table->num_bins; i++) {
535 if (gen->table->bins[i] != NULL) {
536 gen->index = i+1;
537 gen->entry = gen->table->bins[i];
538 break;
539 }
540 }
541 if (gen->entry == NULL) {
542 return 0; /* that's all folks ! */
543 }
544 }
545 *key_p = gen->entry->key;
546 if (value_p != 0) {
547 *value_p = (long) gen->entry->record;
548 }
549 gen->entry = gen->entry->next;
550 return 1;
551 }
552
553
554 void
st__free_gen(st__generator * gen)555 st__free_gen( st__generator *gen)
556 {
557 ABC_FREE(gen);
558 }
559
560 ABC_NAMESPACE_IMPL_END
561
562