cudd
3.0.0
The University of Colorado Decision Diagram Package
|
Symbol table package. More...
Go to the source code of this file.
Macros | |
#define | ST_OUT_OF_MEM -10000 |
Value returned if memory is exhausted. | |
#define | ST_DEFAULT_MAX_DENSITY 5 |
Default value for the maximum table density. More... | |
#define | ST_DEFAULT_INIT_TABLE_SIZE 11 |
Default value for the initial table size. More... | |
#define | ST_DEFAULT_GROW_FACTOR 2.0 |
Default table growth factor. More... | |
#define | ST_DEFAULT_REORDER_FLAG 0 |
Default table reorder flag. More... | |
#define | st_is_member(table, key) st_lookup(table,key,(void **) 0) |
Checks whethere key is in table . More... | |
#define | st_foreach_item(table, gen, key, value) for(gen=st_init_gen(table); st_gen(gen,key,value) || (st_free_gen(gen),0);) |
Iteration macro. More... | |
#define | st_foreach_item_int(table, gen, key, value) for(gen=st_init_gen(table); st_gen_int(gen,key,value) || (st_free_gen(gen),0);) |
Iteration macro. More... | |
Typedefs | |
typedef struct st_table | st_table |
Type of symbol tables. | |
typedef struct st_generator | st_generator |
Type of symbol table generators. | |
typedef enum st_retval(* | st_foreach_t) (void *, void *, void *) |
Type for function passed to st_foreach. | |
typedef int(* | st_compare_t) (void const *, void const *) |
Type of comparison functions. | |
typedef int(* | st_hash_t) (void const *, int) |
Type of hash functions. | |
typedef int(* | st_compare_arg_t) (void const *, void const *, void const *) |
Type of comparison functions with extra argument. | |
typedef int(* | st_hash_arg_t) (void const *, int, void const *) |
Type of hash functions with extra argument. | |
Enumerations | |
enum | st_retval { ST_CONTINUE, ST_STOP, ST_DELETE } |
Type of return values for iterators. | |
Functions | |
st_table * | st_init_table_with_params (st_compare_t, st_hash_t, int, int, double, int) |
Create a table with given parameters. More... | |
st_table * | st_init_table (st_compare_t, st_hash_t) |
Creates and initializes a table. More... | |
st_table * | st_init_table_with_params_and_arg (st_compare_arg_t, st_hash_arg_t, void const *, int, int, double, int) |
Creates and initializes a table. More... | |
st_table * | st_init_table_with_arg (st_compare_arg_t, st_hash_arg_t, void const *) |
Creates and initializes a table. More... | |
void | st_free_table (st_table *) |
Free a table. More... | |
int | st_lookup (st_table *, void const *, void **) |
Lookup up key in table . More... | |
int | st_lookup_int (st_table *, void const *, int *) |
Lookup up key in table . More... | |
int | st_insert (st_table *, void *, void *) |
Insert value in table under the key key . More... | |
int | st_add_direct (st_table *, void *, void *) |
Place 'value' in 'table' under the key 'key'. More... | |
int | st_find_or_add (st_table *, void *, void ***) |
Lookup key in table ; if not found, create an entry. More... | |
int | st_find (st_table *, void const *, void ***) |
Lookup key in table . More... | |
st_table * | st_copy (st_table const *) |
Returns a copy of old_table and all its members. More... | |
int | st_delete (st_table *, void **, void **) |
Deletes the entry with the key pointed to by keyp . More... | |
int | st_delete_int (st_table *, void **, int *) |
Deletes the entry with the key pointed to by keyp . More... | |
int | st_count (st_table const *) |
Returns the number of entries in the table table . More... | |
int | st_foreach (st_table *, st_foreach_t, void *) |
Iterates over the elements of a table. More... | |
int | st_strhash (void const *, int) |
String hash function. More... | |
int | st_numhash (void const *, int) |
Integral number hash function. More... | |
int | st_ptrhash (void const *, int) |
Pointer hash function. More... | |
int | st_numcmp (void const *, void const *) |
Integral number comparison function. More... | |
int | st_ptrcmp (void const *, void const *) |
Pointer comparison function. More... | |
st_generator * | st_init_gen (st_table const *) |
Initializes a generator. More... | |
int | st_gen (st_generator *, void **, void **) |
Returns the next (key, value) pair in the generation sequence. More... | |
int | st_gen_int (st_generator *, void **, int *) |
Returns the next (key, value) pair in the generation sequence. More... | |
void | st_free_gen (st_generator *) |
Reclaims the resources associated with gen . More... | |
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 ST_DEFAULT_GROW_FACTOR 2.0 |
Default table growth factor.
#define ST_DEFAULT_INIT_TABLE_SIZE 11 |
Default value for the initial table size.
#define ST_DEFAULT_MAX_DENSITY 5 |
Default value for the maximum table density.
#define ST_DEFAULT_REORDER_FLAG 0 |
Default table reorder flag.
#define st_foreach_item | ( | table, | |
gen, | |||
key, | |||
value | |||
) | for(gen=st_init_gen(table); st_gen(gen,key,value) || (st_free_gen(gen),0);) |
Iteration macro.
An iteration macro which loops over all the entries in table
, setting key
to point to the key and value
to the associated value (if it is not nil). gen
is a generator variable used internally. Sample usage:
void *key, *value; st_generator *gen; st_foreach_item(table, gen, &key, &value) { process_item(value); }
#define st_foreach_item_int | ( | table, | |
gen, | |||
key, | |||
value | |||
) | for(gen=st_init_gen(table); st_gen_int(gen,key,value) || (st_free_gen(gen),0);) |
Iteration macro.
An iteration macro which loops over all the entries in table
, setting key
to point to the key and value
to the associated value (if it is not nil). value
is assumed to be a pointer to an integer. gen
is a generator variable used internally. Sample usage:
void *key; int value; st_generator *gen; st_foreach_item_int(table, gen, &key, &value) { process_item(value); }
#define st_is_member | ( | table, | |
key | |||
) | st_lookup(table,key,(void **) 0) |
Checks whethere key
is in table
.
Returns 1 if there is an entry under key
in table
, 0 otherwise.
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 a copy of old_table and all its members.
(st_table *) 0 is returned if there was insufficient memory to do the copy.
int st_count | ( | st_table const * | table | ) |
Returns the number of entries in the table table
.
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.
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.
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.
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);
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.
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
.
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).
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.
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.
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
.
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.
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.
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);
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.
int st_insert | ( | st_table * | table, |
void * | key, | ||
void * | value | ||
) |
Insert value in table
under the key key
.
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.
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.
int st_numcmp | ( | void const * | x, |
void const * | y | ||
) |
int st_numhash | ( | void const * | x, |
int | size | ||
) |
int st_ptrcmp | ( | void const * | x, |
void const * | y | ||
) |
int st_ptrhash | ( | void const * | x, |
int | size | ||
) |
int st_strhash | ( | void const * | string, |
int | modulus | ||
) |