Simple hash table
[Hash functions]


Data Structures

struct  di_hash_table
 Hash table. More...
struct  di_hash_node
 Node of a hash table. More...

Defines

#define HASH_TABLE_RESIZE(hash_table)
#define HASH_TABLE_MIN_SIZE   11
#define HASH_TABLE_MAX_SIZE   13845163
#define CLAMP(x, low, high)   (((x) > (high)) ? (high) : (((x) < (low)) ? (low) : (x)))

Functions

di_hash_tabledi_hash_table_new (di_hash_func hash_func, di_equal_func key_equal_func)
di_hash_tabledi_hash_table_new_full (di_hash_func hash_func, di_equal_func key_equal_func, di_destroy_notify key_destroy_func, di_destroy_notify value_destroy_func)
void di_hash_table_destroy (di_hash_table *hash_table)
void di_hash_table_insert (di_hash_table *hash_table, void *key, void *value)
void * di_hash_table_lookup (di_hash_table *hash_table, const void *key)
void di_hash_table_foreach (di_hash_table *hash_table, di_hfunc *func, void *user_data)
di_ksize_t di_hash_table_size (di_hash_table *hash_table)
static void internal_di_hash_table_resize (di_hash_table *hash_table)
static di_hash_node ** internal_di_hash_table_lookup_node (di_hash_table *hash_table, const void *key)
static di_hash_nodeinternal_di_hash_node_new (di_hash_table *hash_table, void *key, void *value)
static void internal_di_hash_node_destroy (di_hash_node *hash_node, di_destroy_notify key_destroy_func, di_destroy_notify value_destroy_func) __attribute__((unused))
static void internal_di_hash_nodes_destroy (di_hash_node *hash_node, di_destroy_notify key_destroy_func, di_destroy_notify value_destroy_func)

Define Documentation

#define CLAMP ( x,
low,
high   )     (((x) > (high)) ? (high) : (((x) < (low)) ? (low) : (x)))

For internal use only.

Parameters:
x value
low low bound
high high bound
Returns:
a value between low and high

#define HASH_TABLE_MAX_SIZE   13845163

For internal use only.

The maximal hash table size

#define HASH_TABLE_MIN_SIZE   11

For internal use only.

The minimal hash table size

#define HASH_TABLE_RESIZE ( hash_table   ) 

Value:

if ((hash_table->size >= 3 * hash_table->nnodes &&      \
      hash_table->size > HASH_TABLE_MIN_SIZE) ||        \
    (3 * hash_table->size <= hash_table->nnodes &&      \
     hash_table->size < HASH_TABLE_MAX_SIZE))           \
     internal_di_hash_table_resize (hash_table);

For internal use only.

Defines if a resize is necessary

Parameters:
hash_table a di_hash_table


Function Documentation

void di_hash_table_destroy ( di_hash_table hash_table  ) 

Destroys the di_hash_table. If keys and/or values are dynamically allocated, you should either free them first or create the di_hash_table using di_hash_table_new_full. In the latter case the destroy functions you supplied will be called on all keys and values before destroying the di_hash_table.

Parameters:
hash_table a di_hash_table.
00138 {
00139   size_t i;
00140 
00141   for (i = 0; i < hash_table->size; i++)
00142     internal_di_hash_nodes_destroy (hash_table->nodes[i], hash_table->key_destroy_func, hash_table->value_destroy_func);
00143 
00144   di_mem_chunk_destroy (hash_table->mem_chunk);
00145 
00146   di_free (hash_table->nodes);
00147   di_free (hash_table);
00148 }

void di_hash_table_foreach ( di_hash_table hash_table,
di_hfunc *  func,
void *  user_data 
)

Calls the given function for each of the key/value pairs in the di_hash_table. The function is passed the key and value of each pair, and the given user_data parameter.

