distr/st/st.c

   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
  40 static char rcsid[] UTIL_UNUSED = " $Id: st.c,v 1.11 2004/02/11 22:31:59 fabio Exp fabio $";
  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
 106 static 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 ******************************************************************************/
 162 st_table *
 163 st_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 ******************************************************************************/
 198 st_table *
 199 st_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 ******************************************************************************/
 251 void
 252 st_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 ******************************************************************************/
 285 int
 286 st_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 ******************************************************************************/
 321 int
 322 st_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 ******************************************************************************/
 357 int
 358 st_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 ******************************************************************************/
 409 int
 410 st_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 ******************************************************************************/
 487 int
 488 st_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 ******************************************************************************/
 535 int
 536 st_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 ******************************************************************************/
 570 st_table *
 571 st_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 ******************************************************************************/
 633 int
 634 st_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 ******************************************************************************/
 674 int
 675 st_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 ******************************************************************************/
 724 int
 725 st_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 ******************************************************************************/
 765 int
 766 st_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 ******************************************************************************/
 791 int
 792 st_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 ******************************************************************************/
 810 int
 811 st_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 ******************************************************************************/
 829 int
 830 st_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 ******************************************************************************/
 848 int
 849 st_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 ******************************************************************************/
 869 st_generator *
 870 st_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 ******************************************************************************/
 907 int
 908 st_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 ******************************************************************************/
 952 int
 953 st_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 ******************************************************************************/
 993 void
 994 st_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 ******************************************************************************/
1020 static int
1021 rehash(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 */