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