source: vis_dev/cusp-1.1/src/st/st.c @ 64

Last change on this file since 64 was 12, checked in by cecile, 13 years ago

cusp added

File size: 28.3 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [st.c]
4
5  PackageName [st]
6
7  Synopsis    [Symbol table package.]
8
9  Description [The st library provides functions to create, maintain,
10  and query symbol tables.]
11
12  SeeAlso     []
13
14  Author      []
15
16  Copyright   []
17
18******************************************************************************/
19#include <stdlib.h>
20#include "util.h"
21#include "st.h"
22
23/*---------------------------------------------------------------------------*/
24/* Constant declarations                                                     */
25/*---------------------------------------------------------------------------*/
26
27/*---------------------------------------------------------------------------*/
28/* Stucture declarations                                                     */
29/*---------------------------------------------------------------------------*/
30
31/*---------------------------------------------------------------------------*/
32/* Type declarations                                                         */
33/*---------------------------------------------------------------------------*/
34
35/*---------------------------------------------------------------------------*/
36/* Variable declarations                                                     */
37/*---------------------------------------------------------------------------*/
38
39#ifndef lint
40static char rcsid[] UNUSED = " $Id: st.c,v 1.2 2009-04-13 17:14:16 hhkim Exp $";
41#endif
42
43/*---------------------------------------------------------------------------*/
44/* Macro declarations                                                        */
45/*---------------------------------------------------------------------------*/
46
47#define ST_NUMCMP(x,y) ((x) != (y))
48
49#define ST_NUMHASH(x,size) (ABS((long)x)%(size))
50
51#ifdef SIZEOF_VOID_P
52#if SIZEOF_VOID_P == 8
53#define st_shift 3
54#else
55#define st_shift 2
56#endif
57#else
58#define st_shift 2
59#endif
60
61#define ST_PTRHASH(x,size) ((unsigned int)((unsigned long)(x)>>st_shift)%size)
62
63#define EQUAL(func, x, y) \
64    ((((func) == st_numcmp) || ((func) == st_ptrcmp)) ?\
65      (ST_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))
66
67#define do_hash(key, table)\
68    ((int)((table->hash == st_ptrhash) ? ST_PTRHASH((char *)(key),(table)->num_bins) :\
69     (table->hash == st_numhash) ? ST_NUMHASH((char *)(key), (table)->num_bins) :\
70     (*table->hash)((char *)(key), (table)->num_bins)))
71
72#define PTR_NOT_EQUAL(table, ptr, user_key)\
73(ptr != NIL(st_table_entry) && !EQUAL(table->compare, (char *)user_key, (ptr)->key))
74
75#define FIND_ENTRY(table, hash_val, key, ptr, last) \
76    (last) = &(table)->bins[hash_val];\
77    (ptr) = *(last);\
78    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
79        (last) = &(ptr)->next; (ptr) = *(last);\
80    }\
81    if ((ptr) != NIL(st_table_entry) && (table)->reorder_flag) {\
82        *(last) = (ptr)->next;\
83        (ptr)->next = (table)->bins[hash_val];\
84        (table)->bins[hash_val] = (ptr);\
85    }
86
87/* This macro does not check if memory allocation fails. Use at you own risk */
88#define ADD_DIRECT(table, key, value, hash_val, newt)\
89{\
90    if (table->num_entries/table->num_bins >= table->max_density) {\
91        rehash(table);\
92        hash_val = do_hash(key,table);\
93    }\
94    \
95    newt = ALLOC(st_table_entry, 1);\
96    \
97    newt->key = (char *)key;\
98    newt->record = value;\
99    newt->next = table->bins[hash_val];\
100    table->bins[hash_val] = newt;\
101    table->num_entries++;\
102}
103
104/**AutomaticStart*************************************************************/
105
106/*---------------------------------------------------------------------------*/
107/* Static function prototypes                                                */
108/*---------------------------------------------------------------------------*/
109
110static int rehash (st_table *);
111
112/**AutomaticEnd***************************************************************/
113
114
115/*---------------------------------------------------------------------------*/
116/* Definition of exported functions                                          */
117/*---------------------------------------------------------------------------*/
118
119/**Function********************************************************************
120
121  Synopsis    [Create and initialize a table.]
122
123  Description [Create and initialize a table with the comparison function
124  compare_fn and hash function hash_fn. compare_fn is
125  <pre>
126        int compare_fn(const char *key1, const char *key2)
127  </pre>
128  It returns <,=,> 0 depending on whether key1 <,=,> key2 by some measure.<p>
129  hash_fn is
130  <pre>
131        int hash_fn(char *key, int modulus)
132  </pre>
133  It returns a integer between 0 and modulus-1 such that if
134  compare_fn(key1,key2) == 0 then hash_fn(key1) == hash_fn(key2).<p>
135  There are five predefined hash and comparison functions in st.
136  For keys as numbers:
137  <pre>
138         st_numhash(key, modulus) { return (unsigned int) key % modulus; }
139  </pre>
140  <pre>
141         st_numcmp(x,y) { return (int) x - (int) y; }
142  </pre>
143  For keys as pointers:
144  <pre>
145         st_ptrhash(key, modulus) { return ((unsigned int) key/4) % modulus }
146  </pre>
147  <pre>
148         st_ptrcmp(x,y) { return (int) x - (int) y; }
149  </pre>
150  For keys as strings:
151  <pre>
152         st_strhash(x,y) - a reasonable hashing function for strings
153  </pre>
154  <pre>
155         strcmp(x,y) - the standard library function
156  </pre>
157  It is recommended to use these particular functions if they fit your
158  needs, since st will recognize certain of them and run more quickly
159  because of it.]
160
161  SideEffects [None]
162
163  SeeAlso     [st_init_table_with_params st_free_table]
164
165******************************************************************************/
166st_table *
167st_init_table(ST_PFICPCP compare, ST_PFICPI hash)
168{
169    return st_init_table_with_params(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,
170                                     ST_DEFAULT_MAX_DENSITY,
171                                     ST_DEFAULT_GROW_FACTOR,
172                                     ST_DEFAULT_REORDER_FLAG);
173
174} /* st_init_table */
175
176
177/**Function********************************************************************
178
179  Synopsis    [Create a table with given parameters.]
180
181  Description [The full blown table initializer.  compare and hash are
182  the same as in st_init_table. density is the largest the average
183  number of entries per hash bin there should be before the table is
184  grown.  grow_factor is the factor the table is grown by when it
185  becomes too full. size is the initial number of bins to be allocated
186  for the hash table.  If reorder_flag is non-zero, then every time an
187  entry is found, it is moved to the top of the chain.<p>
188  st_init_table(compare, hash) is equivelent to
189  <pre>
190  st_init_table_with_params(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,
191                            ST_DEFAULT_MAX_DENSITY,
192                            ST_DEFAULT_GROW_FACTOR,
193                            ST_DEFAULT_REORDER_FLAG);
194  </pre>
195  ]
196
197  SideEffects [None]
198
199  SeeAlso     [st_init_table st_free_table]
200
201******************************************************************************/
202st_table *
203st_init_table_with_params(
204  ST_PFICPCP compare,
205  ST_PFICPI hash,
206  int size,
207  int density,
208  double grow_factor,
209  int reorder_flag)
210{
211    int i;
212    st_table *newt;
213
214    newt = ALLOC(st_table, 1);
215    if (newt == NIL(st_table)) {
216        return NIL(st_table);
217    }
218    newt->compare = compare;
219    newt->hash = hash;
220    newt->num_entries = 0;
221    newt->max_density = density;
222    newt->grow_factor = grow_factor;
223    newt->reorder_flag = reorder_flag;
224    if (size <= 0) {
225        size = 1;
226    }
227    newt->num_bins = size;
228    newt->bins = ALLOC(st_table_entry *, size);
229    if (newt->bins == NIL(st_table_entry *)) {
230        FREE(newt);
231        return NIL(st_table);
232    }
233    for(i = 0; i < size; i++) {
234        newt->bins[i] = 0;
235    }
236    return newt;
237
238} /* st_init_table_with_params */
239
240
241/**Function********************************************************************
242
243  Synopsis    [Free a table.]
244
245  Description [Any internal storage associated with table is freed.
246  It is the user's responsibility to free any storage associated
247  with the pointers he placed in the table (by perhaps using
248  st_foreach).]
249
250  SideEffects [None]
251
252  SeeAlso     [st_init_table st_init_table_with_params]
253
254******************************************************************************/
255void
256st_free_table(st_table *table)
257{
258    st_table_entry *ptr, *next;
259    int i;
260
261    for(i = 0; i < table->num_bins ; i++) {
262        ptr = table->bins[i];
263        while (ptr != NIL(st_table_entry)) {
264            next = ptr->next;
265            FREE(ptr);
266            ptr = next;
267        }
268    }
269    FREE(table->bins);
270    FREE(table);
271
272} /* st_free_table */
273
274
275/**Function********************************************************************
276
277  Synopsis    [Lookup up `key' in `table'.]
278
279  Description [Lookup up `key' in `table'. If an entry is found, 1 is
280  returned and if `value' is not nil, the variable it points to is set
281  to the associated value.  If an entry is not found, 0 is returned
282  and the variable pointed by value is unchanged.]
283
284  SideEffects [None]
285
286  SeeAlso     [st_lookup_int]
287
288******************************************************************************/
289int
290st_lookup(st_table *table, void *key, void *value)
291{
292    int hash_val;
293    st_table_entry *ptr, **last;
294
295    hash_val = do_hash(key, table);
296
297    FIND_ENTRY(table, hash_val, key, ptr, last);
298
299    if (ptr == NIL(st_table_entry)) {
300        return 0;
301    } else {
302        if (value != NIL(void)) {
303            *(char **)value = ptr->record;
304        }
305        return 1;
306    }
307
308} /* st_lookup */
309
310
311/**Function********************************************************************
312
313  Synopsis    [Lookup up `key' in `table'.]
314
315  Description [Lookup up `key' in `table'.  If an entry is found, 1 is
316  returned and if `value' is not nil, the variable it points to is
317  set to the associated integer value.  If an entry is not found, 0 is
318  return and the variable pointed by `value' is unchanged.]
319
320  SideEffects [None]
321
322  SeeAlso     [st_lookup]
323
324******************************************************************************/
325int
326st_lookup_int(st_table *table, void *key, int *value)
327{
328    int hash_val;
329    st_table_entry *ptr, **last;
330
331    hash_val = do_hash(key, table);
332
333    FIND_ENTRY(table, hash_val, key, ptr, last);
334   
335    if (ptr == NIL(st_table_entry)) {
336        return 0;
337    } else {
338        if (value != NIL(int)) {
339            *value = (int) (long) ptr->record;
340        }
341        return 1;
342    }
343
344} /* st_lookup_int */
345
346
347/**Function********************************************************************
348
349  Synopsis    [Insert value in table under the key 'key'.]
350
351  Description [Insert value in table under the key 'key'.  Returns 1
352  if there was an entry already under the key; 0 if there was no entry
353  under the key and insertion was successful; ST_OUT_OF_MEM otherwise.
354  In either of the first two cases the new value is added.]
355
356  SideEffects [None]
357
358  SeeAlso     []
359
360******************************************************************************/
361int
362st_insert(st_table *table, void *key, void *value)
363{
364    int hash_val;
365    st_table_entry *newt;
366    st_table_entry *ptr, **last;
367
368    hash_val = do_hash(key, table);
369
370    FIND_ENTRY(table, hash_val, key, ptr, last);
371
372    if (ptr == NIL(st_table_entry)) {
373        if (table->num_entries/table->num_bins >= table->max_density) {
374            if (rehash(table) == ST_OUT_OF_MEM) {
375                return ST_OUT_OF_MEM;
376            }
377            hash_val = do_hash(key, table);
378        }
379        newt = ALLOC(st_table_entry, 1);
380        if (newt == NIL(st_table_entry)) {
381            return ST_OUT_OF_MEM;
382        }
383        newt->key = (char *)key;
384        newt->record = (char *)value;
385        newt->next = table->bins[hash_val];
386        table->bins[hash_val] = newt;
387        table->num_entries++;
388        return 0;
389    } else {
390        ptr->record = (char *)value;
391        return 1;
392    }
393
394} /* st_insert */
395
396
397/**Function********************************************************************
398
399  Synopsis    [Place 'value' in 'table' under the key 'key'.]
400
401  Description [Place 'value' in 'table' under the key 'key'.  This is
402  done without checking if 'key' is in 'table' already.  This should
403  only be used if you are sure there is not already an entry for
404  'key', since it is undefined which entry you would later get from
405  st_lookup or st_find_or_add. Returns 1 if successful; ST_OUT_OF_MEM
406  otherwise.]
407
408  SideEffects [None]
409
410  SeeAlso     []
411
412******************************************************************************/
413int
414st_add_direct(st_table *table, void *key, void *value)
415{
416    int hash_val;
417    st_table_entry *newt;
418   
419    hash_val = do_hash(key, table);
420    if (table->num_entries / table->num_bins >= table->max_density) {
421        if (rehash(table) == ST_OUT_OF_MEM) {
422            return ST_OUT_OF_MEM;
423        }
424    }
425    hash_val = do_hash(key, table);
426    newt = ALLOC(st_table_entry, 1);
427    if (newt == NIL(st_table_entry)) {
428        return ST_OUT_OF_MEM;
429    }
430    newt->key = (char *)key;
431    newt->record = (char *)value;
432    newt->next = table->bins[hash_val];
433    table->bins[hash_val] = newt;
434    table->num_entries++;
435    return 1;
436
437} /* st_add_direct */
438
439
440/**Function********************************************************************
441
442  Synopsis    [Lookup `key' in `table'.]
443
444  Description [Lookup `key' in `table'.  If not found, create an
445  entry.  In either case set slot to point to the field in the entry
446  where the value is stored.  The value associated with `key' may then
447  be changed by accessing directly through slot.  Returns 1 if an
448  entry already existed, 0 if it did not exist and creation was
449  successful; ST_OUT_OF_MEM otherwise.  As an example:
450  <pre>
451      char **slot;
452  </pre>
453  <pre>
454      char *key;
455  </pre>
456  <pre>
457      char *value = (char *) item_ptr <-- ptr to a malloc'd structure
458  </pre>
459  <pre>
460      if (st_find_or_add(table, key, &slot) == 1) {
461  </pre>
462  <pre>
463         FREE(*slot); <-- free the old value of the record
464  </pre>
465  <pre>
466      }
467  </pre>
468  <pre>
469      *slot = value;  <-- attach the new value to the record
470  </pre>
471  This replaces the equivelent code:
472  <pre>
473      if (st_lookup(table, key, &ovalue) == 1) {
474  </pre>
475  <pre>
476         FREE(ovalue);
477  </pre>
478  <pre>
479      }
480  </pre>
481  <pre>
482      st_insert(table, key, value);
483  </pre>
484  ]
485
486  SideEffects [None]
487
488  SeeAlso     [st_find]
489
490******************************************************************************/
491int
492st_find_or_add(st_table *table, void *key, void *slot)
493{
494    int hash_val;
495    st_table_entry *newt, *ptr, **last;
496
497    hash_val = do_hash(key, table);
498
499    FIND_ENTRY(table, hash_val, key, ptr, last);
500
501    if (ptr == NIL(st_table_entry)) {
502        if (table->num_entries / table->num_bins >= table->max_density) {
503            if (rehash(table) == ST_OUT_OF_MEM) {
504                return ST_OUT_OF_MEM;
505            }
506            hash_val = do_hash(key, table);
507        }
508        newt = ALLOC(st_table_entry, 1);
509        if (newt == NIL(st_table_entry)) {
510            return ST_OUT_OF_MEM;
511        }
512        newt->key = (char *)key;
513        newt->record = (char *) 0;
514        newt->next = table->bins[hash_val];
515        table->bins[hash_val] = newt;
516        table->num_entries++;
517        if (slot != NIL(void)) *(char ***)slot = &newt->record;
518        return 0;
519    } else {
520        if (slot != NIL(void)) *(char ***)slot = &ptr->record;
521        return 1;
522    }
523
524} /* st_find_or_add */
525
526
527/**Function********************************************************************
528
529  Synopsis    [Lookup `key' in `table'.]
530
531  Description [Like st_find_or_add, but does not create an entry if
532  one is not found.]
533
534  SideEffects [None]
535
536  SeeAlso     [st_find_or_add]
537
538******************************************************************************/
539int
540st_find(st_table *table, void *key, void *slot)
541{
542    int hash_val;
543    st_table_entry *ptr, **last;
544
545    hash_val = do_hash(key, table);
546
547    FIND_ENTRY(table, hash_val, key, ptr, last);
548
549    if (ptr == NIL(st_table_entry)) {
550        return 0;
551    } else {
552        if (slot != NIL(void)) {
553            *(char ***)slot = &ptr->record;
554        }
555        return 1;
556    }
557
558} /* st_find */
559
560
561/**Function********************************************************************
562
563  Synopsis    [Return a copy of old_table and all its members.]
564
565  Description [Return a copy of old_table and all its members.
566  (st_table *) 0 is returned if there was insufficient memory to do
567  the copy.]
568
569  SideEffects [None]
570
571  SeeAlso     []
572
573******************************************************************************/
574st_table *
575st_copy(st_table *old_table)
576{
577    st_table *new_table;
578    st_table_entry *ptr, *newptr, *next, *newt;
579    int i, j, num_bins = old_table->num_bins;
580
581    new_table = ALLOC(st_table, 1);
582    if (new_table == NIL(st_table)) {
583        return NIL(st_table);
584    }
585   
586    *new_table = *old_table;
587    new_table->bins = ALLOC(st_table_entry *, num_bins);
588    if (new_table->bins == NIL(st_table_entry *)) {
589        FREE(new_table);
590        return NIL(st_table);
591    }
592    for(i = 0; i < num_bins ; i++) {
593        new_table->bins[i] = NIL(st_table_entry);
594        ptr = old_table->bins[i];
595        while (ptr != NIL(st_table_entry)) {
596            newt = ALLOC(st_table_entry, 1);
597            if (newt == NIL(st_table_entry)) {
598                for (j = 0; j <= i; j++) {
599                    newptr = new_table->bins[j];
600                    while (newptr != NIL(st_table_entry)) {
601                        next = newptr->next;
602                        FREE(newptr);
603                        newptr = next;
604                    }
605                }
606                FREE(new_table->bins);
607                FREE(new_table);
608                return NIL(st_table);
609            }
610            *newt = *ptr;
611            newt->next = new_table->bins[i];
612            new_table->bins[i] = newt;
613            ptr = ptr->next;
614        }
615    }
616    return new_table;
617
618} /* st_copy */
619
620
621/**Function********************************************************************
622
623  Synopsis    [Delete the entry with the key pointed to by `keyp'.]
624
625  Description [Delete the entry with the key pointed to by `keyp'.  If
626  the entry is found, 1 is returned, the variable pointed by `keyp' is
627  set to the actual key and the variable pointed by `value' is set to
628  the corresponding entry.  (This allows the freeing of the associated
629  storage.)  If the entry is not found, then 0 is returned and nothing
630  is changed.]
631
632  SideEffects [None]
633
634  SeeAlso     [st_delete_int]
635
636******************************************************************************/
637int
638st_delete(st_table *table, void *keyp, void *value)
639{
640    int hash_val;
641    char *key = *(char **)keyp;
642    st_table_entry *ptr, **last;
643
644    hash_val = do_hash(key, table);
645
646    FIND_ENTRY(table, hash_val, key, ptr ,last);
647   
648    if (ptr == NIL(st_table_entry)) {
649        return 0;
650    }
651
652    *last = ptr->next;
653    if (value != NIL(void)) *(char **)value = ptr->record;
654    *(char **)keyp = ptr->key;
655    FREE(ptr);
656    table->num_entries--;
657    return 1;
658
659} /* st_delete */
660
661
662/**Function********************************************************************
663
664  Synopsis    [Delete the entry with the key pointed to by `keyp'.]
665
666  Description [Delete the entry with the key pointed to by `keyp'.
667  `value' must be a pointer to an integer.  If the entry is found, 1
668  is returned, the variable pointed by `keyp' is set to the actual key
669  and the variable pointed by `value' is set to the corresponding
670  entry.  (This allows the freeing of the associated storage.) If the
671  entry is not found, then 0 is returned and nothing is changed.]
672
673  SideEffects [None]
674
675  SeeAlso     [st_delete]
676
677******************************************************************************/
678int
679st_delete_int(st_table *table, void *keyp, int *value)
680{
681    int hash_val;
682    char *key = *(char **)keyp;
683    st_table_entry *ptr, **last;
684
685    hash_val = do_hash(key, table);
686
687    FIND_ENTRY(table, hash_val, key, ptr ,last);
688
689    if (ptr == NIL(st_table_entry)) {
690        return 0;
691    }
692
693    *last = ptr->next;
694    if (value != NIL(int)) *value = (int) (long) ptr->record;
695    *(char **)keyp = ptr->key;
696    FREE(ptr);
697    table->num_entries--;
698    return 1;
699
700} /* st_delete_int */
701
702
703/**Function********************************************************************
704
705  Synopsis    [Iterates over the elements of a table.]
706
707  Description [For each (key, value) record in `table', st_foreach
708  call func with the arguments
709  <pre>
710          (*func)(key, value, arg)
711  </pre>
712  If func returns ST_CONTINUE, st_foreach continues processing
713  entries.  If func returns ST_STOP, st_foreach stops processing and
714  returns immediately. If func returns ST_DELETE, then the entry is
715  deleted from the symbol table and st_foreach continues.  In the case
716  of ST_DELETE, it is func's responsibility to free the key and value,
717  if necessary.<p>
718
719  The routine returns 1 if all items in the table were generated and 0
720  if the generation sequence was aborted using ST_STOP.  The order in
721  which the records are visited will be seemingly random.]
722
723  SideEffects [None]
724
725  SeeAlso     [st_foreach_item st_foreach_item_int]
726
727******************************************************************************/
728int
729st_foreach(st_table *table, ST_PFSR func, char *arg)
730{
731    st_table_entry *ptr, **last;
732    enum st_retval retval;
733    int i;
734
735    for(i = 0; i < table->num_bins; i++) {
736        last = &table->bins[i]; ptr = *last;
737        while (ptr != NIL(st_table_entry)) {
738            retval = (*func)(ptr->key, ptr->record, arg);
739            switch (retval) {
740            case ST_CONTINUE:
741                last = &ptr->next; ptr = *last;
742                break;
743            case ST_STOP:
744                return 0;
745            case ST_DELETE:
746                *last = ptr->next;
747                table->num_entries--;   /* cstevens@ic */
748                FREE(ptr);
749                ptr = *last;
750            }
751        }
752    }
753    return 1;
754
755} /* st_foreach */
756
757
758/**Function********************************************************************
759
760  Synopsis    [String hash function.]
761
762  Description [String hash function.]
763
764  SideEffects [None]
765
766  SeeAlso     [st_init_table]
767
768******************************************************************************/
769int
770st_strhash(char *string, int modulus)
771{
772    int val = 0;
773    int c;
774   
775    while ((c = *string++) != '\0') {
776        val = val*997 + c;
777    }
778
779    return ((val < 0) ? -val : val)%modulus;
780
781} /* st_strhash */
782
783
784/**Function********************************************************************
785
786  Synopsis    [Number hash function.]
787
788  Description [Integer number hash function.]
789
790  SideEffects [None]
791
792  SeeAlso     [st_init_table st_numcmp]
793
794******************************************************************************/
795int
796st_numhash(char *x, int size)
797{
798    return ST_NUMHASH(x, size);
799
800} /* st_numhash */
801
802
803/**Function********************************************************************
804
805  Synopsis    [Pointer hash function.]
806
807  Description [Pointer hash function.]
808
809  SideEffects [None]
810
811  SeeAlso     [st_init_table st_ptrcmp]
812
813******************************************************************************/
814int
815st_ptrhash(char *x, int size)
816{
817    return ST_PTRHASH(x, size);
818
819} /* st_ptrhash */
820
821
822/**Function********************************************************************
823
824  Synopsis    [Number comparison function.]
825
826  Description [integer number comparison function.]
827
828  SideEffects [None]
829
830  SeeAlso     [st_init_table st_numhash]
831
832******************************************************************************/
833int
834st_numcmp(const char *x, const char *y)
835{
836    return ST_NUMCMP(x, y);
837
838} /* st_numcmp */
839
840
841/**Function********************************************************************
842
843  Synopsis    [Pointer comparison function.]
844
845  Description [Pointer comparison function.]
846
847  SideEffects [None]
848
849  SeeAlso     [st_init_table st_ptrhash]
850
851******************************************************************************/
852int
853st_ptrcmp(const char *x, const char *y)
854{
855    return ST_NUMCMP(x, y);
856
857} /* st_ptrcmp */
858
859
860/**Function********************************************************************
861
862  Synopsis    [Initializes a generator.]
863
864  Description [Returns a generator handle which when used with
865  st_gen() will progressively return each (key, value) record in
866  `table'.]
867
868  SideEffects [None]
869
870  SeeAlso     [st_free_gen]
871
872******************************************************************************/
873st_generator *
874st_init_gen(st_table *table)
875{
876    st_generator *gen;
877
878    gen = ALLOC(st_generator, 1);
879    if (gen == NIL(st_generator)) {
880        return NIL(st_generator);
881    }
882    gen->table = table;
883    gen->entry = NIL(st_table_entry);
884    gen->index = 0;
885    return gen;
886
887} /* st_init_gen */
888
889
890/**Function********************************************************************
891
892  Synopsis [returns the next (key, value) pair in the generation
893  sequence. ]
894
895  Description [Given a generator returned by st_init_gen(), this
896  routine returns the next (key, value) pair in the generation
897  sequence.  The pointer `value_p' can be zero which means no value
898  will be returned.  When there are no more items in the generation
899  sequence, the routine returns 0.
900
901  While using a generation sequence, deleting any (key, value) pair
902  other than the one just generated may cause a fatal error when
903  st_gen() is called later in the sequence and is therefore not
904  recommended.]
905
906  SideEffects [None]
907
908  SeeAlso     [st_gen_int]
909
910******************************************************************************/
911int
912st_gen(st_generator *gen, void *key_p, void *value_p)
913{
914    int i;
915
916    if (gen->entry == NIL(st_table_entry)) {
917        /* try to find next entry */
918        for(i = gen->index; i < gen->table->num_bins; i++) {
919            if (gen->table->bins[i] != NIL(st_table_entry)) {
920                gen->index = i+1;
921                gen->entry = gen->table->bins[i];
922                break;
923            }
924        }
925        if (gen->entry == NIL(st_table_entry)) {
926            return 0;           /* that's all folks ! */
927        }
928    }
929    *(char **)key_p = gen->entry->key;
930    if (value_p != NIL(void)) {
931        *(char **)value_p = gen->entry->record;
932    }
933    gen->entry = gen->entry->next;
934    return 1;
935
936} /* st_gen */
937
938
939/**Function********************************************************************
940
941  Synopsis    [Returns the next (key, value) pair in the generation
942  sequence.]
943
944  Description [Given a generator returned by st_init_gen(), this
945  routine returns the next (key, value) pair in the generation
946  sequence.  `value_p' must be a pointer to an integer.  The pointer
947  `value_p' can be zero which means no value will be returned.  When
948  there are no more items in the generation sequence, the routine
949  returns 0.]
950
951  SideEffects [None]
952
953  SeeAlso     [st_gen]
954
955******************************************************************************/
956int 
957st_gen_int(st_generator *gen, void *key_p, int *value_p)
958{
959    int i;
960
961    if (gen->entry == NIL(st_table_entry)) {
962        /* try to find next entry */
963        for(i = gen->index; i < gen->table->num_bins; i++) {
964            if (gen->table->bins[i] != NIL(st_table_entry)) {
965                gen->index = i+1;
966                gen->entry = gen->table->bins[i];
967                break;
968            }
969        }
970        if (gen->entry == NIL(st_table_entry)) {
971            return 0;           /* that's all folks ! */
972        }
973    }
974    *(char **)key_p = gen->entry->key;
975    if (value_p != NIL(int)) {
976        *value_p = (int) (long) gen->entry->record;
977    }
978    gen->entry = gen->entry->next;
979    return 1;
980
981} /* st_gen_int */
982
983
984/**Function********************************************************************
985
986  Synopsis    [Reclaims the resources associated with `gen'.]
987
988  Description [After generating all items in a generation sequence,
989  this routine must be called to reclaim the resources associated with
990  `gen'.]
991
992  SideEffects [None]
993
994  SeeAlso     [st_init_gen]
995
996******************************************************************************/
997void
998st_free_gen(st_generator *gen)
999{
1000    FREE(gen);
1001
1002} /* st_free_gen */
1003
1004
1005/*---------------------------------------------------------------------------*/
1006/* Definition of internal functions                                          */
1007/*---------------------------------------------------------------------------*/
1008
1009/*---------------------------------------------------------------------------*/
1010/* Definition of static functions                                            */
1011/*---------------------------------------------------------------------------*/
1012
1013/**Function********************************************************************
1014
1015  Synopsis    [Rehashes a symbol table.]
1016
1017  Description [Rehashes a symbol table.]
1018
1019  SideEffects [None]
1020
1021  SeeAlso     [st_insert]
1022
1023******************************************************************************/
1024static int
1025rehash(st_table *table)
1026{
1027    st_table_entry *ptr, *next, **old_bins;
1028    int             i, old_num_bins, hash_val, old_num_entries;
1029
1030    /* save old values */
1031    old_bins = table->bins;
1032    old_num_bins = table->num_bins;
1033    old_num_entries = table->num_entries;
1034
1035    /* rehash */
1036    table->num_bins = (int) (table->grow_factor * old_num_bins);
1037    if (table->num_bins % 2 == 0) {
1038        table->num_bins += 1;
1039    }
1040    table->num_entries = 0;
1041    table->bins = ALLOC(st_table_entry *, table->num_bins);
1042    if (table->bins == NIL(st_table_entry *)) {
1043        table->bins = old_bins;
1044        table->num_bins = old_num_bins;
1045        table->num_entries = old_num_entries;
1046        return ST_OUT_OF_MEM;
1047    }
1048    /* initialize */
1049    for (i = 0; i < table->num_bins; i++) {
1050        table->bins[i] = 0;
1051    }
1052
1053    /* copy data over */
1054    for (i = 0; i < old_num_bins; i++) {
1055        ptr = old_bins[i];
1056        while (ptr != NIL(st_table_entry)) {
1057            next = ptr->next;
1058            hash_val = do_hash(ptr->key, table);
1059            ptr->next = table->bins[hash_val];
1060            table->bins[hash_val] = ptr;
1061            table->num_entries++;
1062            ptr = next;
1063        }
1064    }
1065    FREE(old_bins);
1066
1067    return 1;
1068
1069} /* rehash */
Note: See TracBrowser for help on using the repository browser.