Azinix: st.c File Reference

Go to the source code of this file.


Defines
#define	PTR_NOT_EQUAL(table, ptr, user_key) (ptr != NIL(Hash_Entry_t) && !HASH_EQUAL(table->compare, user_key, (ptr)->key))
#define	FIND_ENTRY(table, hash_val, key, ptr, last)
#define	ADD_DIRECT(table, key, value, hash_val, newHash)
Functions
Hash_t *	st_init_table_with_params (ST_PFI a, ST_PFI b, int c, int d, double e, int f)
Hash_t *	st_init_table (ST_PFI a, ST_PFI b)
void	st_free_table (Hash_t *a)
int	st_lookup (Hash_t a, char b, char **c)
int	st_lookup_int (Hash_t a, char b, int *c)
int	st_insert (Hash_t a, char b, char *c)
int	st_add_direct (Hash_t a, char b, char *c)
int	st_find_or_add (Hash_t a, char b, char ***c)
int	st_find (Hash_t a, char b, char ***c)
Hash_t *	st_copy (Hash_t *a)
int	st_delete (Hash_t a, char b, char *c)
int	st_delete_int (Hash_t a, int b, char **c)
int	st_foreach (Hash_t a, ST_PFSR b, char c)
int	st_strhash (char *a, int b)
int	st_numhash (char *a, int b)
int	st_ptrhash (char *a, int b)
int	st_numcmp (int a, int b)
int	st_ptrcmp (char a, char b)
int	st_gen (Hash_Generator_t a, char b, char *c)
int	st_gen_int (Hash_Generator_t a, char b, int c)
Hash_Generator_t *	st_init_gen (Hash_t *a)
void	st_free_gen (Hash_Generator_t *a)
Hash_t *	Hash_InitTableWithParams (int(compare)(), int(hash)(), int size, int density, double grow_factor, int reorder_flag)
	The full blown table initializer.
Hash_t *	Hash_InitTable (int(compare)(), int(hash)())
	Create and initialize a table with the comparison function compare_fn and hash function hash_fn.
void	Hash_FreeTable (Hash_t *table)
	Free any internal storage associated with table.
int	Hash_Lookup (Hash_t table, char key, char **value)
	Lookup up `key' in `table'.
int	Hash_LookupInt (Hash_t table, char key, int *value)
	Lookup up int `key' in `table'.
int	Hash_Insert (Hash_t table, char key, char *value)
	Insert value in table under the key 'key'.
int	Hash_AddDirect (Hash_t table, char key, char *value)
	Place 'value' in 'table' under the key 'key'. This is done without checking if 'key' is in 'table' already.
