st/st.c File Reference

Symbol table package. More...

#include "util.h"
#include "st.h"
Include dependency graph for st.c:

Data Structures

struct  st_table_entry
 Symbol table entry. More...
struct  st_table
 Symbol table header. More...
struct  st_generator
 Symbol table generator. More...

Defines

#define ST_NUMCMP(x, y)   ((x) != (y))
 Compares two numbers or two pointers.
#define ST_NUMHASH(x, size)   ((int)((uintptr_t)(x)%(uintptr_t)(size)))
 Hash function for numbers.
#define st_shift   2
 Amount by which pointers should be shifted right when hashing.
#define ST_PTRHASH(x, size)   ((int)(((uintptr_t)(x)>>st_shift)%(uintptr_t)(size)))
 Hash function for pointers.
#define EQUAL(table, x, y)
 Compares two entries.
#define do_hash(key, table)
 Computes the hash of one entry.
#define PTR_NOT_EQUAL(table, ptr, user_key)
 Compares the new key to one in a collision list.
#define FIND_ENTRY(table, hash_val, key, ptr, last)
 Looks up an entry in a collision list.
#define ADD_DIRECT(table, key, value, hash_val, newt)
 Adds an entry to a table.

Typedefs

typedef struct st_table_entry st_table_entry
 Type of symbol table entries.

Functions

st_tablest_init_table (st_compare_t compare, st_hash_t hash)
 Creates and initializes a table.
st_tablest_init_table_with_params (st_compare_t compare, st_hash_t hash, int size, int density, double grow_factor, int reorder_flag)
 Create a table with given parameters.
st_tablest_init_table_with_params_and_arg (st_compare_arg_t compare, st_hash_arg_t hash, void const *arg, int size, int density, double growth_factor, int reorder_flag)
 Creates and initializes a table.
st_tablest_init_table_with_arg (st_compare_arg_t compare, st_hash_arg_t hash, void const *arg)
 Creates and initializes a table.
void st_free_table (st_table *table)
 Free a table.
int st_lookup (st_table *table, void const *key, void **value)
 Lookup up `key` in `table`.
int st_lookup_int (st_table *table, void const *key, int *value)
 Lookup up `key` in `table`.
int st_insert (st_table *table, void *key, void *value)
 Insert value in `table` under the key `key`.
int st_add_direct (st_table *table, void *key, void *value)
 Place 'value' in 'table' under the key 'key'.
int st_find_or_add (st_table *table, void *key, void ***slot)
 Lookup `key` in `table`; if not found, create an entry.
int st_find (st_table *table, void const *key, void ***slot)
 Lookup `key` in `table`.
st_tablest_copy (st_table const *old_table)
 Returns a copy of old_table and all its members.
int st_delete (st_table *table, void **keyp, void **value)
 Deletes the entry with the key pointed to by `keyp`.
int st_delete_int (st_table *table, void **keyp, int *value)
 Deletes the entry with the key pointed to by `keyp`.
int st_count (st_table const *table)
 Returns the number of entries in the table `table`.
int st_foreach (st_table *table, st_foreach_t func, void *arg)
 Iterates over the elements of a table.
int st_strhash (void const *string, int modulus)
 String hash function.
int st_numhash (void const *x, int size)
 Integral number hash function.
int st_ptrhash (void const *x, int size)
 Pointer hash function.
int st_numcmp (void const *x, void const *y)
 Integral number comparison function.
int st_ptrcmp (void const *x, void const *y)
 Pointer comparison function.
st_generatorst_init_gen (st_table const *table)
 Initializes a generator.
int st_gen (st_generator *gen, void **key_p, void **value_p)
 Returns the next (key, value) pair in the generation sequence.
int st_gen_int (st_generator *gen, void **key_p, int *value_p)
 Returns the next (key, value) pair in the generation sequence.
void st_free_gen (st_generator *gen)
 Reclaims the resources associated with `gen`.
static int rehash (st_table *table)
 Rehashes a symbol table.

Detailed Description

Symbol table package.

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

Copyright (c) 1994-1998 The Regents of the Univ. of California. All rights reserved.

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

Copyright (c) 1999-2015, Regents of the University of Colorado

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


Define Documentation

