source: icGREP/icgrep-devel/cudd-2.5.1/sis/st.c @ 4746

Last change on this file since 4746 was 4597, checked in by nmedfort, 4 years ago

Upload of the CUDD library.

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