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

## CLAMP

#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

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

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

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

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

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

Referenced by di_packages_append_package().

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

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, 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_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 nnodes.