# St Library Documentation

The st library provides functions to create, maintain, and query symbol tables.

- Basic Functions
  - `st_init_table`
  - `st_free_table`
  - `st_insert`
  - `st_lookup`
  - `st_is_member`
  - `st_delete`
  - `st_foreach`
  - `st_init_gen`
  - `st_gen`
  - `st_gen_int`
  - `st_free_gen`
  - `st_foreach_item`
  - `st_foreach_item_int`
  - `st_count`
- Fancier Functions
  - `st_init_table_with_params`
  - `st_find_or_add`
  - `st_find`
  - `st_add_direct`
  - `st_copy`

## Basic Functions

    st_table *st_init_table(compare_fn, hash_fn)
    int (*compare_fn);
    int (*hash_fn);

Create and initialize a table with the comparison function `compare_fn` and hash function `hash_fn`. `compare_fn` is

    	int compare_fn(char *key1, char *key2)
    	    /*
    	     * returns <,=,> 0 depending on whether
    	     * key1 <,=,> key2 by some measure
    	     */

and `hash_fn` is

    	int hash_fn(char *key, int modulus)
    	    /*
    	     * returns a integer between 0 and modulus-1
    	     * such that if compare_fn(key1,key2) == 0 then
    	     * hash_fn(key1) == hash_fn(key2)
    	     */

There are five predefined hash and comparison functions in st. For keys as numbers:

    	 st_numhash(key, modulus) { return (unsigned int) key % modulus; }
    	 st_numcmp(x,y) { return (int) x - (int) y; }

For keys as pointers:

    	 st_ptrhash(key, modulus) { return ((unsigned int) key/4) % modulus }
    	 st_ptrcmp(x,y) { return (int) x - (int) y; }

For keys as strings:

             st_strhash(x,y) - a reasonable hashing function for strings
    	 strcmp(x,y)     - the standard library function

It is recommended to use these particular functions if they fit your needs, since st will recognize certain of them and run more quickly because of it.

    void st_free_table(table)
    st_table *table;

Any internal storage associated with table is freed. It is the user's responsibility to free any storage associated with the pointers he placed in the table (by perhaps using `st_foreach`).

    int st_insert(table, key, value)
    st_table *table;
    char *key;
    char *value;

Insert value in table under the key '`key`'. Returns 1 if there was an entry already under the key, 0 if there was no entry under the key and insertion was successful; ST_OUT_OF_MEM otherewise. In either case the new value is added.

    int st_lookup(table, key, value_ptr)
    st_table *table;
    char *key;
    char **value_ptr;

Lookup up ``key`' in ``table`'. If an entry is found, 1 is returned and if ``value_ptr`' is not nil, the variable it points to is set to associated value. If an entry is not found, 0 is returned and `value_ptr` is unchanged.

    int st_lookup_int(table, key, int_ptr)
    st_table *table;
    char *key;
    int *int_ptr;

Lookup up ``key`' in ``table`'. If an entry is found, 1 is returned and if ``int_ptr`' is not nil, the variable it points to is set to associated integer value. If an entry is not found, 0 is returned and `int_ptr` is unchanged.

    int st_is_member(table, key)
    st_table *table;
    char *key;

Returns 1 if there is an entry under ``key`' in ``table`', 0 otherwise. This is a macro.

    int st_delete(table, key_ptr, entry_ptr)
    st_table *table;
    char **key_ptr;
    char **value_ptr;

Delete the entry with the key pointed to by ``key_ptr`'. If the entry is found, 1 is returned and ``key_ptr`' is set to the actual key and ``entry_ptr`' is set to the corresponding entry (This allows the freeing of the associated storage). If the entry is not found, then 0 is returned and nothing is changed.

    int st_delete_int(table, key_ptr, entry_ptr)
    st_table *table;
    int *key_ptr;
    char **value_ptr;

Delete the entry with the key pointed to by ``key_ptr`'. ``key_ptr`' should be specifically a pointer to an integer. If the entry is found, 1 is returned and ``key_ptr`' is set to the actual key and ``entry_ptr`' is set to the corresponding entry (This allows the freeing of the associated storage). If the entry is not found, then 0 is returned and nothing is changed.

    int st_foreach(table, func, arg)
    st_table table;
    enum st_retval (*func)();
    char *arg;

For each `(key, value)` record in ``table`', `st_foreach` calls `func` with the arguments

    	  (*func)(key, value, arg)

If `func` returns `ST_CONTINUE`, `st_foreach` continues processing entries. If `func` returns `ST_STOP`, `st_foreach` stops processing and returns immediately. If `func` returns `ST_DELETE`, then the entry is deleted from the symbol table and `st_foreach` continues. In the case of `ST_DELETE`, it is `func`'s responsibility to free the key and value, if necessary. The routine returns 1 if all items in the table were generated and 0 if the generation sequence was aborted using `ST_STOP`. The order in which the records are visited will be seemingly random.

    st_generator *st_init_gen(table)
    st_table *table;