int	Hash_FindOrAdd (Hash_t table, char key, char ***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. Returns 1 if an entry already existed, 0 otherwise.
int	Hash_Find (Hash_t table, char key, char ***slot)
	Like `Hash_FindOrAdd`, but does not create an entry if one is not found.
Hash_t *	Hash_Copy (Hash_t *old_table)
	Return a copy of old_table and all its members.
int	Hash_Delete (Hash_t table, char keyp, char *value)
	Delete the entry with the key pointed to by `key_ptr'.
int	Hash_DeleteInt (Hash_t table, int keyp, char **value)
	Delete the entry with the key pointed to by `key_ptr'.
int	Hash_ForEach (Hash_t table, enum st_retval(func)(), char *arg)
	For each (key, value) record in `table', Hash_ForEach call func with the arguments `(*func)(key, value, arg)`.
int	Hash_StrHash_orig (char *string, int modulus)
int	Hash_StrHash (char *string, int modulus)
	Hash function for strings.
int	Hash_NumHash (char *x, int size)
	Hash function for numbers.
int	Hash_PtrHash (char *x, int size)
	Hash function for pointers.
int	Hash_NumCmp (int x, int y)
	Compare function for numbers.
int	Hash_PtrCmp (char x, char y)
	Compare function for pointers.
Hash_Generator_t *	Hash_InitGen (Hash_t *table)
	Returns a generator handle which when used with Hash_Gen() will progressively return each (key, value) record in `table'.
int	Hash_Gen (Hash_Generator_t gen, char key_p, char *value_p)
	Given a generator returned by Hash_InitGen(), this routine returns the next (key, value) pair in the generation sequence.
int	Hash_GenInt (Hash_Generator_t gen, char key_p, int value_p)
	Given a generator returned by Hash_InitGen(), this routine returns the next (key, value) pair in the generation sequence.
void	Hash_FreeGen (Hash_Generator_t *gen)
	After generating all items in a generation sequence, this routine must be called to reclaim the resources associated with `gen'.
void	Hash_Test ()
	Simple test of the hash package.

Detailed Description

Define Documentation

#define ADD_DIRECT	(	table,
		key,
		value,
		hash_val,
		newHash	)

Value:

{\
    if (table->num_entries/table->num_bins >= table->max_density) {\
    rehash(table);\
    hash_val = do_hash(key,table);\
    }\
    \
    newHash = ALLOC(Hash_Entry_t, 1);\
    \
    newHash->key = key;\
    newHash->record = value;\
    newHash->next = table->bins[hash_val];\
    table->bins[hash_val] = newHash;\
    table->num_entries++;\
}

Definition at line 376 of file st.c.

#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(Hash_Entry_t) && (table)->reorder_flag) {\
    *(last) = (ptr)->next;\
    (ptr)->next = (table)->bins[hash_val];\
    (table)->bins[hash_val] = (ptr);\
    }

Definition at line 289 of file st.c.

#define PTR_NOT_EQUAL	(	table,
		ptr,
		user_key	)	(ptr != NIL(Hash_Entry_t) && !HASH_EQUAL(table->compare, user_key, (ptr)->key))

Definition at line 286 of file st.c.

Function Documentation

int Hash_AddDirect	(	Hash_t *	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 Hash_Lookup or Hash_FindOrAdd.

Definition at line 453 of file st.c.

Hash_t* Hash_Copy ( Hash_t * old_table )

Return a copy of old_table and all its members.

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

Definition at line 654 of file st.c.

int Hash_Delete	(	Hash_t *	table,
		char **	keyp,
		char **	value
	)

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.

Definition at line 714 of file st.c.

int Hash_DeleteInt	(	Hash_t *	table,
		int *	keyp,
		char **	value
	)

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.

Definition at line 752 of file st.c.

int Hash_Find	(	Hash_t *	table,
		char *	key,
		char ***	slot
	)

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

Definition at line 563 of file st.c.

int Hash_FindOrAdd	(	Hash_t *	table,
		char *	key,
		char ***	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. Returns 1 if an entry already existed, 0 otherwise.

As an example:

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

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

This replaces the equivelent code:

                                                                                                      
      if (Hash_Lookup(table, key, &ovalue)) {
         FREE(ovalue);
      }
      Hash_Insert(table, key, value);

Definition at line 513 of file st.c.

int Hash_ForEach	(	Hash_t *	table,
		enum st_retval(*)()	func,
		char *	arg
	)

For each (key, value) record in `table', Hash_ForEach call func with the arguments (*func)(key, value, arg).

If func returns ST_CONTINUE, Hash_ForEach continues processing entries. If func returns ST_STOP, Hash_ForEach stops processing and returns immediately. If func returns ST_DELETE, then the entry is deleted from the symbol table and Hash_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.

Definition at line 796 of file st.c.

void Hash_FreeGen ( Hash_Generator_t * gen )

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

Definition at line 1020 of file st.c.

void Hash_FreeTable ( Hash_t * table )

Free any internal storage associated with table.

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

Definition at line 266 of file st.c.

int Hash_Gen	(	Hash_Generator_t *	gen,
		char **	key_p,
		char **	value_p
	)

Given a generator returned by Hash_InitGen(), 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 Hash_Gen() is called later in the sequence and is therefore not recommended.

Definition at line 937 of file st.c.

int Hash_GenInt	(	Hash_Generator_t *	gen,
		char **	key_p,
		int *	value_p
	)

Given a generator returned by Hash_InitGen(), 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.

Definition at line 981 of file st.c.

Hash_Generator_t* Hash_InitGen ( Hash_t * table )

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

Definition at line 907 of file st.c.

Hash_t* Hash_InitTable	(	int(*)()	compare,
		int(*)()	hash
	)

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:

Hash_NumHash(key, modulus) { return (unsigned int) key % modulus; }

Hash_NumCmp(x,y) { return (int) x - (int) y; }

For keys as pointers:

Hash_PreHash(key, modulus) { return ((unsigned int) key/4) % modulus }

Hash_PtrCmp(x,y) { return (int) x - (int) y; }

For keys as strings:
```
Hash_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.

Definition at line 249 of file st.c.

Hash_t* Hash_InitTableWithParams	(	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 Hash_InitTable. 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 everytime an entry is found, it is moved to the top of the chain.

Hash_InitTable(compare, hash) is equivelent to

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

Definition at line 174 of file st.c.

int Hash_LookupInt	(	Hash_t *	table,
		char *	key,
		int *	value
	)

Hash_t* st_init_table_with_params	(	ST_PFI	a,
		ST_PFI	b,
		int	c,
		int	d,
		double	e,
		int	f
	)			`[inline]`

st.c File Reference

Defines

Functions

Detailed Description

Define Documentation

Function Documentation