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