Azinix

st.c File Reference

Hash code. More...

#include <stdio.h>
#include "util.h"
#include "st.h"

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_tst_init_table_with_params (ST_PFI a, ST_PFI b, int c, int d, double e, int f)
Hash_tst_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_tst_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_tst_init_gen (Hash_t *a)
void st_free_gen (Hash_Generator_t *a)
Hash_tHash_InitTableWithParams (int(*compare)(), int(*hash)(), int size, int density, double grow_factor, int reorder_flag)
 The full blown table initializer.
Hash_tHash_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_tHash_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_tHash_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

Hash code.

Definition in file st.c.


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.

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_Insert ( Hash_t 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 otherewise. In either case the new value is added.

Definition at line 400 of file st.c.

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

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 return and value_ptr is unchanged.

Definition at line 311 of file st.c.

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

Lookup up int `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 return and int_ptr is unchanged.

Definition at line 348 of file st.c.

int Hash_NumCmp ( int  x,
int  y 
)

Compare function for numbers.

Definition at line 887 of file st.c.

int Hash_NumHash ( char *  x,
int  size 
)

Hash function for numbers.

Definition at line 870 of file st.c.

int Hash_PtrCmp ( char *  x,
char *  y 
)

Compare function for pointers.

Definition at line 896 of file st.c.

int Hash_PtrHash ( char *  x,
int  size 
)

Hash function for pointers.

Definition at line 878 of file st.c.

int Hash_StrHash ( char *  string,
int  modulus 
)

Hash function for strings.

Definition at line 854 of file st.c.

int Hash_StrHash_orig ( char *  string,
int  modulus 
)

Definition at line 837 of file st.c.

void Hash_Test (  ) 

Simple test of the hash package.

Definition at line 1031 of file st.c.

int st_add_direct ( Hash_t a,
char *  b,
char *  c 
)

Definition at line 90 of file st.c.

Hash_t* st_copy ( Hash_t a  ) 

Definition at line 102 of file st.c.

int st_delete ( Hash_t a,
char **  b,
char **  c 
)

Definition at line 106 of file st.c.

int st_delete_int ( Hash_t a,
int *  b,
char **  c 
)

Definition at line 110 of file st.c.

int st_find ( Hash_t a,
char *  b,
char ***  c 
)

Definition at line 98 of file st.c.

int st_find_or_add ( Hash_t a,
char *  b,
char ***  c 
)

Definition at line 94 of file st.c.

int st_foreach ( Hash_t a,
ST_PFSR  b,
char *  c 
)

Definition at line 114 of file st.c.

void st_free_gen ( Hash_Generator_t a  ) 

Definition at line 150 of file st.c.

void st_free_table ( Hash_t a  ) 

Definition at line 74 of file st.c.

int st_gen ( Hash_Generator_t a,
char **  b,
char **  c 
)

Definition at line 138 of file st.c.

int st_gen_int ( Hash_Generator_t a,
char **  b,
int *  c 
)

Definition at line 142 of file st.c.

Hash_Generator_t* st_init_gen ( Hash_t a  ) 

Definition at line 146 of file st.c.

Hash_t* st_init_table ( ST_PFI  a,
ST_PFI  b 
)

Definition at line 70 of file st.c.

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

AutomaticEnd

Definition at line 66 of file st.c.

int st_insert ( Hash_t a,
char *  b,
char *  c 
)

Definition at line 86 of file st.c.

int st_lookup ( Hash_t a,
char *  b,
char **  c 
)

Definition at line 78 of file st.c.

int st_lookup_int ( Hash_t a,
char *  b,
int *  c 
)

Definition at line 82 of file st.c.

int st_numcmp ( int  a,
int  b 
)

Definition at line 130 of file st.c.

int st_numhash ( char *  a,
int  b 
)

Definition at line 122 of file st.c.

int st_ptrcmp ( char *  a,
char *  b 
)

Definition at line 134 of file st.c.

int st_ptrhash ( char *  a,
int  b 
)

Definition at line 126 of file st.c.

int st_strhash ( char *  a,
int  b 
)

Definition at line 118 of file st.c.