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