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
95 : (((x) < (low)) ? (low) : (x)))
96
97static void internal_di_hash_table_resize (di_hash_table *hash_table);
98static di_hash_node **internal_di_hash_table_lookup_node (di_hash_table *hash_table, const void *key);
99static di_hash_node *internal_di_hash_node_new (di_hash_table *hash_table, void *key, void *value);
100static 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));
101static void internal_di_hash_nodes_destroy (di_hash_node *hash_node, di_destroy_notify key_destroy_func, di_destroy_notify value_destroy_func);
102
105static unsigned int internal_di_spaced_primes_closest (unsigned int num);
106
108{
109 return di_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
110}
111
112di_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)
113{
114 di_hash_table *hash_table;
115 size_t i;
116
117 hash_table = di_new (di_hash_table, 1);
118 hash_table->size = HASH_TABLE_MIN_SIZE;
119 hash_table->nnodes = 0;
120 hash_table->mem_chunk = di_mem_chunk_new (sizeof (di_hash_node), 4096);
121 hash_table->hash_func = hash_func;
122 hash_table->key_equal_func = key_equal_func;
123 hash_table->key_destroy_func = key_destroy_func;
124 hash_table->value_destroy_func = value_destroy_func;
125 hash_table->nodes = di_new (di_hash_node*, hash_table->size);
126
127 for (i = 0; i < hash_table->size; i++)
128 hash_table->nodes[i] = NULL;
129
130 return hash_table;
131}
132
133void di_hash_table_destroy (di_hash_table *hash_table)
134{
135 size_t i;
136
137 for (i = 0; i < hash_table->size; i++)
138 internal_di_hash_nodes_destroy (hash_table->nodes[i], hash_table->key_destroy_func, hash_table->value_destroy_func);
139
140 di_mem_chunk_destroy (hash_table->mem_chunk);
141
142 di_free (hash_table->nodes);
143 di_free (hash_table);
144}
145
146static inline di_hash_node** internal_di_hash_table_lookup_node (di_hash_table *hash_table, const void *key)
147{
148 di_hash_node **node;
149
150 node = &hash_table->nodes
151 [hash_table->hash_func (key) % hash_table->size];
152
153 /* Hash table lookup needs to be fast.
154 * We therefore remove the extra conditional of testing
155 * whether to call the key_equal_func or not from
156 * the inner loop.
157 */
158 if (hash_table->key_equal_func)
159 while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
160 node = &(*node)->next;
161 else
162 while (*node && (*node)->key != key)
163 node = &(*node)->next;
164
165 return node;
166}
167
168void *di_hash_table_lookup (di_hash_table *hash_table, const void *key)
169{
170 di_hash_node *node;
171
172 node = *internal_di_hash_table_lookup_node (hash_table, key);
173
174 return node ? node->value : NULL;
175}
176
177void di_hash_table_insert (di_hash_table *hash_table, void *key, void *value)
178{
179 di_hash_node **node;
180
181 node = internal_di_hash_table_lookup_node (hash_table, key);
182
183 if (*node)
184 {
185 if (hash_table->key_destroy_func)
186 hash_table->key_destroy_func (key);
187
188 if (hash_table->value_destroy_func)
189 hash_table->value_destroy_func ((*node)->value);
190
191 (*node)->value = value;
192 }
193 else
194 {
195 *node = internal_di_hash_node_new (hash_table, key, value);
196 hash_table->nnodes++;
197 HASH_TABLE_RESIZE (hash_table);
198 }
199}
200
201static di_hash_node* internal_di_hash_node_new (di_hash_table *hash_table, void *key, void *value)
202{
203 di_hash_node *hash_node;
204
205 hash_node = di_mem_chunk_alloc (hash_table->mem_chunk);
206
207 hash_node->key = key;
208 hash_node->value = value;
209 hash_node->next = NULL;
210
211 return hash_node;
212}
213
214static void internal_di_hash_node_destroy (di_hash_node *hash_node, di_destroy_notify key_destroy_func, di_destroy_notify value_destroy_func)
215{
216 if (key_destroy_func)
217 key_destroy_func (hash_node->key);
218 if (value_destroy_func)
219 value_destroy_func (hash_node->value);
220}
221
222static void internal_di_hash_nodes_destroy (di_hash_node *hash_node, di_destroy_notify key_destroy_func, di_destroy_notify value_destroy_func)
223{
224 if (hash_node)
225 {
226 di_hash_node *node = hash_node;
227
228 while (node->next)
229 {
230 if (key_destroy_func)
231 key_destroy_func (node->key);
232 if (value_destroy_func)
233 value_destroy_func (node->value);
234
235 node = node->next;
236 }
237
238 if (key_destroy_func)
239 key_destroy_func (node->key);
240 if (value_destroy_func)
241 value_destroy_func (node->value);
242 }
243}
244
245void di_hash_table_foreach (di_hash_table *hash_table, di_hfunc *func, void *user_data)
246{
247 di_hash_node *node;
248 size_t i;
249
250 for (i = 0; i < hash_table->size; i++)
251 for (node = hash_table->nodes[i]; node; node = node->next)
252 func (node->key, node->value, user_data);
253}
254
256{
257 return hash_table->nnodes;
258}
259
260static void internal_di_hash_table_resize (di_hash_table *hash_table)
261{
262 di_hash_node **new_nodes;
263 di_hash_node *node;
264 di_hash_node *next;
265 uint32_t hash_val;
266 size_t new_size;
267 size_t i;
268
269 new_size = internal_di_spaced_primes_closest (hash_table->nnodes);
270 new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
271
272 new_nodes = di_new0 (di_hash_node*, new_size);
273
274 for (i = 0; i < hash_table->size; i++)
275 for (node = hash_table->nodes[i]; node; node = next)
276 {
277 next = node->next;
278
279 hash_val = (* hash_table->hash_func) (node->key) % new_size;
280
281 node->next = new_nodes[hash_val];
282 new_nodes[hash_val] = node;
283 }
284
285 di_free (hash_table->nodes);
286 hash_table->nodes = new_nodes;
287 hash_table->size = new_size;
288}
289
290static const unsigned int internal_di_primes[] =
291{
292 11,
293 19,
294 37,
295 73,
296 109,
297 163,
298 251,
299 367,
300 557,
301 823,
302 1237,
303 1861,
304 2777,
305 4177,
306 6247,
307 9371,
308 14057,
309 21089,
310 31627,
311 47431,
312 71143,
313 106721,
314 160073,
315 240101,
316 360163,
317 540217,
318 810343,
319 1215497,
320 1823231,
321 2734867,
322 4102283,
323 6153409,
324 9230113,
325 13845163,
326};
327
328static const unsigned int internal_di_nprimes = sizeof (internal_di_primes) / sizeof (internal_di_primes[0]);
329
330static unsigned int internal_di_spaced_primes_closest (unsigned int num)
331{
332 unsigned int i;
333
334 for (i = 0; i < internal_di_nprimes; i++)
335 if (internal_di_primes[i] > num)
336 return internal_di_primes[i];
337
338 return internal_di_primes[internal_di_nprimes - 1];
339}
340
#define CLAMP(x, low, high)
Definition hash.c:96
void * di_hash_table_lookup(di_hash_table *hash_table, const void *key)
Definition hash.c:169
di_ksize_t di_hash_table_size(di_hash_table *hash_table)
Definition hash.c:256
void di_hash_table_destroy(di_hash_table *hash_table)
Definition hash.c:134
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
void di_hash_table_insert(di_hash_table *hash_table, void *key, void *value)
Definition hash.c:178
di_hash_table * di_hash_table_new(di_hash_func hash_func, di_equal_func key_equal_func)
Definition hash.c:108
void di_hash_table_foreach(di_hash_table *hash_table, di_hfunc *func, void *user_data)
Definition hash.c:246
#define HASH_TABLE_RESIZE(hash_table)
Definition hash.c:70
void * di_mem_chunk_alloc(di_mem_chunk *mem_chunk)
Definition mem_chunk.c:120
di_mem_chunk * di_mem_chunk_new(di_ksize_t atom_size, di_ksize_t area_size)
Definition mem_chunk.c:87
void di_free(void *mem)
Definition mem.c:60
#define di_new(struct_type, n_structs)
Definition mem.h:73
#define di_new0(struct_type, n_structs)
Definition mem.h:79
uint32_t di_ksize_t
Definition types.h:78
bool di_equal_func(const void *key1, const void *key2)
Definition types.h:45
uint32_t di_hash_func(const void *key)
Definition types.h:56
void di_destroy_notify(void *data)
Definition types.h:50
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
Hash table.
Definition hash.c:42
size_t nnodes
Definition hash.c:44
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_equal_func * key_equal_func
Definition hash.c:48
di_hash_func * hash_func
Definition hash.c:47
di_hash_node ** nodes
Definition hash.c:45
di_destroy_notify * value_destroy_func
Definition hash.c:50

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}

References di_free(), key_destroy_func, mem_chunk, nodes, size, and 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_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}

References di_hash_node::key, di_hash_node::next, nodes, 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_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}

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_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}

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_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}

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}

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}

◆ 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}