Postcondition:
The hash table may not be modified while iterating over it (you can't add/remove items).
Parameters:
hash_table a di_hash_table.
func the function to call for each key/value pair.
user_data user data to pass to the function.
00250 {
00251   di_hash_node *node;
00252   size_t i;
00253 
00254   for (i = 0; i < hash_table->size; i++)
00255     for (node = hash_table->nodes[i]; node; node = node->next)
00256       func (node->key, node->value, user_data);
00257 }

void di_hash_table_insert ( di_hash_table hash_table,
void *  key,
void *  value 
)

Inserts a new key and value into a di_hash_table.

If the key already exists in the di_hash_table its current value is replaced with the new value. If you supplied a value_destroy_func when creating the di_hash_table, the old value is freed using that function. If you supplied a key_destroy_func when creating the di_hash_table, the passed key is freed using that function.

Parameters:
hash_table a di_hash_table.
key a key to insert.
value the value to associate with the key.
00182 {
00183   di_hash_node **node;
00184 
00185   node = internal_di_hash_table_lookup_node (hash_table, key);
00186 
00187   if (*node)
00188   {
00189     if (hash_table->key_destroy_func)
00190       hash_table->key_destroy_func (key);
00191 
00192     if (hash_table->value_destroy_func)
00193       hash_table->value_destroy_func ((*node)->value);
00194 
00195     (*node)->value = value;
00196   }
00197   else
00198   {
00199     *node = internal_di_hash_node_new (hash_table, key, value);
00200     hash_table->nnodes++;
00201     HASH_TABLE_RESIZE (hash_table);
00202   }
00203 }

void* di_hash_table_lookup ( di_hash_table hash_table,
const void *  key 
)

Looks up a key in a di_hash_table.

Parameters:
hash_table a di_hash_table,
key the key to look up.
Returns:
the associated value, or NULL if the key is not found.
00173 {
00174   di_hash_node *node;
00175 
00176   node = *internal_di_hash_table_lookup_node (hash_table, key);
00177 
00178   return node ? node->value : NULL;
00179 }

di_hash_table* di_hash_table_new ( di_hash_func  hash_func,
di_equal_func  key_equal_func 
)

Creates a new di_hash_table.

Parameters:
hash_func a function to create a hash value from a key. Hash values are used to determine where keys are stored within the di_hash_table data structure.
key_equal_func a function to check two keys for equality. This is used when looking up keys in the di_hash_table.
Returns:
a new di_hash_table.
00112 {
00113   return di_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
00114 }

di_hash_table* di_hash_table_new_full ( di_hash_func  hash_func,
di_equal_func  key_equal_func,
di_destroy_notify  key_destroy_func,
di_destroy_notify  value_destroy_func 
)

Creates a new di_hash_table like di_hash_table_new and allows to specify functions to free the memory allocated for the key and value that get called when removing the entry from the di_hash_table

Parameters:
hash_func a function to create a hash value from a key. Hash values are used to determine where keys are stored within the di_hash_table data structure.
key_equal_func a function to check two keys for equality. This is used when looking up keys in the di_hash_table.
key_destroy_func a function to free the memory allocated for the key used when removing the entry from the di_hash_table or NULL if you don't want to supply such a function.
value_destroy_func a function to free the memory allocated for the value used when removing the entry from the di_hash_table or NULL if you don't want to supply such a function.
Returns:
a new di_hash_table.
00117 {
00118   di_hash_table *hash_table;
00119   size_t i;
00120 
00121   hash_table = di_new (di_hash_table, 1);
00122   hash_table->size               = HASH_TABLE_MIN_SIZE;
00123   hash_table->nnodes             = 0;
00124   hash_table->mem_chunk          = di_mem_chunk_new (sizeof (di_hash_node), 4096);
00125   hash_table->hash_func          = hash_func;
00126   hash_table->key_equal_func     = key_equal_func;
00127   hash_table->key_destroy_func   = key_destroy_func;
00128   hash_table->value_destroy_func = value_destroy_func;
00129   hash_table->nodes              = di_new (di_hash_node*, hash_table->size);
00130 
00131   for (i = 0; i < hash_table->size; i++)
00132     hash_table->nodes[i] = NULL;
00133 
00134   return hash_table;
00135 }

di_ksize_t di_hash_table_size ( di_hash_table hash_table  ) 

Returns the number of elements contained in the di_hash_table.

Parameters:
hash_table a di_hash_table.
Returns:
the number of key/value pairs.
00260 {
00261   return hash_table->nnodes;
00262 }


Generated on Sat Sep 29 08:45:16 2007 for libdebian-installer by  doxygen 1.5.1