95 : (((x) < (low)) ? (low) : (x)))
96
97static void internal_di_hash_table_resize (
di_hash_table *hash_table);
102
105static unsigned int internal_di_spaced_primes_closest (unsigned int num);
106
108{
110}
111
113{
115 size_t i;
116
126
127 for (i = 0; i < hash_table->
size; i++)
128 hash_table->
nodes[i] = NULL;
129
130 return hash_table;
131}
132
134{
135 size_t i;
136
137 for (i = 0; i < hash_table->
size; i++)
139
140 di_mem_chunk_destroy (hash_table->
mem_chunk);
141
144}
145
147{
149
150 node = &hash_table->
nodes
152
153
154
155
156
157
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
169{
171
172 node = *internal_di_hash_table_lookup_node (hash_table, key);
173
174 return node ? node->
value : NULL;
175}
176
178{
180
181 node = internal_di_hash_table_lookup_node (hash_table, key);
182
183 if (*node)
184 {
187
190
191 (*node)->value = value;
192 }
193 else
194 {
195 *node = internal_di_hash_node_new (hash_table, key, value);
198 }
199}
200
202{
204
206
207 hash_node->
key = key;
208 hash_node->
value = value;
209 hash_node->
next = NULL;
210
211 return hash_node;
212}
213
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
223{
224 if (hash_node)
225 {
227
229 {
230 if (key_destroy_func)
231 key_destroy_func (node->
key);
232 if (value_destroy_func)
233 value_destroy_func (node->
value);
234
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
246{
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{
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);
271
273
274 for (i = 0; i < hash_table->
size; i++)
275 for (node = hash_table->
nodes[i]; node; node = next)
276 {
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
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