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