#define ADD_DIRECT ( table,
key,
value,
hash_val,
newt   ) 
Value:
{\
    if (table->num_entries/table->num_bins >= table->max_density) {\
    rehash(table);\
    hash_val = do_hash(key,table);\
    }\
    \
    newt = ALLOC(st_table_entry, 1);\
    \
    newt->key = key;\
    newt->record = value;\
    newt->next = table->bins[hash_val];\
    table->bins[hash_val] = newt;\
    table->num_entries++;\
}

Adds an entry to a table.

Deprecated:
This macro does not check if memory allocation fails. Use at your own risk.
#define do_hash ( key,
table   ) 
Value:
(((table)->hash == st_ptrhash) ? ST_PTRHASH((key), (table)->num_bins) : \
     ((table)->hash == st_numhash) ? ST_NUMHASH((key), (table)->num_bins) : \
     ((table)->hash) ? (*(table)->hash)((key), (table)->num_bins) : \
     (*(table)->hash_arg)((key), (table)->num_bins, (table)->arg))

Computes the hash of one entry.

#define EQUAL ( table,
x,
 ) 
Value:
((((table)->compare == st_numcmp) || ((table)->compare == st_ptrcmp)) ?\
     (ST_NUMCMP((x),(y)) == 0) : ((table)->compare) ?\
     ((*(table)->compare)((x), (y)) == 0) :\
     ((*(table)->compare_arg)((x), (y), (table)->arg) == 0))

Compares two entries.

#define FIND_ENTRY ( table,
hash_val,
key,
ptr,
last   ) 
Value:
(last) = &(table)->bins[hash_val];\
    (ptr) = *(last);\
    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
    (last) = &(ptr)->next; (ptr) = *(last);\
    }\
    if ((ptr) != NIL(st_table_entry) && (table)->reorder_flag) {\
    *(last) = (ptr)->next;\
    (ptr)->next = (table)->bins[hash_val];\
    (table)->bins[hash_val] = (ptr);\
    }

Looks up an entry in a collision list.

If the entry is found and the reorder flag is set, the found entry is brought to the fore of the collision list.

#define PTR_NOT_EQUAL ( table,
ptr,
user_key   ) 
Value:
((ptr) != NIL(st_table_entry) && \
     !EQUAL((table), (user_key), (ptr)->key))

Compares the new key to one in a collision list.

#define ST_NUMCMP ( x,
 )     ((x) != (y))

Compares two numbers or two pointers.

Used by the default comparison functions.

#define st_shift   2

Amount by which pointers should be shifted right when hashing.

This is to discard bits that are (likely to be) 0 due to alignment constraints.


Function Documentation

static int rehash ( st_table table  )  [static]

Rehashes a symbol table.

Side effects
None
See also:
st_insert
int st_add_direct ( st_table table,
void *  key,
void *  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.
Side effects
None
See also:
st_lookup st_find_or_add
st_table* st_copy ( st_table const *  old_table  ) 

Returns a copy of old_table and all its members.

(st_table *) 0 is returned if there was insufficient memory to do the copy.

Side effects
None
int st_count ( st_table const *  table  ) 

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

Side effects
None
int st_delete ( st_table table,
void **  keyp,
void **  value 
)

Deletes the entry with the key pointed to by `keyp`.

If the entry is found, 1 is returned, the variable pointed by `keyp` is set to the actual key and the variable pointed by `value` 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.

Side effects
The locations pointed by keyp and value are modified.
See also:
st_delete_int
int st_delete_int ( st_table table,
void **  keyp,
int *  value 
)

Deletes the entry with the key pointed to by `keyp`.

`value` must be a pointer to an integer. If the entry is found, 1 is returned, the variable pointed by `keyp` is set to the actual key and the variable pointed by `value` 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.

Side effects
The locations pointed by keyp and value are modified.
See also:
st_delete
int st_find ( st_table table,
void const *  key,
void ***  slot 
)

Lookup `key` in `table`.

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

Side effects
The location pointed by slot is modified.
See also:
st_find_or_add
int st_find_or_add ( st_table table,
void *  key,
void ***  slot 
)

Lookup `key` in `table`; if not found, create an entry.

In either case set slot 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. As an example:

void **slot; void *key; void *value = 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);

Returns:
1 if an entry already existed, 0 if it did not exist and creation was successful; ST_OUT_OF_MEM otherwise.
Side effects
The location pointed by slot is modified.
See also:
st_find
int st_foreach ( st_table table,
st_foreach_t  func,
void *  arg 
)

