1 /**CFile***********************************************************************
7 Synopsis [Symbol table package.]
9 Description [The st library provides functions to create, maintain,
10 and query symbol tables.]
18 ******************************************************************************/
23 /*---------------------------------------------------------------------------*/
24 /* Constant declarations */
25 /*---------------------------------------------------------------------------*/
27 /*---------------------------------------------------------------------------*/
28 /* Stucture declarations */
29 /*---------------------------------------------------------------------------*/
31 /*---------------------------------------------------------------------------*/
32 /* Type declarations */
33 /*---------------------------------------------------------------------------*/
35 /*---------------------------------------------------------------------------*/
36 /* Variable declarations */
37 /*---------------------------------------------------------------------------*/
40 static char rcsid
[] UTIL_UNUSED
= " $Id: st.c,v 1.11 2004/02/11 22:31:59 fabio Exp fabio $";
43 /*---------------------------------------------------------------------------*/
44 /* Macro declarations */
45 /*---------------------------------------------------------------------------*/
47 #define ST_NUMCMP(x,y) ((x) != (y))
49 #define ST_NUMHASH(x,size) (ABS((long)x)%(size))
51 #if SIZEOF_VOID_P == 8
57 #define ST_PTRHASH(x,size) ((unsigned int)((unsigned long)(x)>>st_shift)%size)
59 #define EQUAL(func, x, y) \
60 ((((func) == st_numcmp) || ((func) == st_ptrcmp)) ?\
61 (ST_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))
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)))
68 #define PTR_NOT_EQUAL(table, ptr, user_key)\
69 (ptr != NIL(st_table_entry) && !EQUAL(table->compare, (char *)user_key, (ptr)->key))
71 #define FIND_ENTRY(table, hash_val, key, ptr, last) \
72 (last) = &(table)->bins[hash_val];\
74 while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
75 (last) = &(ptr)->next; (ptr) = *(last);\
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);\
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)\
86 if (table->num_entries/table->num_bins >= table->max_density) {\
88 hash_val = do_hash(key,table);\
91 newt = ALLOC(st_table_entry, 1);\
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++;\
100 /**AutomaticStart*************************************************************/
102 /*---------------------------------------------------------------------------*/
103 /* Static function prototypes */
104 /*---------------------------------------------------------------------------*/
106 static int rehash (st_table
*);
108 /**AutomaticEnd***************************************************************/
111 /*---------------------------------------------------------------------------*/
112 /* Definition of exported functions */
113 /*---------------------------------------------------------------------------*/
115 /**Function********************************************************************
117 Synopsis [Create and initialize a table.]
119 Description [Create and initialize a table with the comparison function
120 compare_fn and hash function hash_fn. compare_fn is
122 int compare_fn(const char *key1, const char *key2)
124 It returns <,=,> 0 depending on whether key1 <,=,> key2 by some measure.<p>
127 int hash_fn(char *key, int modulus)
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.
134 st_numhash(key, modulus) { return (unsigned int) key % modulus; }
137 st_numcmp(x,y) { return (int) x - (int) y; }
139 For keys as pointers:
141 st_ptrhash(key, modulus) { return ((unsigned int) key/4) % modulus }
144 st_ptrcmp(x,y) { return (int) x - (int) y; }
148 st_strhash(x,y) - a reasonable hashing function for strings
151 strcmp(x,y) - the standard library function
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
159 SeeAlso [st_init_table_with_params st_free_table]
161 ******************************************************************************/
163 st_init_table(ST_PFICPCP compare
, ST_PFICPI hash
)
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
);
170 } /* st_init_table */
173 /**Function********************************************************************
175 Synopsis [Create a table with given parameters.]
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
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);
195 SeeAlso [st_init_table st_free_table]
197 ******************************************************************************/
199 st_init_table_with_params(
210 newt
= ALLOC(st_table
, 1);
211 if (newt
== NIL(st_table
)) {
212 return NIL(st_table
);
214 newt
->compare
= compare
;
216 newt
->num_entries
= 0;
217 newt
->max_density
= density
;
218 newt
->grow_factor
= grow_factor
;
219 newt
->reorder_flag
= reorder_flag
;
223 newt
->num_bins
= size
;
224 newt
->bins
= ALLOC(st_table_entry
*, size
);
225 if (newt
->bins
== NIL(st_table_entry
*)) {
227 return NIL(st_table
);
229 for(i
= 0; i
< size
; i
++) {
234 } /* st_init_table_with_params */
237 /**Function********************************************************************
239 Synopsis [Free a table.]
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
248 SeeAlso [st_init_table st_init_table_with_params]
250 ******************************************************************************/
252 st_free_table(st_table
*table
)
254 st_table_entry
*ptr
, *next
;
257 for(i
= 0; i
< table
->num_bins
; i
++) {
258 ptr
= table
->bins
[i
];
259 while (ptr
!= NIL(st_table_entry
)) {
268 } /* st_free_table */
271 /**Function********************************************************************
273 Synopsis [Lookup up `key' in `table'.]
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.]
282 SeeAlso [st_lookup_int]
284 ******************************************************************************/
286 st_lookup(st_table
*table
, void *key
, void *value
)
289 st_table_entry
*ptr
, **last
;
291 hash_val
= do_hash(key
, table
);
293 FIND_ENTRY(table
, hash_val
, key
, ptr
, last
);
295 if (ptr
== NIL(st_table_entry
)) {
298 if (value
!= NIL(void)) {
299 *(char **)value
= ptr
->record
;
307 /**Function********************************************************************
309 Synopsis [Lookup up `key' in `table'.]
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.]
320 ******************************************************************************/
322 st_lookup_int(st_table
*table
, void *key
, int *value
)
325 st_table_entry
*ptr
, **last
;
327 hash_val
= do_hash(key
, table
);
329 FIND_ENTRY(table
, hash_val
, key
, ptr
, last
);
331 if (ptr
== NIL(st_table_entry
)) {
334 if (value
!= NIL(int)) {
335 *value
= (int) (long) ptr
->record
;
340 } /* st_lookup_int */
343 /**Function********************************************************************
345 Synopsis [Insert value in table under the key 'key'.]
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.]
356 ******************************************************************************/
358 st_insert(st_table
*table
, void *key
, void *value
)
361 st_table_entry
*newt
;
362 st_table_entry
*ptr
, **last
;
364 hash_val
= do_hash(key
, table
);
366 FIND_ENTRY(table
, hash_val
, key
, ptr
, last
);
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
;
373 hash_val
= do_hash(key
, table
);
375 newt
= ALLOC(st_table_entry
, 1);
376 if (newt
== NIL(st_table_entry
)) {
377 return ST_OUT_OF_MEM
;
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
++;
386 ptr
->record
= (char *)value
;
393 /**Function********************************************************************
395 Synopsis [Place 'value' in 'table' under the key 'key'.]
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
408 ******************************************************************************/
410 st_add_direct(st_table
*table
, void *key
, void *value
)
413 st_table_entry
*newt
;
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
;
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
;
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
++;
433 } /* st_add_direct */
436 /**Function********************************************************************
438 Synopsis [Lookup `key' in `table'.]
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:
453 char *value = (char *) item_ptr <-- ptr to a malloc'd structure
456 if (st_find_or_add(table, key, &slot) == 1) {
459 FREE(*slot); <-- free the old value of the record
465 *slot = value; <-- attach the new value to the record
467 This replaces the equivelent code:
469 if (st_lookup(table, key, &ovalue) == 1) {
478 st_insert(table, key, value);
486 ******************************************************************************/
488 st_find_or_add(st_table
*table
, void *key
, void *slot
)
491 st_table_entry
*newt
, *ptr
, **last
;
493 hash_val
= do_hash(key
, table
);
495 FIND_ENTRY(table
, hash_val
, key
, ptr
, last
);
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
;
502 hash_val
= do_hash(key
, table
);
504 newt
= ALLOC(st_table_entry
, 1);
505 if (newt
== NIL(st_table_entry
)) {
506 return ST_OUT_OF_MEM
;
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
;
516 if (slot
!= NIL(void)) *(char ***)slot
= &ptr
->record
;
520 } /* st_find_or_add */
523 /**Function********************************************************************
525 Synopsis [Lookup `key' in `table'.]
527 Description [Like st_find_or_add, but does not create an entry if
532 SeeAlso [st_find_or_add]
534 ******************************************************************************/
536 st_find(st_table
*table
, void *key
, void *slot
)
539 st_table_entry
*ptr
, **last
;
541 hash_val
= do_hash(key
, table
);
543 FIND_ENTRY(table
, hash_val
, key
, ptr
, last
);
545 if (ptr
== NIL(st_table_entry
)) {
548 if (slot
!= NIL(void)) {
549 *(char ***)slot
= &ptr
->record
;
557 /**Function********************************************************************
559 Synopsis [Return a copy of old_table and all its members.]
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
569 ******************************************************************************/
571 st_copy(st_table
*old_table
)
574 st_table_entry
*ptr
, *newptr
, *next
, *newt
;
575 int i
, j
, num_bins
= old_table
->num_bins
;
577 new_table
= ALLOC(st_table
, 1);
578 if (new_table
== NIL(st_table
)) {
579 return NIL(st_table
);
582 *new_table
= *old_table
;
583 new_table
->bins
= ALLOC(st_table_entry
*, num_bins
);
584 if (new_table
->bins
== NIL(st_table_entry
*)) {
586 return NIL(st_table
);
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
)) {
602 FREE(new_table
->bins
);
604 return NIL(st_table
);
607 newt
->next
= new_table
->bins
[i
];
608 new_table
->bins
[i
] = newt
;
617 /**Function********************************************************************
619 Synopsis [Delete the entry with the key pointed to by `keyp'.]
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
630 SeeAlso [st_delete_int]
632 ******************************************************************************/
634 st_delete(st_table
*table
, void *keyp
, void *value
)
637 char *key
= *(char **)keyp
;
638 st_table_entry
*ptr
, **last
;
640 hash_val
= do_hash(key
, table
);
642 FIND_ENTRY(table
, hash_val
, key
, ptr
,last
);
644 if (ptr
== NIL(st_table_entry
)) {
649 if (value
!= NIL(void)) *(char **)value
= ptr
->record
;
650 *(char **)keyp
= ptr
->key
;
652 table
->num_entries
--;
658 /**Function********************************************************************
660 Synopsis [Delete the entry with the key pointed to by `keyp'.]
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.]
673 ******************************************************************************/
675 st_delete_int(st_table
*table
, void *keyp
, int *value
)
678 char *key
= *(char **)keyp
;
679 st_table_entry
*ptr
, **last
;
681 hash_val
= do_hash(key
, table
);
683 FIND_ENTRY(table
, hash_val
, key
, ptr
,last
);
685 if (ptr
== NIL(st_table_entry
)) {
690 if (value
!= NIL(int)) *value
= (int) (long) ptr
->record
;
691 *(char **)keyp
= ptr
->key
;
693 table
->num_entries
--;
696 } /* st_delete_int */
699 /**Function********************************************************************
701 Synopsis [Iterates over the elements of a table.]
703 Description [For each (key, value) record in `table', st_foreach
704 call func with the arguments
706 (*func)(key, value, arg)
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,
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.]
721 SeeAlso [st_foreach_item st_foreach_item_int]
723 ******************************************************************************/
725 st_foreach(st_table
*table
, ST_PFSR func
, char *arg
)
727 st_table_entry
*ptr
, **last
;
728 enum st_retval retval
;
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
);
737 last
= &ptr
->next
; ptr
= *last
;
743 table
->num_entries
--; /* cstevens@ic */
754 /**Function********************************************************************
756 Synopsis [String hash function.]
758 Description [String hash function.]
762 SeeAlso [st_init_table]
764 ******************************************************************************/
766 st_strhash(char *string
, int modulus
)
771 while ((c
= *string
++) != '\0') {
775 return ((val
< 0) ? -val
: val
)%modulus
;
780 /**Function********************************************************************
782 Synopsis [Number hash function.]
784 Description [Integer number hash function.]
788 SeeAlso [st_init_table st_numcmp]
790 ******************************************************************************/
792 st_numhash(char *x
, int size
)
794 return ST_NUMHASH(x
, size
);
799 /**Function********************************************************************
801 Synopsis [Pointer hash function.]
803 Description [Pointer hash function.]
807 SeeAlso [st_init_table st_ptrcmp]
809 ******************************************************************************/
811 st_ptrhash(char *x
, int size
)
813 return ST_PTRHASH(x
, size
);
818 /**Function********************************************************************
820 Synopsis [Number comparison function.]
822 Description [integer number comparison function.]
826 SeeAlso [st_init_table st_numhash]
828 ******************************************************************************/
830 st_numcmp(const char *x
, const char *y
)
832 return ST_NUMCMP(x
, y
);
837 /**Function********************************************************************
839 Synopsis [Pointer comparison function.]
841 Description [Pointer comparison function.]
845 SeeAlso [st_init_table st_ptrhash]
847 ******************************************************************************/
849 st_ptrcmp(const char *x
, const char *y
)
851 return ST_NUMCMP(x
, y
);
856 /**Function********************************************************************
858 Synopsis [Initializes a generator.]
860 Description [Returns a generator handle which when used with
861 st_gen() will progressively return each (key, value) record in
866 SeeAlso [st_free_gen]
868 ******************************************************************************/
870 st_init_gen(st_table
*table
)
874 gen
= ALLOC(st_generator
, 1);
875 if (gen
== NIL(st_generator
)) {
876 return NIL(st_generator
);
879 gen
->entry
= NIL(st_table_entry
);
886 /**Function********************************************************************
888 Synopsis [returns the next (key, value) pair in the generation
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.
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
906 ******************************************************************************/
908 st_gen(st_generator
*gen
, void *key_p
, void *value_p
)
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
)) {
917 gen
->entry
= gen
->table
->bins
[i
];
921 if (gen
->entry
== NIL(st_table_entry
)) {
922 return 0; /* that's all folks ! */
925 *(char **)key_p
= gen
->entry
->key
;
926 if (value_p
!= NIL(void)) {
927 *(char **)value_p
= gen
->entry
->record
;
929 gen
->entry
= gen
->entry
->next
;
935 /**Function********************************************************************
937 Synopsis [Returns the next (key, value) pair in the generation
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
951 ******************************************************************************/
953 st_gen_int(st_generator
*gen
, void *key_p
, int *value_p
)
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
)) {
962 gen
->entry
= gen
->table
->bins
[i
];
966 if (gen
->entry
== NIL(st_table_entry
)) {
967 return 0; /* that's all folks ! */
970 *(char **)key_p
= gen
->entry
->key
;
971 if (value_p
!= NIL(int)) {
972 *value_p
= (int) (long) gen
->entry
->record
;
974 gen
->entry
= gen
->entry
->next
;
980 /**Function********************************************************************
982 Synopsis [Reclaims the resources associated with `gen'.]
984 Description [After generating all items in a generation sequence,
985 this routine must be called to reclaim the resources associated with
990 SeeAlso [st_init_gen]
992 ******************************************************************************/
994 st_free_gen(st_generator
*gen
)
1001 /*---------------------------------------------------------------------------*/
1002 /* Definition of internal functions */
1003 /*---------------------------------------------------------------------------*/
1005 /*---------------------------------------------------------------------------*/
1006 /* Definition of static functions */
1007 /*---------------------------------------------------------------------------*/
1009 /**Function********************************************************************
1011 Synopsis [Rehashes a symbol table.]
1013 Description [Rehashes a symbol table.]
1019 ******************************************************************************/
1021 rehash(st_table
*table
)
1023 st_table_entry
*ptr
, *next
, **old_bins
;
1024 int i
, old_num_bins
, hash_val
, old_num_entries
;
1026 /* save old values */
1027 old_bins
= table
->bins
;
1028 old_num_bins
= table
->num_bins
;
1029 old_num_entries
= table
->num_entries
;
1032 table
->num_bins
= (int) (table
->grow_factor
* old_num_bins
);
1033 if (table
->num_bins
% 2 == 0) {
1034 table
->num_bins
+= 1;
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
;
1045 for (i
= 0; i
< table
->num_bins
; i
++) {
1049 /* copy data over */
1050 for (i
= 0; i
< old_num_bins
; i
++) {
1052 while (ptr
!= NIL(st_table_entry
)) {
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
++;