Di_hash_table

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

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

## CLAMP

#define CLAMP | ( |  | x,
|  |  | low,
|  |  | high )

Value:
(((x) > (high)) ? (high) : (((x) < (low)) ? (low) : (x)))

Parameters

  x | value
  low | low bound
  high | high bound

Returns
  a value between low and high

## HASH_TABLE_MAX_SIZE

#define HASH_TABLE_MAX_SIZE 13845163

The maximal hash table size

## HASH_TABLE_MIN_SIZE

#define HASH_TABLE_MIN_SIZE 11

The minimal hash table size

Referenced by di_hash_table_new_full().

## HASH_TABLE_RESIZE

#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);
HASH_TABLE_MIN_SIZE
#define HASH_TABLE_MIN_SIZE
Definition hash.c:81
HASH_TABLE_MAX_SIZE
#define HASH_TABLE_MAX_SIZE
Definition hash.c:86

Defines if a resize is necessary

Parameters

  hash_table | a di_hash_table

#define HASH_TABLE_RESIZE(hash_table) \
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);

Referenced by di_hash_table_insert().

## Function Documentation

## di_hash_table_destroy()

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.

{
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);
}
di_free
void di_free(void *mem)
Definition mem.c:60
di_hash_table::mem_chunk
di_mem_chunk * mem_chunk
Definition hash.c:46
di_hash_table::key_destroy_func
di_destroy_notify * key_destroy_func
Definition hash.c:49
di_hash_table::size
size_t size
Definition hash.c:43
di_hash_table::nodes
di_hash_node ** nodes
Definition hash.c:45
di_hash_table::value_destroy_func
di_destroy_notify * value_destroy_func
Definition hash.c:50

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

Referenced by di_packages_free(), and di_release_free().

## di_hash_table_foreach()

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.

{
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);
}
di_hash_node
Node of a hash table.
Definition hash.c:58
di_hash_node::value
void * value
Definition hash.c:60
di_hash_node::key
void * key
Definition hash.c:59
di_hash_node::next
di_hash_node * next
Definition hash.c:61

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

## di_hash_table_insert()

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.

{
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);
}
}
HASH_TABLE_RESIZE
#define HASH_TABLE_RESIZE(hash_table)
Definition hash.c:70
di_hash_table::nnodes
size_t nnodes
Definition hash.c:44

References HASH_TABLE_RESIZE, di_hash_table::key_destroy_func, di_hash_table::nnodes, and di_hash_table::value_destroy_func.

Referenced by di_packages_append_package(), and di_packages_get_package_new().

## di_hash_table_lookup()

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.

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

References di_hash_node::value.

Referenced by di_packages_get_package(), and di_parser_rfc822_read().

## di_hash_table_new()

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.

{
return di_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
}
di_hash_table_new_full
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)
Definition hash.c:113

References di_hash_table_new_full().

## di_hash_table_new_full()

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.

{
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_mem_chunk_new
di_mem_chunk * di_mem_chunk_new(di_ksize_t atom_size, di_ksize_t area_size)
Definition mem_chunk.c:87
di_new
#define di_new(struct_type, n_structs)
Definition mem.h:73
di_hash_table
Hash table.
Definition hash.c:42
di_hash_table::key_equal_func
di_equal_func * key_equal_func
Definition hash.c:48
di_hash_table::hash_func
di_hash_func * hash_func
Definition hash.c:47

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

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

## di_hash_table_size()

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.

{
return hash_table->nnodes;
}

References di_hash_table::nnodes.

## internal_di_hash_node_destroy()

void internal_di_hash_node_destroy | ( | di_hash_node * | hash_node,
|  | di_destroy_notify | key_destroy_func,
|  | di_destroy_notify | value_destroy_func )

static

{
if (key_destroy_func)
key_destroy_func (hash_node->key);
if (value_destroy_func)
value_destroy_func (hash_node->value);
}

## internal_di_hash_node_new()

di_hash_node * internal_di_hash_node_new | ( | di_hash_table * | hash_table,
|  | void * | key,
|  | void * | value )

static

{
di_hash_node *hash_node;
hash_node = di_mem_chunk_alloc (hash_table->mem_chunk);
hash_node->key = key;
hash_node->value = value;
hash_node->next = NULL;
return hash_node;
}
di_mem_chunk_alloc
void * di_mem_chunk_alloc(di_mem_chunk *mem_chunk)
Definition mem_chunk.c:120

## internal_di_hash_nodes_destroy()

void internal_di_hash_nodes_destroy | ( | di_hash_node * | hash_node,
|  | di_destroy_notify | key_destroy_func,
|  | di_destroy_notify | value_destroy_func )

static

{
if (hash_node)
{
di_hash_node *node = hash_node;
while (node->next)
{
if (key_destroy_func)
key_destroy_func (node->key);
if (value_destroy_func)
value_destroy_func (node->value);
node = node->next;
}
if (key_destroy_func)
key_destroy_func (node->key);
if (value_destroy_func)
value_destroy_func (node->value);
}
}

## internal_di_hash_table_lookup_node()

di_hash_node ** internal_di_hash_table_lookup_node | ( | di_hash_table * | hash_table,
|  | const void * | key )

inline static

{
di_hash_node **node;
node = &hash_table->nodes
[hash_table->hash_func (key) % hash_table->size];
/* Hash table lookup needs to be fast.
* We therefore remove the extra conditional of testing
* whether to call the key_equal_func or not from
* the inner loop.
*/
if (hash_table->key_equal_func)
while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
node = &(*node)->next;
else
while (*node && (*node)->key != key)
node = &(*node)->next;
return node;
}

## internal_di_hash_table_resize()

void internal_di_hash_table_resize | ( | di_hash_table * | hash_table | ) |

static

{
di_hash_node **new_nodes;
di_hash_node *node;
di_hash_node *next;
uint32_t hash_val;
size_t new_size;
size_t i;
new_size = internal_di_spaced_primes_closest (hash_table->nnodes);
new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
new_nodes = di_new0 (di_hash_node*, new_size);
for (i = 0; i < hash_table->size; i++)
for (node = hash_table->nodes[i]; node; node = next)
{
next = node->next;
hash_val = (* hash_table->hash_func) (node->key) % new_size;
node->next = new_nodes[hash_val];
new_nodes[hash_val] = node;
}
di_free (hash_table->nodes);
hash_table->nodes = new_nodes;
hash_table->size = new_size;
}
CLAMP
#define CLAMP(x, low, high)
Definition hash.c:96
di_new0
#define di_new0(struct_type, n_structs)
Definition mem.h:79