Data Structures
struct	di_hash_table
	Hash table. More...

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

Macros
#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_table *	di_hash_table_new (di_hash_func hash_func, di_equal_func key_equal_func)

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)

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_node *	internal_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)

Detailed Description

Macro Definition Documentation

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

Parameters

x	value
low	low bound
high	high bound

Returns: a value between low and high

#define HASH_TABLE_MAX_SIZE 13845163

The maximal hash table size

#define HASH_TABLE_MIN_SIZE 11

The minimal hash table size

Referenced by di_hash_table_new_full().

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

Defines if a resize is necessary

Parameters

hash_table a di_hash_table

Referenced by di_hash_table_insert().

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.

References di_free(), key_destroy_func, mem_chunk, nodes, size, and value_destroy_func.

Referenced by di_packages_free(), and di_release_free().

 {
   size_t i;
 
   for (i = 0; i < hash_table->size; i++)
     internal_di_hash_nodes_destroy (hash_table->nodes[i], hash_table->key_destroy_func, hash_table->value_destroy_func);
 
   di_mem_chunk_destroy (hash_table->mem_chunk);
 
   di_free (hash_table->nodes);
   di_free (hash_table);
 }

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.

References di_hash_node::key, di_hash_node::next, nodes, size, and di_hash_node::value.

 {
   di_hash_node *node;
   size_t i;
 
   for (i = 0; i < hash_table->size; i++)
     for (node = hash_table->nodes[i]; node; node = node->next)
       func (node->key, node->value, user_data);
 }

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.

References HASH_TABLE_RESIZE, key_destroy_func, nnodes, and value_destroy_func.

Referenced by di_packages_append_package(), and di_packages_get_package_new().

 {
   di_hash_node **node;
 
   node = internal_di_hash_table_lookup_node (hash_table, key);
 
   if (*node)
   {
     if (hash_table->key_destroy_func)
       hash_table->key_destroy_func (key);
 
     if (hash_table->value_destroy_func)
       hash_table->value_destroy_func ((*node)->value);
 
     (*node)->value = value;
   }
   else
   {
     *node = internal_di_hash_node_new (hash_table, key, value);
     hash_table->nnodes++;
     HASH_TABLE_RESIZE (hash_table);
   }
 }

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.

References di_hash_node::value.

Referenced by di_packages_get_package(), and di_parser_rfc822_read().

 {
   di_hash_node *node;
 
   node = *internal_di_hash_table_lookup_node (hash_table, key);
 
   return node ? node->value : NULL;
 }

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.

References di_hash_table_new_full().

 {
   return di_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
 }

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.

References di_mem_chunk_new(), di_new, hash_func, HASH_TABLE_MIN_SIZE, key_destroy_func, key_equal_func, mem_chunk, nnodes, nodes, size, and value_destroy_func.

Referenced by di_hash_table_new(), di_packages_alloc(), and di_release_alloc().

 {
   di_hash_table *hash_table;
   size_t i;
 
   hash_table = di_new (di_hash_table, 1);
   hash_table->size               = HASH_TABLE_MIN_SIZE;
   hash_table->nnodes             = 0;
   hash_table->mem_chunk          = di_mem_chunk_new (sizeof (di_hash_node), 4096);
   hash_table->hash_func          = hash_func;
   hash_table->key_equal_func     = key_equal_func;
   hash_table->key_destroy_func   = key_destroy_func;
   hash_table->value_destroy_func = value_destroy_func;
   hash_table->nodes              = di_new (di_hash_node*, hash_table->size);
 
   for (i = 0; i < hash_table->size; i++)
     hash_table->nodes[i] = NULL;
 
   return hash_table;
 }

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.

References nnodes.

 {
   return hash_table->nnodes;
 }

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

Function Documentation