Iterates over the elements of a table.

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 order in which the records are visited will be seemingly random.

Returns:
1 if all items in the table were generated and 0 if the generation sequence was aborted using ST_STOP.
Side effects
None
See also:
st_foreach_item st_foreach_item_int
void st_free_gen ( st_generator gen  ) 

Reclaims the resources associated with `gen`.

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

Side effects
None
See also:
st_init_gen
void st_free_table ( st_table table  ) 

Free a 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).

Side effects
None
See also:
st_init_table st_init_table_with_params
int st_gen ( st_generator gen,
void **  key_p,
void **  value_p 
)

Returns the next (key, value) pair in the generation sequence.

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.

Side effects
The locations pointed by key_p and value_p are modified.
See also:
st_gen_int
int st_gen_int ( st_generator gen,
void **  key_p,
int *  value_p 
)

Returns the next (key, value) pair in the generation sequence.

Given a generator returned by st_init_gen(), this routine returns the next (key, value) pair in the generation sequence. `value_p` 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.

Side effects
The locations pointed by key_p and value_p are modified.
See also:
st_gen
st_generator* st_init_gen ( st_table const *  table  ) 

Initializes a generator.

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

Side effects
None
See also:
st_free_gen
st_table* st_init_table ( st_compare_t  compare,
st_hash_t  hash 
)

Creates and initializes a table.

Creates and initializes a table with the comparison function compare_fn and hash function hash_fn. compare_fn is

int compare_fn(const void *key1, const void *key2)

It returns `<,=,> 0` depending on whether `key1 <,=,> key2` by some measure.

hash_fn is

int hash_fn(void *key, int modulus)

It returns an 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.

Side effects
None
See also:
st_init_table_with_params st_free_table
st_table* st_init_table_with_arg ( st_compare_arg_t  compare,
st_hash_arg_t  hash,
void const *  arg 
)

Creates and initializes a table.

Like st_init_table, but the comparison and hash functions are passed an extra parameter `arg` that is registered in the table at initialization.

See also:
st_init_table st_init_table_with_params_and_arg
st_table* st_init_table_with_params ( st_compare_t  compare,
st_hash_t  hash,
int  size,
int  density,
double  grow_factor,
int  reorder_flag 
)

Create a table with given parameters.

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);

Side effects
None
See also:
st_init_table st_free_table
st_table* st_init_table_with_params_and_arg ( st_compare_arg_t  compare,
st_hash_arg_t  hash,
void const *  arg,
int  size,
int  density,
double  growth_factor,
int  reorder_flag 
)

Creates and initializes a table.

Like st_init_table_with_params, but the comparison and hash functions are passed an extra parameter `arg` that is registered in the table at initialization.

See also:
st_init_table_with_params
int st_insert ( st_table table,
void *  key,
void *  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 otherwise. In either of the first two cases the new value is added.
Side effects
None
int st_lookup ( st_table table,
void const *  key,
void **  value 
)

Lookup up `key` in `table`.

If an entry is found, 1 is returned and if `value` is not nil, the variable it points to is set to the associated value. If an entry is not found, 0 is returned and the variable pointed by value is unchanged.

Side effects
The location pointed by value is modified.
See also:
st_lookup_int
int st_lookup_int ( st_table table,
void const *  key,
int *  value 
)

Lookup up `key` in `table`.

If an entry is found, 1 is returned and if `value` is not nil, the variable it points to is set to the associated integer value. If an entry is not found, 0 is return and the variable pointed by `value` is unchanged.

Side effects
The location pointed by value is modified.
See also:
st_lookup
int st_numcmp ( void const *  x,
void const *  y 
)

Integral number comparison function.

Side effects
None
See also:
st_init_table st_numhash
int st_numhash ( void const *  x,
int  size 
)

Integral number hash function.

Side effects
None
See also:
st_init_table st_numcmp
int st_ptrcmp ( void const *  x,
void const *  y 
)

Pointer comparison function.

Side effects
None
See also:
st_init_table st_ptrhash
int st_ptrhash ( void const *  x,
int  size 
)

Pointer hash function.

Side effects
None
See also:
st_init_table st_ptrcmp
int st_strhash ( void const *  string,
int  modulus 
)

String hash function.

Side effects
None
See also:
st_init_table
 All Data Structures Files Functions Variables Typedefs Enumerations Defines

Generated on 31 Dec 2015 for cudd by  doxygen 1.6.1