libdebian-installer
Data Structures | Macros | Functions
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_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)
 

Detailed Description

Macro Definition Documentation

◆ CLAMP

#define CLAMP (   x,
  low,
  high 
)    (((x) > (high)) ? (high) : (((x) < (low)) ? (low) : (x)))
Parameters
xvalue
lowlow bound
highhigh 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);
#define HASH_TABLE_MIN_SIZE
Definition: hash.c:81
#define HASH_TABLE_MAX_SIZE
Definition: hash.c:86

Defines if a resize is necessary

Parameters
hash_tablea 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_tablea di_hash_table.
135{
136 size_t i;
137
138 for (i = 0; i < hash_table->size; i++)
139 internal_di_hash_nodes_destroy (hash_table->nodes[i], hash_table->key_destroy_func, hash_table->value_destroy_func);
140
141 di_mem_chunk_destroy (hash_table->mem_chunk);
142
143 di_free (hash_table->nodes);
144 di_free (hash_table);
145}
void di_free(void *mem)
Definition: mem.c:60
di_mem_chunk * mem_chunk
Definition: hash.c:46
di_destroy_notify * key_destroy_func
Definition: hash.c:49
size_t size
Definition: hash.c:43
di_hash_node ** nodes
Definition: hash.c:45
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_tablea di_hash_table.
functhe function to call for each key/value pair.
user_datauser data to pass to the function.
247{
248 di_hash_node *node;
249 size_t i;
250
251 for (i = 0; i < hash_table->size; i++)
252 for (node = hash_table->nodes[i]; node; node = node->next)
253 func (node->key, node->value, user_data);
254}
Node of a hash table.
Definition: hash.c:58
void * value
Definition: hash.c:60
void * key
Definition: hash.c:59
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_tablea di_hash_table.
keya key to insert.
valuethe value to associate with the key.
179{
180 di_hash_node **node;
181
182 node = internal_di_hash_table_lookup_node (hash_table, key);
183
184 if (*node)
185 {
186 if (hash_table->key_destroy_func)
187 hash_table->key_destroy_func (key);
188
189 if (hash_table->value_destroy_func)
190 hash_table->value_destroy_func ((*node)->value);
191
192 (*node)->value = value;
193 }
194 else
195 {
196 *node = internal_di_hash_node_new (hash_table, key, value);
197 hash_table->nnodes++;
198 HASH_TABLE_RESIZE (hash_table);
199 }
200}
#define HASH_TABLE_RESIZE(hash_table)
Definition: hash.c:70
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_tablea di_hash_table,
keythe key to look up.
Returns
the associated value, or NULL if the key is not found.
170{
171 di_hash_node *node;
172
173 node = *internal_di_hash_table_lookup_node (hash_table, key);
174
175 return node ? node->value : NULL;
176}

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_funca 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_funca 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.
109{
110 return di_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
111}
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_funca 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_funca function to check two keys for equality. This is used when looking up keys in the di_hash_table.
key_destroy_funca 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_funca 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.
114{
115 di_hash_table *hash_table;
116 size_t i;
117
118 hash_table = di_new (di_hash_table, 1);
119 hash_table->size = HASH_TABLE_MIN_SIZE;
120 hash_table->nnodes = 0;
121 hash_table->mem_chunk = di_mem_chunk_new (sizeof (di_hash_node), 4096);
122 hash_table->hash_func = hash_func;
123 hash_table->key_equal_func = key_equal_func;
124 hash_table->key_destroy_func = key_destroy_func;
125 hash_table->value_destroy_func = value_destroy_func;
126 hash_table->nodes = di_new (di_hash_node*, hash_table->size);
127
128 for (i = 0; i < hash_table->size; i++)
129 hash_table->nodes[i] = NULL;
130
131 return hash_table;
132}
di_mem_chunk * di_mem_chunk_new(di_ksize_t atom_size, di_ksize_t area_size)
Definition: mem_chunk.c:87
#define di_new(struct_type, n_structs)
Definition: mem.h:73
Hash table.
Definition: hash.c:42
di_equal_func * key_equal_func
Definition: hash.c:48
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_tablea di_hash_table.
Returns
the number of key/value pairs.
257{
258 return hash_table->nnodes;
259}

References nnodes.

◆ internal_di_hash_node_destroy()

static void internal_di_hash_node_destroy ( di_hash_node hash_node,
di_destroy_notify  key_destroy_func,
di_destroy_notify  value_destroy_func 
)
static
216{
217 if (key_destroy_func)
218 key_destroy_func (hash_node->key);
219 if (value_destroy_func)
220 value_destroy_func (hash_node->value);
221}

◆ internal_di_hash_node_new()

static di_hash_node * internal_di_hash_node_new ( di_hash_table hash_table,
void *  key,
void *  value 
)
static
203{
204 di_hash_node *hash_node;
205
206 hash_node = di_mem_chunk_alloc (hash_table->mem_chunk);
207
208 hash_node->key = key;
209 hash_node->value = value;
210 hash_node->next = NULL;
211
212 return hash_node;
213}
void * di_mem_chunk_alloc(di_mem_chunk *mem_chunk)
Definition: mem_chunk.c:120

◆ internal_di_hash_nodes_destroy()

static void internal_di_hash_nodes_destroy ( di_hash_node hash_node,
di_destroy_notify  key_destroy_func,
di_destroy_notify  value_destroy_func 
)
static
224{
225 if (hash_node)
226 {
227 di_hash_node *node = hash_node;
228
229 while (node->next)
230 {
231 if (key_destroy_func)
232 key_destroy_func (node->key);
233 if (value_destroy_func)
234 value_destroy_func (node->value);
235
236 node = node->next;
237 }
238
239 if (key_destroy_func)
240 key_destroy_func (node->key);
241 if (value_destroy_func)
242 value_destroy_func (node->value);
243 }
244}

◆ internal_di_hash_table_lookup_node()

static di_hash_node ** internal_di_hash_table_lookup_node ( di_hash_table hash_table,
const void *  key 
)
inlinestatic
148{
149 di_hash_node **node;
150
151 node = &hash_table->nodes
152 [hash_table->hash_func (key) % hash_table->size];
153
154 /* Hash table lookup needs to be fast.
155 * We therefore remove the extra conditional of testing
156 * whether to call the key_equal_func or not from
157 * the inner loop.
158 */
159 if (hash_table->key_equal_func)
160 while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
161 node = &(*node)->next;
162 else
163 while (*node && (*node)->key != key)
164 node = &(*node)->next;
165
166 return node;
167}

◆ internal_di_hash_table_resize()

static void internal_di_hash_table_resize ( di_hash_table hash_table)
static
262{
263 di_hash_node **new_nodes;
264 di_hash_node *node;
265 di_hash_node *next;
266 uint32_t hash_val;
267 size_t new_size;
268 size_t i;
269
270 new_size = internal_di_spaced_primes_closest (hash_table->nnodes);
271 new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
272
273 new_nodes = di_new0 (di_hash_node*, new_size);
274
275 for (i = 0; i < hash_table->size; i++)
276 for (node = hash_table->nodes[i]; node; node = next)
277 {
278 next = node->next;
279
280 hash_val = (* hash_table->hash_func) (node->key) % new_size;
281
282 node->next = new_nodes[hash_val];
283 new_nodes[hash_val] = node;
284 }
285
286 di_free (hash_table->nodes);
287 hash_table->nodes = new_nodes;
288 hash_table->size = new_size;
289}
#define CLAMP(x, low, high)
Definition: hash.c:96
#define di_new0(struct_type, n_structs)
Definition: mem.h:79