source: vis_dev/glu-2.3/src/st/st.c @ 91

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

library glu 2.3

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