Returns a generator handle which, when used with `st_gen()`, will progressively return each `(key, value)` record in ``table`'.

    int st_gen(gen, key_p, value_p)
    st_generator *gen;
    char **key_p;
    char **value_p;

Given a generator returned by `st_init_gen()`, this routine returns the next `(key, value)` pair in the generation sequence. The pointer ``value_p`' can be zero which means no value will be returned. When there are no more items in the generation sequence, the routine returns 0. While using a generation sequence, deleting any `(key, value)` pair other than the one just generated may cause a fatal error when `st_gen()` is called later in the sequence and is therefore not recommended.

    int st_gen_int(gen, key_p, value_p)
    st_generator *gen;
    char **key_p;
    int *value_p;

Given a generator returned by `st_init_gen()`, this routine returns the next `(key, value)` pair in the generation sequence. `value` must be a pointer to an integer. The pointer ``value_p`' can be zero which means no value will be returned. When there are no more items in the generation sequence, the routine returns 0.

    void st_free_gen(gen)
    st_generator *gen;

After generating all items in a generation sequence, this routine must be called to reclaim the resources associated with ``gen`'.

    st_foreach_item(table, gen, key_p, value_p)
    st_table *table;
    st_generator *gen;
    char **key_p;
    char **value_p;

An iteration macro which loops over all the entries in ``table`', setting ``key_p`' to point to the key and ``value_p`' to the associated value (if it is not nil). ``gen`' is a generator variable used internally. Sample usage:

         	char *key, *value;
    	st_generator *gen;

    	st_foreach_item(table, gen, &key, &value) {
    	    process_item(value);
    	}

    st_foreach_item_int(table, gen, key_p, value_p)
    st_table *table;
    st_generator *gen;
    char **key_p;
    int *value_p;

An iteration macro which loops over all the entries in ``table`', setting ``key_p`' to point to the key and ``value_p`' to the associated value (if it is not nil). ``value_p`' is assumed to be a pointer to an integer. ``gen`' is a generator variable used internally. Sample usage:

         	char *key;
    	int value;
    	st_generator *gen;

    	st_foreach_item(table, gen, &key, &value) {
    	    process_item(value);
    	}

    int st_count(table)
    st_table *table;

Returns the number of entries in the table ``table`'.

## Fancier Functions

    st_table *st_init_table_with_params(compare, hash, size, density, grow_factor,
                                        reorder_flag)
    int (*compare)();
    int (*hash)();
    int size;
    int density;
    double grow_factor;
    int reorder_flag;

The full blown table initializer. `compare` and `hash` are the same as in `st_init_table`. `density` is the largest the average number of entries per hash bin there should be before the table is grown. `grow_factor` is the factor the table is grown by when it becomes too full. `size` is the initial number of bins to be allocated for the hash table. If `reorder_flag` is non-zero, then every time an entry is found, it is moved to the top of the chain.

`st_init_table(compare, hash)` is equivelent to

        st_init_table_with_params(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,
    				     ST_DEFAULT_MAX_DENSITY,
    				     ST_DEFAULT_GROW_FACTOR,
    				     ST_DEFAULT_REORDER_FLAG);

    int st_find_or_add(table, key, slot_ptr)
    st_table *table;
    char *key;
    char ***slot_ptr;

Lookup ``key`' in ``table`'. If not found, create an entry. In either case set `slot_ptr` to point to the field in the entry where the value is stored. The value associated with ``key`' may then be changed by accessing directly through `slot_ptr`. Returns 1 if an entry already existed; 0 if it did not exist and creation was successful; ST_OUT_OF_MEM otherwise. As an example:

          char **slot;
          char *key;
          char *value = (char *) item_ptr /* ptr to a malloc'd structure */

          if (st_find_or_add(table, key, &slot) == 1) {
    	 FREE(*slot); /* free the old value of the record */
          }
          *slot = value;  /* attach the new value to the record */

This replaces the equivelent code:

          if (st_lookup(table, key, &ovalue) == 1) {
             FREE(ovalue);
          }
          st_insert(table, key, value);

    int st_find(table, key, slot_ptr)
    st_table *table;
    char *key;
    char ***slot_ptr;

Like `st_find_or_add`, but does not create an entry if one is not found.

    int st_add_direct(table, key, value)
    st_table *table;
    char *key;
    char *value;

Place '`value`' in '`table`' under the key '`key`'. This is done without checking if '`key`' is in '`table`' already. This should only be used if you are sure there is not already an entry for '`key`', since it is undefined which entry you would later get from `st_lookup` or `st_find_or_add`. Returns 1 if successful; ST_OUT_OF_MEM otherwise.

    st_table *st_copy(old_table)
    st_table *old_table;

Return a copy of `old_table` and all its members. `(st_table *) 0` is returned if there was insufficient memory to do the copy.