hashtable.h (49706B)
1 #pragma once
2
3 /**
4 * \file
5 *
6 * Chained hash table
7 *
8 * NOTE: The macros in this file are for creating hash table functions wrapping the macros.
9 * I don't advise using these directly because of the risk of memory leaks and
10 * wrong computations.
11 * The leaks and wrong computations happen because the parameters to the macros
12 * are evaluated multiple times.
13 * Example:
14 * hashTbAdd(ahashtable, strdup("akey"), value) causes a leak because strdup is
15 * evaluted twice.
16 *
17 * NOTE: This package doesn't provide the hash functions, install the hashfunctions package to
18 * get some hash functions.
19 *
20 * This hash table has 2 single linked lists in each bucket,
21 * the performance is still good with a load factor of 2.
22 *
23 * The maximum number of buckets is 2^32 and and the maximum number (key, value) nodes 2^32 ( > 40 GB RAM)
24 *
25 * The size (bucket count) increases in power of 2.
26 *
27 * The status of the macros is saved (hashtableVar).res and is set to true when the operation is success and
28 * false when the operation is failure.
29 *
30 * Use hashmap when there are more than 50 elements in the dictionary
31 *
32 * Hash table memory usage (for key type char* and value type u32):
33 * Empty hashmap size: 2744 bytes
34 * Size depending on element count (with load factor 2): 184 + 42 * count
35 *
36 * It takes in average 4 times more memory than smallDict
37 * hashmap = 4 * smallDict RAM
38 *
39 * Lookup time:
40 * fnv hash get: 440ns (300 000 000 keys in hash table - kaby lake CPU)
41 *
42 * This hash table has better performance than smallDict with 50 elements
43 *
44 *
45 * The types handled by the hash table (key, value and hash types)
46 * are defined with hashTbT or hashNodeT and hashtableT.
47 *
48 * The hashTb* are short and convenient macros for the hashtable* macros.
49 * With hashTb* macros there is no need to specify the hash, cmp and free functions.
50 *
51 * Before using the hashTb* macros, define HASHFUNC CMPFUNC and FREEFUNC.
52 *
53 * *Node Macros:
54 * The *Node macros handle the nodes in hash table and save time by not running the hash function.
55 * These macros are useful when the hash function is expensive (like siphash).
56 *
57 * The hash table has to be defined with hashNodeT and hashtableT to be able to use the *Node macros.
58 * The *Node macros use the context type defined by hashNodeT, the context type is named:
59 *
60 * context_typeName
61 *
62 * The key and value in the node is accessed with:
63 * node.key
64 * node.value
65 *
66 * HASHFUNC is a function with prototype:
67 * hashType hashFunc(keyType key);
68 *
69 * CMPFUNC compares keys and is a function with prototype:
70 * int compare(keyType k1, keyType k2);
71 * Return 0 when the keys are equal, 1 otherwise
72 *
73 * FREEFUNC frees key and value is a function with prototype:
74 * void freeKV(keyType* key, valueType* value);
75 * NOTE: the free function gets a pointer to the key and value which is useful when iterating on the nodes
76 * (for example, when keyType is int, set key to -1, iterate on the aHashnode dArray and ignore the node
77 * when the key is -1)
78 *
79 * See the 'node macros' section below for details on usage scenarios of the *Node macros.
80 *
81 * Example:
82 * hashTbT(hasht, char*, u32, u32);
83 *
84 * #define HASHFUNC strHashFNV1A
85 * #define CMPFUNC strcmp
86 * #define FREEFUNC freeNode
87 *
88 * void freeNode(char **key, u32* UNUSED value) {
89 * //logI("free key %x\n", key);
90 * free(key);
91 * }
92 *
93 * hasht h;
94 * hashtableInit(h, 128, 2, 1);
95 *
96 * hashTbAdd(h, "a key", 12);
97 *
98 * u32 result = 0;
99 * hashTbGet(h, "a key", result);
100 *
101 * hashTbDel(h, "a key");
102 *
103 * hashTbFree(h);
104 */
105
106
107 #include "libsheepyObject.h"
108
109 /**
110 * function declarations for tailored hash table
111 *
112 * - define hash table types
113 * - declare prototypes
114 *
115 * this macro is placed most of the time in a header file
116 *
117 * the Hash table type is defined as:
118 * 'typeName't
119 *
120 * the node in the hash table is defined as:
121 * 'typeName'Nodet
122 *
123 * the node context is defined as:
124 * context_'typeName'Nodet
125 *
126 * the function names are:
127 * function'suffix'
128 *
129 * the scope parameter is the function scope and can be 'empty' for global functions, 'static' for local functions, ...
130 *
131 * the declared functions are:
132 * init, empty, free, add, addOrFind, find, get, getKey, del, seed, addOrFindNode
133 * setKeyNode, getNode, updateNodeContext, unlink, freeUnlinked, delNode
134 *
135 *
136 * RETURN VALUES:
137 * add, setKeyNode, updateNodeContext: true success, false failure
138 * addOrFind, addOrFindNode: non NULL success, NULL failure.
139 * *isnew is set to true when the returned value pointer is in a new node.
140 * find, getNode, unlink: non NULL success, NULL failure
141 *
142 * the ctx pointer parameters must be allocated before the function calls
143 * the isnew pointer must point to an existing bool variable
144 *
145 *
146 * Example:
147 * hashTbDef(, m3232, M32, u32, u32, u32); // declare hash table type m3232t with u32 keys, u32 values and u32 hash
148 *
149 * m3232Nodet *node;
150 * context_m3232Nodet ctx;
151 * bool isnew;
152 *
153 * m3232t h; // declares a hash table
154 *
155 */
156 #define hashTbDef(scope, typeName, suffix, keyType, valueType, hashType) \
157 hashNodeT(typeName##Nodet, keyType, valueType, hashType);\
158 hashtableT(typeName##t, typeName##Nodet);\
159 scope void init##suffix(typeName##t *map);\
160 scope void empty##suffix(typeName##t *map);\
161 scope void free##suffix(typeName##t *map);\
162 scope bool add##suffix(typeName##t *map, keyType key, valueType value);\
163 scope valueType* addOrFind##suffix(typeName##t *map, keyType key, bool *isnew);\
164 scope valueType* find##suffix(typeName##t *map, keyType key);\
165 scope valueType get##suffix(typeName##t *map, keyType key);\
166 scope keyType getKey##suffix(typeName##t *map, keyType key);\
167 scope void del##suffix(typeName##t *map, keyType key);\
168 scope u8* seed##suffix(typeName##t *map);\
169 scope typeName##Nodet* addOrFindNode##suffix(typeName##t *map, keyType key, bool *isnew, context_##typeName##Nodet *ctx);\
170 scope bool setKeyNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx);\
171 scope typeName##Nodet *getNode##suffix(typeName##t *map, keyType key, context_##typeName##Nodet *ctx);\
172 scope bool updateNodeContext##suffix(typeName##t *map, context_##typeName##Nodet *ctx);\
173 scope typeName##Nodet* unlink##suffix(typeName##t *map, keyType key);\
174 scope void freeUnlinked##suffix(typeName##t *map, typeName##Nodet *node);\
175 scope void delNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx)
176
177 /**
178 * function implementations
179 *
180 * this macros implements the hash table functions:
181 * init, empty, free, add, addOrFind, find, get, getKey, del, seed, addOrFindNode
182 * setKeyNode, getNode, updateNodeContext, unlink, freeUnlinked, delNode
183 *
184 * this macro is placed most of the time in a source file
185 *
186 * the hash function, compare function and free function must be implemented before this macro
187 * HASHFUNC, CMPFUNC and FREEFUNC must be defined before this macro
188 *
189 * Example:
190 * hashTbDef(, m3232, M32, u32, u32, u32); // declare hash table type m3232t with u32 keys, u32 values and u32 hash
191 *
192 * int cmp(u32 k1, u32 k2) {
193 * return k1 == k2 ? 0 : 1;
194 * }
195 *
196 * void freeM(u32* k, u32* v) {
197 * }
198 *
199 * #define HASHFUNC u32Hash // hash function from the hashfunctions spm package
200 * #define CMPFUNC cmp
201 * #define FREEFUNC freeM
202 *
203 * hashTbFunctions(, m3232, M32, u32, u32); // implements global scope m3232t functions: *M32()
204 *
205 * #undef HASHFUNC
206 * #undef CMPFUNC
207 * #undef FREEFUNC
208 *
209 * m3232t h; // declares a hash table
210 *
211 * initM32(&h);
212 * addM32(&h, 1, 1);
213 *
214 */
215 #define hashTbFunctions(scope, typeName, suffix, keyType, valueType)\
216 scope void init##suffix(typeName##t *map) {\
217 hashTbInit(*map, 64, 2, 1);\
218 }\
219 scope void empty##suffix(typeName##t *map) {\
220 hashTbEmpty(*map);\
221 }\
222 scope void free##suffix(typeName##t *map) {\
223 hashTbFree(*map);\
224 }\
225 scope bool add##suffix(typeName##t *map, keyType key, valueType value) {\
226 hashTbAdd(*map, key, value);\
227 return map->res;\
228 }\
229 scope valueType* addOrFind##suffix(typeName##t *map, keyType key, bool *isnew) {\
230 valueType* r = NULL;\
231 hashTbAddOrFind(*map, key, r, *isnew);\
232 return r;\
233 }\
234 scope valueType* find##suffix(typeName##t *map, keyType key) {\
235 valueType *r = NULL;\
236 hashTbFind(*map, key, r);\
237 return r;\
238 }\
239 scope valueType get##suffix(typeName##t *map, keyType key) {\
240 valueType r;\
241 hashTbGet(*map, key, r);\
242 return r;\
243 }\
244 scope keyType getKey##suffix(typeName##t *map, keyType key) {\
245 keyType r;\
246 hashTbGetKey(*map, key, r);\
247 return r;\
248 }\
249 scope void del##suffix(typeName##t *map, keyType key) {\
250 hashTbDel(*map, key);\
251 }\
252 scope u8* seed##suffix(typeName##t *map) {\
253 u8 *r = hashTbSeed(*map);\
254 return r;\
255 }\
256 scope typeName##Nodet* addOrFindNode##suffix(typeName##t *map, keyType key, bool *isnew, context_##typeName##Nodet *ctx) {\
257 typeName##Nodet* r;\
258 hashTbAddOrFindNode(*map, key, r, *ctx, *isnew);\
259 return r;\
260 }\
261 scope bool setKeyNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx) {\
262 hashTbSetKeyNode(*map, *ctx);\
263 return map->res;\
264 }\
265 scope typeName##Nodet *getNode##suffix(typeName##t *map, keyType key, context_##typeName##Nodet *ctx) {\
266 typeName##Nodet *r = NULL;\
267 hashTbGetNode(*map , key, r, *ctx);\
268 return r;\
269 }\
270 scope bool updateNodeContext##suffix(typeName##t *map, context_##typeName##Nodet *ctx) {\
271 hashTbUpdateNodeContext(*map, *ctx);\
272 return map->res;\
273 }\
274 scope typeName##Nodet* unlink##suffix(typeName##t *map, keyType key) {\
275 typeName##Nodet *r = NULL;\
276 hashTbUnlinkNode(*map, key, r);\
277 return r;\
278 }\
279 scope void freeUnlinked##suffix(typeName##t *map, typeName##Nodet *node) {\
280 hashTbFreeUnlinkedNode(*map, node);\
281 }\
282 scope void delNode##suffix(typeName##t *map, context_##typeName##Nodet *ctx) {\
283 hashTbDelNode(*map, *ctx);\
284 }
285
286
287 /** initialize hash table */
288 #define hashTbInit(HT, SIZE, NUMERATOR, DENOMINATOR) hashtableInit(HT, SIZE, NUMERATOR, DENOMINATOR)
289
290 /** remove all key,value pairs in hash table */
291 #define hashTbEmpty(HT) hashtableEmpty(HT, FREEFUNC)
292
293 /** free hash table */
294 #define hashTbFree(HT) hashtableFree(HT, FREEFUNC)
295
296 /** insert new (key,value), fail when the key already exists */
297 #define hashTbAdd(HT, K, V) hashtableAdd(HT, K, V, HASHFUNC, CMPFUNC)
298
299 /** insert/find key, return value address in VPOINTER and ISNEW */
300 #define hashTbAddOrFind(HT, K, VPOINTER, ISNEW) hashtableAddOrFind(HT, K, VPOINTER, ISNEW, HASHFUNC, CMPFUNC)
301
302 /** find key, return value address in VPOINTER */
303 #define hashTbFind(HT, K, VPOINTER) hashtableFind(HT, K, VPOINTER, HASHFUNC, CMPFUNC)
304
305 /** get value */
306 #define hashTbGet(HT, K, R) hashtableGet(HT, K, R, HASHFUNC, CMPFUNC)
307
308 /** get key */
309 #define hashTbGetKey(HT, K, R) hashtableGetKey(HT, K, R, HASHFUNC, CMPFUNC)
310
311 /** remove key, value */
312 #define hashTbDel(HT, K) hashtableDel(HT, K, HASHFUNC, CMPFUNC, FREEFUNC)
313
314 /** get random seed address */
315 #define hashTbSeed(HT) hashtableSeed(HT)
316
317 /** create or reuse an exists node, return NODEPOINTER, NODECONTEXT and ISNEW */
318 #define hashTbAddOrFindNode(HT, K, NODEPOINTER, NODECONTEXT, ISNEW) hashtableAddOrFindNode(HT, K, NODEPOINTER, NODECONTEXT, ISNEW, HASHFUNC, CMPFUNC)
319
320 /** change the key in a node */
321 #define hashTbSetKeyNode(HT, NODECONTEXT) hashtableSetKeyNode(HT, NODECONTEXT, HASHFUNC, CMPFUNC)
322
323 /** get a node, return NODE and NODECONTEXT */
324 #define hashTbGetNode(HT, K, NODE, NODECONTEXT) hashtableGetNode(HT, K, NODE, NODECONTEXT, HASHFUNC, CMPFUNC)
325
326 /** key in node */
327 #define hashTbNodeKey(NODE) (NODE).key
328
329 /** value in node */
330 #define hashTbNodeValue(NODE) (NODE).value
331
332 /** update node context after a rehash, return NODECONTEXT */
333 #define hashTbUpdateNodeContext(HT, NODECONTEXT) hashtableUpdateNodeContext(HT, NODECONTEXT, HASHFUNC, CMPFUNC)
334
335 /** return a node and remove it from the hashtable, return NODE */
336 #define hashTbUnlinkNode(HT, K, NODE) hashtableUnlinkNode(HT, K, NODE, HASHFUNC, CMPFUNC)
337
338 /** free an unlinked node */
339 #define hashTbFreeUnlinkedNode(HT, NODE) hashtableFreeUnlinkedNode(HT, NODE, FREEFUNC)
340
341 /** delete a node */
342 #define hashTbDelNode(HT, NODECONTEXT) hashtableDelNode(HT, NODECONTEXT, FREEFUNC)
343
344 /**
345 * node definition for bucket single linked lists
346 *
347 * keyType, valueType and hashType can any valid type.
348 *
349 * context_typeName is defined and is needed for *Node macros
350 *
351 * In general, hashType is an uint between 32bits and 256bits
352 */
353 #define hashNodeT(typeName, keyType, valueType, hashType)\
354 typedef struct typeName typeName;\
355 struct typeName {\
356 keyType key;\
357 typeName *next;\
358 hashType hash;\
359 u32 index;\
360 valueType value;\
361 };\
362 typedef struct {\
363 typeName *node;\
364 typeName *prev;\
365 u32 mhash;\
366 u8 moreOrLess;\
367 u32 size;\
368 } TOKENPASTE(context_, typeName) /* concatenate strings with preprocessor */
369
370 /**
371 * hash table definition
372 * typeName is the type of hash table defined.
373 *
374 * hashNodeT(nodeType) has to defined before this macro.
375 *
376 * Example:
377 * hashNodeT(hashSipNodet, char*, u32, u64);
378 * hashtableT(hashsipt, hashSipNodet);
379 *
380 * context_hashSipNodet is the node context type.
381 */
382 #define hashtableT(typeName, nodeType)\
383 dArrayT(UNIQVAR(aHashnodet), nodeType);\
384 dArrayT(UNIQVAR(HNFreet), u32);\
385 typedef struct {\
386 nodeType* (*list)[][2]; /* buckets, 2 single linked lists */\
387 nodeType node;\
388 size_t count; /* node count */\
389 u32 size; /* bucket count */\
390 u32 szMask; /* mask for bucket indexing */\
391 UNIQVAR(aHashnodet) aHashnode; /* node dynamic array */\
392 UNIQVAR(HNFreet) HNFree; /* list of free nodes in aHashnode */\
393 u8 hashseed[16]; /* random seed for siphash */\
394 u32 loadfactor_numerator;\
395 u32 loadfactor_denominator;\
396 bool res; /* return value for macros */\
397 bool newNodeInDArray; /* add, addOrFind and addOrFindNode set this flag: true an new node is pushed in aHashnode, false an existing array element is recycled */\
398 } typeName
399
400 /**
401 * hash table and hash node definition
402 * typeName is the type of hash table defined.
403 *
404 * keyType, valueType and hashType can any valid type.
405 *
406 * In general, hashType is an uint between 32bits and 256bits
407 */
408 #define hashTbT(typeName, keyType, valueType, hashType)\
409 hashNodeT(UNIQVAR(hashnodet), keyType, valueType, hashType);\
410 hashtableT(typeName, UNIQVAR(hashnodet))
411
412 /**
413 * fast log2 function for computing the bucket list size and mask
414 */
415 u32 ilog2Hashtable(u32 value);
416
417 /**
418 * initialize the hash table 'name'
419 *
420 * sz is the initial size
421 * numerator and denominator are the load factor
422 *
423 * the random hash seed is generated
424 *
425 * this macro must be called before using the hash table
426 *
427 * \return
428 * (name).res true success, false failed
429 */
430 #define hashtableInit(name, sz, numerator, denominator) do{\
431 (name).size = sz;\
432 if (sz <= 0) { (name).res = false; break;}\
433 (name).loadfactor_numerator = numerator;\
434 (name).loadfactor_denominator = denominator;\
435 dArrayInit(&(name).aHashnode);\
436 dArrayInit(&(name).HNFree);\
437 setSoftwareRandom();\
438 range(UNIQVAR(i),16) {\
439 (name).hashseed[UNIQVAR(i)] = randomChoice(256);\
440 }\
441 (name).size = (1<<ilog2Hashtable(sz));\
442 (name).szMask = (name).size - 1;\
443 (name).list = malloc((name).size * 2 * sizeof(typeof((name).node)*));\
444 if (!(name).list) /* alloc failed */ { (name).size = 0; (name).res = false; break;}\
445 memset((name).list, 0, (name).size * 2 * sizeof(typeof((name).node)*));\
446 (name).count = 0;\
447 (name).res = true;\
448 } while(0)
449
450 /** Internal - for testing the hash table
451 * show the content of the buckets
452 */
453 #define hashtableTest(name) do{\
454 range(UNIQVAR(i), (name).size) {\
455 /* free first linked list */\
456 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][0];\
457 while (UNIQVAR(node)) {\
458 logI("bucket %3d list 0 key %s", UNIQVAR(i), UNIQVAR(node)->key);\
459 typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
460 UNIQVAR(node) = UNIQVAR(next);\
461 }\
462 /* free second linked list */\
463 UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][1];\
464 while (UNIQVAR(node)) {\
465 logI("bucket %3d list 1 key %s", UNIQVAR(i), UNIQVAR(node)->key);\
466 typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
467 UNIQVAR(node) = UNIQVAR(next);\
468 }\
469 }\
470 } while(0);
471
472 /**
473 * remove all key,value pairs in hash table
474 */
475 #define hashtableEmpty(name, freeNodeFunc) do{\
476 range(UNIQVAR(i), (name).size) {\
477 /* free first linked list */\
478 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][0];\
479 while (UNIQVAR(node)) {\
480 typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
481 freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
482 UNIQVAR(node) = UNIQVAR(next);\
483 }\
484 /* free second linked list */\
485 UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][1];\
486 while (UNIQVAR(node)) {\
487 typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
488 freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
489 UNIQVAR(node) = UNIQVAR(next);\
490 }\
491 (*(name).list)[UNIQVAR(i)][0] = NULL;\
492 (*(name).list)[UNIQVAR(i)][1] = NULL;\
493 }\
494 (name).count = 0;\
495 } while(0);
496
497 /**
498 * empty hash table and free all buffers
499 *
500 * \return
501 * (name).res true success, false failed
502 */
503 #define hashtableFree(name, freeNodeFunc) do{\
504 (name).res = false;\
505 if (!(name).size) /* size=0 invalid */ break;\
506 hashtableEmpty(name, freeNodeFunc);\
507 free((name).list);\
508 dArrayFree(&(name).aHashnode);\
509 dArrayFree(&(name).HNFree);\
510 (name).list = NULL;\
511 (name).count = 0;\
512 (name).size = 0;\
513 (name).res = true;\
514 } while(0)
515
516 /**
517 * resize the hash table
518 *
519 * \return
520 * (name).res true success, false failed
521 */
522 #define hashtableResize(name, sz) do{\
523 u32 UNIQVAR(new_size) = (1<<ilog2Hashtable(sz));\
524 (name).szMask = (name).size - 1;\
525 if ((name).size == UNIQVAR(new_size)) goto UNIQVAR(msuccess);\
526 typeof((name).node) *(*UNIQVAR(list))[][2] = malloc(UNIQVAR(new_size) * 2 * sizeof(typeof((name).node)*));\
527 if (!UNIQVAR(list)) {(name).res = false; break;}\
528 memset(UNIQVAR(list), 0, UNIQVAR(new_size) * 2 * sizeof(typeof((name).node)*));\
529 range(UNIQVAR(i), (name).size) {\
530 range(UNIQVAR(moreLessIdx), 2) {\
531 for (typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(i)][UNIQVAR(moreLessIdx)]; UNIQVAR(node);) {\
532 typeof((name).node) *UNIQVAR(next) = UNIQVAR(node)->next;\
533 u32 UNIQVAR(mhash) = UNIQVAR(node)->hash & (name).szMask;\
534 typeof((name).node) *UNIQVAR(search) = (*UNIQVAR(list))[UNIQVAR(mhash)][0];\
535 typeof((name).node) *UNIQVAR(prev) = NULL;\
536 u8 UNIQVAR(moreOrLess) = 0;\
537 if (UNIQVAR(search)) {\
538 if (UNIQVAR(node)->hash >= UNIQVAR(search)->hash) {\
539 UNIQVAR(moreOrLess) = 0;\
540 while (UNIQVAR(search) && UNIQVAR(node)->hash >= UNIQVAR(search)->hash) {\
541 UNIQVAR(prev) = UNIQVAR(search);\
542 UNIQVAR(search) = UNIQVAR(search)->next;\
543 }\
544 }\
545 else {\
546 UNIQVAR(moreOrLess) = 1;\
547 UNIQVAR(search) = (*UNIQVAR(list))[UNIQVAR(mhash)][1];\
548 while (UNIQVAR(search) && UNIQVAR(node)->hash <= UNIQVAR(search)->hash) {\
549 UNIQVAR(prev) = UNIQVAR(search);\
550 UNIQVAR(search) = UNIQVAR(search)->next;\
551 }\
552 }\
553 }\
554 UNIQVAR(node)->next = UNIQVAR(search);\
555 if (UNIQVAR(prev)) {\
556 UNIQVAR(prev)->next = UNIQVAR(node);\
557 }\
558 else {\
559 (*UNIQVAR(list))[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = UNIQVAR(node);\
560 }\
561 UNIQVAR(node) = UNIQVAR(next);\
562 }\
563 }\
564 }\
565 free((name).list);\
566 (name).list = UNIQVAR(list);\
567 (name).size = UNIQVAR(new_size);\
568 UNIQVAR(msuccess):\
569 (name).res = true;\
570 } while(0)
571
572 /**
573 * insert key, value
574 *
575 * fails when the key already exists
576 *
577 * \return
578 * (name).res true success, false failed
579 */
580 #define hashtableAdd(name, k, v, hashFunc, cmpFunc) do{\
581 if ((name).loadfactor_denominator * (name).count >= (name).loadfactor_numerator * (name).size) {\
582 /* load factor too high */\
583 hashtableResize(name, (name).count*2);\
584 /*if (!(name).res) break; else (name).res = false;*/\
585 }\
586 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
587 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
588 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
589 typeof((name).node) *UNIQVAR(prev) = NULL;\
590 typeof((name).node) *UNIQVAR(add);\
591 u8 UNIQVAR(moreOrLess) = 0;\
592 if (UNIQVAR(node)) {\
593 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
594 UNIQVAR(moreOrLess) = 0;\
595 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
596 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
597 (name).newNodeInDArray = false;\
598 (name).res = false; goto UNIQVAR(mreturn);\
599 }\
600 UNIQVAR(prev) = UNIQVAR(node);\
601 UNIQVAR(node) = UNIQVAR(node)->next;\
602 }\
603 }\
604 else {\
605 UNIQVAR(moreOrLess) = 1;\
606 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
607 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
608 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
609 (name).newNodeInDArray = false;\
610 (name).res = false; goto UNIQVAR(mreturn);\
611 }\
612 UNIQVAR(prev) = UNIQVAR(node);\
613 UNIQVAR(node) = UNIQVAR(node)->next;\
614 }\
615 }\
616 }\
617 if (dArrayIsEmpty(&(name).HNFree)) {\
618 dArrayPush(&(name).aHashnode);\
619 UNIQVAR(add) = dArrayLastPtr(&(name).aHashnode);\
620 UNIQVAR(add)->index = dArrayLastIndex(&(name).aHashnode);\
621 (name).newNodeInDArray = true;\
622 }\
623 else {\
624 u32 UNIQVAR(idx) = dArrayLast(&(name).HNFree);\
625 dArrayDelLast(&(name).HNFree);\
626 UNIQVAR(add) = dArrayPtr(&(name).aHashnode, UNIQVAR(idx));\
627 (name).newNodeInDArray = false;\
628 }\
629 UNIQVAR(add)->key = k;\
630 UNIQVAR(add)->value = v;\
631 UNIQVAR(add)->hash = UNIQVAR(hash);\
632 if (UNIQVAR(prev)) UNIQVAR(prev)->next = UNIQVAR(add);\
633 else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = UNIQVAR(add);\
634 UNIQVAR(add)->next = UNIQVAR(node);\
635 (name).count++;\
636 (name).res = true;\
637 UNIQVAR(mreturn):;\
638 } while(0)
639
640 /**
641 * add or find key, get value pointer
642 *
643 * vPointer must be of type:
644 * valueType *
645 *
646 * isNew must be of type:
647 * bool
648 *
649 * \return
650 * vPointer address to value associated the key k
651 * isNew true when the node is new, false when the node already existed
652 * (name).res true success, false failed
653 */
654 #define hashtableAddOrFind(name, k, vPointer, isNew, hashFunc, cmpFunc) do{\
655 if ((name).loadfactor_denominator * (name).count >= (name).loadfactor_numerator * (name).size) {\
656 /* load factor too high */\
657 hashtableResize(name, (name).count*2);\
658 /*if (!(name).res) break; else (name).res = false;*/\
659 }\
660 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
661 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
662 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
663 typeof((name).node) *UNIQVAR(prev) = NULL;\
664 typeof((name).node) *UNIQVAR(add);\
665 u8 UNIQVAR(moreOrLess) = 0;\
666 if (UNIQVAR(node)) {\
667 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
668 UNIQVAR(moreOrLess) = 0;\
669 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
670 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
671 vPointer = &(UNIQVAR(node)->value);\
672 isNew = false;\
673 (name).newNodeInDArray = false;\
674 (name).res = true; goto UNIQVAR(mreturn);\
675 }\
676 UNIQVAR(prev) = UNIQVAR(node);\
677 UNIQVAR(node) = UNIQVAR(node)->next;\
678 }\
679 }\
680 else {\
681 UNIQVAR(moreOrLess) = 1;\
682 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
683 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
684 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
685 vPointer = &(UNIQVAR(node)->value);\
686 isNew = false;\
687 (name).newNodeInDArray = false;\
688 (name).res = true; goto UNIQVAR(mreturn);\
689 }\
690 UNIQVAR(prev) = UNIQVAR(node);\
691 UNIQVAR(node) = UNIQVAR(node)->next;\
692 }\
693 }\
694 }\
695 isNew = true;\
696 if (dArrayIsEmpty(&(name).HNFree)) {\
697 dArrayPush(&(name).aHashnode);\
698 UNIQVAR(add) = dArrayLastPtr(&(name).aHashnode);\
699 UNIQVAR(add)->index = dArrayLastIndex(&(name).aHashnode);\
700 (name).newNodeInDArray = true;\
701 }\
702 else {\
703 u32 UNIQVAR(idx) = dArrayLast(&(name).HNFree);\
704 dArrayDelLast(&(name).HNFree);\
705 UNIQVAR(add) = dArrayPtr(&(name).aHashnode, UNIQVAR(idx));\
706 (name).newNodeInDArray = false;\
707 }\
708 UNIQVAR(add)->key = k;\
709 vPointer = &(UNIQVAR(add)->value);\
710 UNIQVAR(add)->hash = UNIQVAR(hash);\
711 if (UNIQVAR(prev)) UNIQVAR(prev)->next = UNIQVAR(add);\
712 else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = UNIQVAR(add);\
713 UNIQVAR(add)->next = UNIQVAR(node);\
714 (name).count++;\
715 (name).res = true;\
716 UNIQVAR(mreturn):;\
717 } while(0)
718
719 /**
720 * find key, get value pointer
721 *
722 * vPointer must be of type:
723 * valueType *
724 *
725 * \return
726 * vPointer address to value associated the key k
727 * (name).res true success, false failed
728 */
729 #define hashtableFind(name, k, vPointer, hashFunc, cmpFunc) do{\
730 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
731 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
732 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
733 if (UNIQVAR(node)) {\
734 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
735 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
736 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
737 vPointer = &UNIQVAR(node)->value;\
738 (name).res = true;\
739 goto UNIQVAR(mreturn);\
740 }\
741 UNIQVAR(node) = UNIQVAR(node)->next;\
742 }\
743 }\
744 else {\
745 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
746 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
747 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
748 vPointer = &UNIQVAR(node)->value;\
749 (name).res = true;\
750 goto UNIQVAR(mreturn);\
751 }\
752 UNIQVAR(node) = UNIQVAR(node)->next;\
753 }\
754 }\
755 }\
756 (name).res = false;\
757 UNIQVAR(mreturn):;\
758 } while(0)
759
760 /**
761 * get value
762 *
763 * \return
764 * (name).res true success, false failed
765 */
766 #define hashtableGet(name, k, result, hashFunc, cmpFunc) do{\
767 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
768 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
769 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
770 if (UNIQVAR(node)) {\
771 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
772 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
773 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
774 result = UNIQVAR(node)->value;\
775 (name).res = true;\
776 goto UNIQVAR(mreturn);\
777 }\
778 UNIQVAR(node) = UNIQVAR(node)->next;\
779 }\
780 }\
781 else {\
782 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
783 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
784 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
785 result = UNIQVAR(node)->value;\
786 (name).res = true;\
787 goto UNIQVAR(mreturn);\
788 }\
789 UNIQVAR(node) = UNIQVAR(node)->next;\
790 }\
791 }\
792 }\
793 (name).res = false;\
794 UNIQVAR(mreturn):;\
795 } while(0)
796
797 /**
798 * get key
799 *
800 * \return
801 * (name).res true success, false failed
802 */
803 #define hashtableGetKey(name, k, result, hashFunc, cmpFunc) do{\
804 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
805 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
806 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
807 if (UNIQVAR(node)) {\
808 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
809 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
810 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
811 result = UNIQVAR(node)->key;\
812 (name).res = true;\
813 goto UNIQVAR(mreturn);\
814 }\
815 UNIQVAR(node) = UNIQVAR(node)->next;\
816 }\
817 }\
818 else {\
819 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
820 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
821 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
822 result = UNIQVAR(node)->key;\
823 (name).res = true;\
824 goto UNIQVAR(mreturn);\
825 }\
826 UNIQVAR(node) = UNIQVAR(node)->next;\
827 }\
828 }\
829 }\
830 (name).res = false;\
831 UNIQVAR(mreturn):;\
832 } while(0)
833
834 /**
835 * remove key, value
836 *
837 * \return
838 * (name).res true success, false failed
839 */
840 #define hashtableDel(name, k, hashFunc, cmpFunc, freeNodeFunc) do{\
841 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
842 u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
843 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
844 typeof((name).node) *UNIQVAR(prev) = NULL;\
845 if (UNIQVAR(node)) {\
846 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
847 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
848 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
849 freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
850 hashtableInternalDelNode(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 0);\
851 (name).res = true;\
852 goto UNIQVAR(mreturn);\
853 }\
854 UNIQVAR(prev) = UNIQVAR(node);\
855 UNIQVAR(node) = UNIQVAR(node)->next;\
856 }\
857 }\
858 else {\
859 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
860 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
861 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
862 freeNodeFunc(&UNIQVAR(node)->key, &UNIQVAR(node)->value);\
863 hashtableInternalDelNode(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 1);\
864 (name).res = true;\
865 goto UNIQVAR(mreturn);\
866 }\
867 UNIQVAR(prev) = UNIQVAR(node);\
868 UNIQVAR(node) = UNIQVAR(node)->next;\
869 }\
870 }\
871 }\
872 (name).res = false;\
873 UNIQVAR(mreturn):;\
874 } while(0)
875
876 // Internal macro
877 #define hashtableInternalDelNode(name, node, mhash, prev, moreOrLess) do{\
878 hashtableInternalUnlink(name, node, mhash, prev, moreOrLess);\
879 dArrayAppend(&(name).HNFree, node->index);\
880 (name).count--;\
881 } while(0)
882
883 /**
884 * get hash seed address for siphash
885 */
886 #define hashtableSeed(name) ((name).hashseed)
887
888
889
890 /***************************************
891 * node macros
892 *
893 * Usage scenarios:
894 *
895 * The getNode allow processing node data before reinsert or delete and running the hash function
896 * only once.
897 *
898 * Example:
899 * getNode
900 * use node data, change key
901 * setKeyNode
902 *
903 * same as
904 * get
905 * use node data, change key
906 * del original key
907 * add new key, value
908 *
909 * The unlink macro allow using data in a node before deleting it.
910 * The same operation can be done with Get and Del, using unlink runs the hash function only once.
911 *
912 * Example:
913 * unlinkNode
914 * use node data
915 * freeUnlinkedNode
916 *
917 * same as
918 * get
919 * use value
920 * del
921 *
922 ***************************************/
923
924 /**
925 * add or find node
926 *
927 * nodePointer must be a pointer to hash node type
928 * hashNode *result;
929 *
930 * nodeContext must be a struct of type
931 * context_hashNode ctx;
932 *
933 * \return
934 * (name).res true success, false failed
935 */
936 #define hashtableAddOrFindNode(name, k, nodePointer, nodeContext, isNew, hashFunc, cmpFunc) do{\
937 if ((name).loadfactor_denominator * (name).count >= (name).loadfactor_numerator * (name).size) {\
938 /* load factor too high */\
939 hashtableResize(name, (name).count*2);\
940 /*if (!(name).res) break; else (name).res = false;*/\
941 }\
942 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
943 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
944 (nodeContext).node->hash = UNIQVAR(hash);\
945 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
946 typeof((name).node) *UNIQVAR(prev) = NULL;\
947 u8 UNIQVAR(moreOrLess) = 0;\
948 if (UNIQVAR(node)) {\
949 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
950 UNIQVAR(moreOrLess) = 0;\
951 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
952 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
953 nodePointer = UNIQVAR(node);\
954 (nodeContext).node = nodePointer;\
955 (nodeContext).prev = UNIQVAR(prev);\
956 (nodeContext).mhash = UNIQVAR(mhash);\
957 (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
958 (nodeContext).size = (name).size;\
959 isNew = false;\
960 (name).newNodeInDArray = false;\
961 (name).res = true; goto UNIQVAR(mreturn);\
962 }\
963 UNIQVAR(prev) = UNIQVAR(node);\
964 UNIQVAR(node) = UNIQVAR(node)->next;\
965 }\
966 }\
967 else {\
968 UNIQVAR(moreOrLess) = 1;\
969 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
970 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
971 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
972 nodePointer = UNIQVAR(node);\
973 (nodeContext).node = nodePointer;\
974 (nodeContext).prev = UNIQVAR(prev);\
975 (nodeContext).mhash = UNIQVAR(mhash);\
976 (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
977 (nodeContext).size = (name).size;\
978 isNew = false;\
979 (name).newNodeInDArray = false;\
980 (name).res = true; goto UNIQVAR(mreturn);\
981 }\
982 UNIQVAR(prev) = UNIQVAR(node);\
983 UNIQVAR(node) = UNIQVAR(node)->next;\
984 }\
985 }\
986 }\
987 isNew = true;\
988 if (dArrayIsEmpty(&(name).HNFree)) {\
989 dArrayPush(&(name).aHashnode);\
990 nodePointer = dArrayLastPtr(&(name).aHashnode);\
991 nodePointer->index = dArrayLastIndex(&(name).aHashnode);\
992 (name).newNodeInDArray = true;\
993 }\
994 else {\
995 u32 UNIQVAR(idx) = dArrayLast(&(name).HNFree);\
996 dArrayDelLast(&(name).HNFree);\
997 nodePointer = dArrayPtr(&(name).aHashnode, UNIQVAR(idx));\
998 (name).newNodeInDArray = false;\
999 }\
1000 nodePointer->key = k;\
1001 if (UNIQVAR(prev)) UNIQVAR(prev)->next = nodePointer;\
1002 else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = nodePointer;\
1003 nodePointer->next = UNIQVAR(node);\
1004 (name).count++;\
1005 /* set context */\
1006 (nodeContext).node = nodePointer;\
1007 (nodeContext).prev = UNIQVAR(prev);\
1008 (nodeContext).mhash = UNIQVAR(mhash);\
1009 (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
1010 (nodeContext).size = (name).size;\
1011 (name).res = true;\
1012 UNIQVAR(mreturn):;\
1013 } while(0)
1014
1015 /**
1016 * set node to be used when the key is updated
1017 * unlink the node then
1018 * insert it in another bucket
1019 *
1020 * nodeContext must be a struct of type
1021 * context_hashNode ctx;
1022 *
1023 * The node context is updated and remains valid after this macro (no need to run updateNodeContext)
1024 *
1025 * When key,value pairs are added after getNode and the table is rehashed (the size changed), the node context should be updated with getNode before calling this macro
1026 *
1027 * The node is unlinked, so in case of failure, the node should be added with AddOrFindNode or the node should be freed with freeUnlinkedNode
1028 *
1029 * \return
1030 * (name).res true success, false failed
1031 */
1032 #define hashtableSetKeyNode(name, nodeContext, hashFunc, cmpFunc) do{\
1033 /* no need to resize because the node is unlinked and the key is rehashed */\
1034 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc((nodeContext).node->key);\
1035 if (UNIQVAR(hash) == (nodeContext).node->hash) /* the hash is identical to the previous one, we are done */{\
1036 (name).res = true; goto UNIQVAR(mreturn);\
1037 }\
1038 hashtableInternalUnlinkNode(name, nodeContext);\
1039 if (!(name).res) /* the table has been rehashed, the context is invalid */ goto UNIQVAR(mreturn);\
1040 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
1041 (nodeContext).node->hash = UNIQVAR(hash);\
1042 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][0];\
1043 typeof((name).node) *UNIQVAR(prev) = NULL;\
1044 u8 UNIQVAR(moreOrLess) = 0;\
1045 if (UNIQVAR(node)) {\
1046 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1047 UNIQVAR(moreOrLess) = 0;\
1048 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1049 if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
1050 (name).res = false; goto UNIQVAR(mreturn);\
1051 }\
1052 UNIQVAR(prev) = UNIQVAR(node);\
1053 UNIQVAR(node) = UNIQVAR(node)->next;\
1054 }\
1055 }\
1056 else {\
1057 UNIQVAR(moreOrLess) = 1;\
1058 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
1059 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
1060 if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
1061 (name).res = false; goto UNIQVAR(mreturn);\
1062 }\
1063 UNIQVAR(prev) = UNIQVAR(node);\
1064 UNIQVAR(node) = UNIQVAR(node)->next;\
1065 }\
1066 }\
1067 }\
1068 if (UNIQVAR(prev)) UNIQVAR(prev)->next = (nodeContext).node;\
1069 else (*(name).list)[UNIQVAR(mhash)][UNIQVAR(moreOrLess)] = (nodeContext).node;\
1070 (nodeContext).node->next = UNIQVAR(node);\
1071 /* update context */\
1072 (nodeContext).prev = UNIQVAR(prev);\
1073 (nodeContext).mhash = UNIQVAR(mhash);\
1074 (nodeContext).moreOrLess = UNIQVAR(moreOrLess);\
1075 (nodeContext).size = (name).size;\
1076 (name).res = true;\
1077 UNIQVAR(mreturn):;\
1078 } while(0)
1079
1080 // Internal macro, like Internal DelNode without free the node
1081 // the node is removed from the bucket
1082 #define hashtableInternalUnlinkNode(name, nodeContext) do{\
1083 if ((nodeContext).size != (name).size) {\
1084 /* the table has been rehashed since the nodeContext was filled in */\
1085 /* update the context, run updateNodeContext with the original key */\
1086 /* the original is not available in the context, since the key is probably updated */\
1087 (name).res = false;\
1088 break;\
1089 }\
1090 if ((nodeContext).prev) (nodeContext).prev->next = (nodeContext).node->next;\
1091 else (*(name).list)[(nodeContext).mhash][(nodeContext).moreOrLess] = (nodeContext).node->next;\
1092 if (((nodeContext).moreOrLess == 0) && !(*(name).list)[(nodeContext).mhash][0] && (*(name).list)[(nodeContext).mhash][1]) {\
1093 /* the first linked list is empty, take the first element from the second linked list */\
1094 (*(name).list)[(nodeContext).mhash][0] = (*(name).list)[(nodeContext).mhash][1];\
1095 (*(name).list)[(nodeContext).mhash][1] = (*(name).list)[(nodeContext).mhash][1]->next;\
1096 (*(name).list)[(nodeContext).mhash][0]->next = NULL;\
1097 }\
1098 (name).res = true;\
1099 } while(0)
1100
1101
1102 /**
1103 * get node
1104 *
1105 * result must be a pointer to hash node type
1106 * hashNode *result;
1107 *
1108 * nodeContext must be a struct of type
1109 * context_hashNode ctx;
1110 *
1111 * \return
1112 * (name).res true success, false failed
1113 */
1114 #define hashtableGetNode(name, k, result, nodeContext, hashFunc, cmpFunc) do{\
1115 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
1116 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
1117 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
1118 typeof((name).node) *UNIQVAR(prev) = NULL;\
1119 if (UNIQVAR(node)) {\
1120 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1121 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1122 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
1123 result = UNIQVAR(node);\
1124 (nodeContext).node = UNIQVAR(node);\
1125 (nodeContext).prev = UNIQVAR(prev);\
1126 (nodeContext).mhash = UNIQVAR(mhash);\
1127 (nodeContext).moreOrLess = 0;\
1128 (nodeContext).size = (name).size;\
1129 (name).res = true;\
1130 goto UNIQVAR(mreturn);\
1131 }\
1132 UNIQVAR(prev) = UNIQVAR(node);\
1133 UNIQVAR(node) = UNIQVAR(node)->next;\
1134 }\
1135 }\
1136 else {\
1137 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
1138 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
1139 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
1140 result = UNIQVAR(node);\
1141 (nodeContext).node = UNIQVAR(node);\
1142 (nodeContext).prev = UNIQVAR(prev);\
1143 (nodeContext).mhash = UNIQVAR(mhash);\
1144 (nodeContext).moreOrLess = 1;\
1145 (nodeContext).size = (name).size;\
1146 (name).res = true;\
1147 goto UNIQVAR(mreturn);\
1148 }\
1149 UNIQVAR(prev) = UNIQVAR(node);\
1150 UNIQVAR(node) = UNIQVAR(node)->next;\
1151 }\
1152 }\
1153 }\
1154 (name).res = false;\
1155 UNIQVAR(mreturn):;\
1156 } while(0)
1157
1158 /**
1159 * update node context
1160 *
1161 * the node context must have been initialized with getNode or setKeyNode
1162 *
1163 * call this macro when the table has been rehashed after getNode or setKeyNode
1164 *
1165 * nodeContext must be a struct of type
1166 * context_hashNode ctx;
1167 *
1168 * \return
1169 * (name).res true success, false failed
1170 */
1171 #define hashtableUpdateNodeContext(name, nodeContext, hashFunc, cmpFunc) do{\
1172 const typeof((name).node.hash) UNIQVAR(hash) = (nodeContext).node->hash;\
1173 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
1174 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
1175 typeof((name).node) *UNIQVAR(prev) = NULL;\
1176 if (UNIQVAR(node)) {\
1177 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1178 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1179 if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
1180 (nodeContext).prev = UNIQVAR(prev);\
1181 (nodeContext).mhash = UNIQVAR(mhash);\
1182 (nodeContext).moreOrLess = 0;\
1183 (nodeContext).size = (name).size;\
1184 (name).res = true;\
1185 goto UNIQVAR(mreturn);\
1186 }\
1187 UNIQVAR(prev) = UNIQVAR(node);\
1188 UNIQVAR(node) = UNIQVAR(node)->next;\
1189 }\
1190 }\
1191 else {\
1192 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
1193 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
1194 if (UNIQVAR(hash) == UNIQVAR(node)->hash && (((nodeContext).node->key == UNIQVAR(node)->key) || (cmpFunc((nodeContext).node->key, UNIQVAR(node)->key) == 0))) {\
1195 (nodeContext).prev = UNIQVAR(prev);\
1196 (nodeContext).mhash = UNIQVAR(mhash);\
1197 (nodeContext).moreOrLess = 1;\
1198 (nodeContext).size = (name).size;\
1199 (name).res = true;\
1200 goto UNIQVAR(mreturn);\
1201 }\
1202 UNIQVAR(prev) = UNIQVAR(node);\
1203 UNIQVAR(node) = UNIQVAR(node)->next;\
1204 }\
1205 }\
1206 }\
1207 (name).res = false;\
1208 UNIQVAR(mreturn):;\
1209 } while(0)
1210
1211 /**
1212 * unlink node
1213 *
1214 * result must be a pointer to hash node type
1215 * hashNode *result;
1216 *
1217 * result must be freed with freeUnlinkNode
1218 *
1219 * This macro allow using data in a node before deleting it.
1220 * The same operation can be done with Get and Del, using unlink runs the hash function only once.
1221 *
1222 * Example:
1223 * unlinkNode
1224 * use node data
1225 * freeUnlinkedNode
1226 *
1227 * same as
1228 * get
1229 * use value
1230 * del
1231 *
1232 * \return
1233 * result unlinked node
1234 * (name).res true success, false failed
1235 */
1236 #define hashtableUnlinkNode(name, k, result, hashFunc, cmpFunc) do{\
1237 const typeof((name).node.hash) UNIQVAR(hash) = hashFunc(k);\
1238 const u32 UNIQVAR(mhash) = UNIQVAR(hash) & (name).szMask;\
1239 typeof((name).node) *UNIQVAR(node) = (*(name).list)[UNIQVAR(hash) & (name).szMask][0];\
1240 typeof((name).node) *UNIQVAR(prev) = NULL;\
1241 if (UNIQVAR(node)) {\
1242 if (UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1243 while (UNIQVAR(node) && UNIQVAR(hash) >= UNIQVAR(node)->hash) {\
1244 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
1245 hashtableInternalUnlink(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 0);\
1246 result = UNIQVAR(node);\
1247 (name).res = true;\
1248 goto UNIQVAR(mreturn);\
1249 }\
1250 UNIQVAR(prev) = UNIQVAR(node);\
1251 UNIQVAR(node) = UNIQVAR(node)->next;\
1252 }\
1253 }\
1254 else {\
1255 UNIQVAR(node) = (*(name).list)[UNIQVAR(mhash)][1];\
1256 while (UNIQVAR(node) && UNIQVAR(hash) <= UNIQVAR(node)->hash) {\
1257 if (UNIQVAR(hash) == UNIQVAR(node)->hash && ((k == UNIQVAR(node)->key) || (cmpFunc(k, UNIQVAR(node)->key) == 0))) {\
1258 hashtableInternalUnlink(name, UNIQVAR(node), UNIQVAR(mhash), UNIQVAR(prev), 1);\
1259 result = UNIQVAR(node);\
1260 (name).res = true;\
1261 goto UNIQVAR(mreturn);\
1262 }\
1263 UNIQVAR(prev) = UNIQVAR(node);\
1264 UNIQVAR(node) = UNIQVAR(node)->next;\
1265 }\
1266 }\
1267 }\
1268 (name).res = false;\
1269 UNIQVAR(mreturn):;\
1270 } while(0)
1271
1272 // Internal macro
1273 #define hashtableInternalUnlink(name, node, mhash, prev, moreOrLess) do{\
1274 if (prev) prev->next = node->next;\
1275 else (*(name).list)[mhash][moreOrLess] = node->next;\
1276 if ((moreOrLess == 0) && !(*(name).list)[mhash][0] && (*(name).list)[mhash][1]) {\
1277 /* the first linked list is empty, take the first element from the second linked list */\
1278 (*(name).list)[mhash][0] = (*(name).list)[mhash][1];\
1279 (*(name).list)[mhash][1] = (*(name).list)[mhash][1]->next;\
1280 (*(name).list)[mhash][0]->next = NULL;\
1281 }\
1282 } while(0)
1283
1284 /**
1285 * free an unlinked node
1286 *
1287 * node must be a pointer to hash node type
1288 * hashNode *node;
1289 *
1290 * the node has to be first unlinked with the unlinkNode macro
1291 */
1292 #define hashtableFreeUnlinkedNode(name, node, freeNodeFunc) do{\
1293 freeNodeFunc(&(node)->key, &(node)->value);\
1294 dArrayAppend(&(name).HNFree, (node)->index);\
1295 (name).count--;\
1296 } while(0)
1297
1298 /**
1299 * delete/remove node
1300 *
1301 * the node context must be already initialized with the other *Node macros
1302 *
1303 * if the node context is changed due to rehash, updateNodeContext has to be called before this macro
1304 */
1305 // no status
1306 #define hashtableDelNode(name, nodeContext, freeNodeFunc) do{\
1307 freeNodeFunc(&(nodeContext).node->key, &(nodeContext).node->value);\
1308 hashtableInternalDelNode(name, (nodeContext).node, (nodeContext).mhash, (nodeContext).prev, (nodeContext).moreOrLess);\
1309 } while(0)
1310