wavl.h (24373B)
1 #pragma once 2 3 #include "libsheepyObject.h" 4 5 /** 6 * \file 7 * 8 * WAVL tree 9 * 10 * WAVL tree is type-safe binary search tree with characteristics from the AVL and red black trees. 11 * 12 * The iterator traverses the tree in sorted order (by key and CMPFUNC). 13 * 14 * The maximum number of nodes is 2^32 15 * 16 * The tree nodes are stored in a dVector, since allocating node in dVector is slightly faster 17 * (in the order of 10% when the memory is not already map in the process) 18 * than the version allocating nodes with malloc. (826ms vs 870ms for 10M elements) 19 * 20 * wavlDef defines 2 types for the tree: 21 * 22 * - 'typeName't is the type for the tree itself 23 * - 'typeName'Nodet is the node type in the tree 24 * 25 * The public functions follow the same pattern as the hashtable API in the hashtable sheepy package. 26 * 27 * init, empty, isEmpty, free, add, addOrFind, find, find, get, getKey, del, addOrFindNode, getNode, delNode behave 28 * like the ones for the hashtable. 29 * 30 * There are a few tree specific functions: 31 * 32 * height, iterStart, hasNext, next, prev, delCurrent 33 * 34 * The key and value in the node are accessed with: 35 * node->key 36 * node->value 37 * 38 * Before implementing the functions with wavlFunctions, define CMPFUNC and FREEFUNC 39 * 40 * - CMPFUNC compares 2 keys, prototype: int cmp(keyType k1, keyType k2); 41 * return -1 when k1 < k2, 0 when k1 = k2 and 1 when k1 > k2 42 * - FREEFUNC frees key and value in a node, prototype: void freeKV(keyType *k, valueType *v); 43 * 44 * Redefine dVectorBits to change the size of the segments in dVector and tweak the memory usage and performance 45 * 46 * Example: 47 * // define WAVL tree: u32 key and u32 value 48 * wavlDef(, w, W, u32, u32); 49 * 50 * // declare tree 51 * wt tree; 52 * 53 * // free KV function 54 * void freeKV(u32* key, u32* value) { 55 * } 56 * 57 * // implement WAVL tree functions 58 * #define FREEFUNC freeKV 59 * #define CMPFUNC CMP 60 * 61 * wavlFunctions(, w, W, u32, u32, -1, -1); 62 * 63 * #undef FREEFUNC 64 * #undef CMPFUNC 65 * 66 * // initialize tree 67 * initW(&tree); 68 * 69 * // add key value pair 70 * addW(&tree, 0, 0); 71 * 72 * // get value for key 73 * var n = getW(&tree, 0); 74 * logVarG(n); 75 * 76 * // iterator from the lowest key to the highest key 77 * iterStartW(&tree, getFirstEntryW(&tree)); 78 * wNodet *node; 79 * while(node = nextW(&tree)) { 80 * logVarG(node->key); 81 * logVarG(node->value); 82 * } 83 * 84 * // delete a key value pair 85 * delW(&tree, 10); 86 * 87 * // free tree 88 * freeW(&tree); 89 * 90 * 91 * 92 * To traverse the tree and print all key value pairs, implement one of these functions: 93 * 94 * void printTree(typeName##Nodet *X) { 95 * if (!X) return; 96 * 97 * printf("value %d, rank %d", X->value, X->rank); 98 * if (X->left) { 99 * printf(" left key %d", X->left->key); 100 * } 101 * else 102 * printf(" no left"); 103 * if (X->right) { 104 * printf(" right key %d", X->right->key); 105 * } 106 * else 107 * printf(" no right"); 108 * printf("\n"); 109 * 110 * inOrderTraversal(X->left); 111 * inOrderTraversal(X->right); 112 * } 113 * 114 * void inOrderTraversal(typeName##Nodet *X) { 115 * if (!X) return; 116 * 117 * inOrderTraversal(X->left); 118 * printf("value %d, rank %d\n", X->value, X->rank); 119 * inOrderTraversal(X->right); 120 * } 121 * 122 * TODO add leftMost, rightMost pointer in tree 123 */ 124 125 /** 126 * function declarations for tailored WAVL tree 127 * 128 * wavlDef defines: 129 * 130 * - 'typeName't is the type for the tree itself 131 * - 'typeName'Nodet is the node type in the tree 132 * - prototypes 133 * 134 * this macro is placed most of the time in a header file 135 * 136 * the function names are: 137 * function'suffix' 138 * 139 * the scope parameter is the function scope and can be 'empty' for global functions, 'static' for local functions, ... 140 * 141 * RETURN VALUES: 142 * height: tree height or -1 when empty 143 * isEmpty, add, hasNext, delCurrent: true success, false failure 144 * addOrFind, addOrFindNode: value or node pointer 145 * *isnew is set to true when the returned value pointer is in a new node 146 * find, getNode, next, prev: value or node pointer 147 * NULL failure 148 * get, getKey: value or key 149 * nullValueV or nullKeyV failure 150 * 151 */ 152 #define wavlDef(scope, typeName, suffix, keyType, valueType)\ 153 wavlNodeT(typeName##Nodet, keyType, valueType);\ 154 wavlTreeT(typeName##t, typeName##Nodet, keyType, valueType);\ 155 scope void init##suffix(typeName##t *tree);\ 156 scope int height##suffix(typeName##t *tree);\ 157 scope void empty##suffix(typeName##t *tree);\ 158 scope bool isEmpty##suffix(typeName##t *tree);\ 159 scope void free##suffix(typeName##t *tree);\ 160 scope bool add##suffix(typeName##t *tree, keyType key, valueType value);\ 161 scope valueType* addOrFind##suffix(typeName##t *tree, keyType key, bool *isnew);\ 162 scope valueType* find##suffix(typeName##t *tree, keyType key);\ 163 scope valueType get##suffix(typeName##t *tree, keyType key);\ 164 scope keyType getKey##suffix(typeName##t *tree, keyType key);\ 165 scope void del##suffix(typeName##t *tree, keyType key);\ 166 scope typeName##Nodet* addOrFindNode##suffix(typeName##t *tree, keyType key, bool *isnew);\ 167 scope typeName##Nodet* getNode##suffix(typeName##t *tree, keyType key);\ 168 scope typeName##Nodet* getFirstEntry##suffix(typeName##t *tree);\ 169 scope typeName##Nodet* getLastEntry##suffix(typeName##t *tree);\ 170 scope void delNode##suffix(typeName##t *tree, typeName##Nodet *node);\ 171 scope void iterStart##suffix(typeName##t *tree, typeName##Nodet *first);\ 172 scope bool hasNext##suffix(typeName##t *tree);\ 173 scope typeName##Nodet* next##suffix(typeName##t *tree);\ 174 scope typeName##Nodet* prev##suffix(typeName##t *tree);\ 175 scope bool delCurrent##suffix(typeName##t *tree) 176 177 /** 178 * function implementations 179 * 180 * this macros implements the tree functions 181 * 182 * this macro is placed most of the time in a source file 183 * 184 * the compare function and free function must be implemented before this macro 185 * CMPFUNC and FREEFUNC must be defined before this macro 186 * 187 */ 188 #define wavlFunctions(scope, typeName, suffix, keyType, valueType, nullKeyV, nullValueV)\ 189 /* initialize tree */\ 190 scope void init##suffix(typeName##t *tree) {\ 191 wavlInit(tree, nullKeyV, nullValueV);\ 192 }\ 193 /* allocate a new node */\ 194 internal typeName##Nodet* newNode##suffix(typeName##t *tree, keyType k, typeName##Nodet *parent) {\ 195 ret wavlNewNode(tree, k, parent);\ 196 }\ 197 internal int nodeHeight##suffix(typeName##Nodet *node) {\ 198 if (!node) {\ 199 ret 0;\ 200 }\ 201 ret (1 + maxV(nodeHeight##suffix(node->left), nodeHeight##suffix(node->right)));\ 202 }\ 203 /* tree height */\ 204 scope int height##suffix(typeName##t *tree) {\ 205 ret nodeHeight##suffix(tree->root) - 1;\ 206 }\ 207 internal void freeNodes##suffix(typeName##t *tree, typeName##Nodet *node) {\ 208 if (!node) ret;\ 209 freeNodes##suffix(tree, node->left);\ 210 freeNodes##suffix(tree, node->right);\ 211 FREEFUNC(&node->key, &node->value);\ 212 dVectorAppend(&tree->freeNodeList, node->index);\ 213 }\ 214 /* free all nodes in tree */\ 215 scope void empty##suffix(typeName##t *tree) {\ 216 freeNodes##suffix(tree, tree->root);\ 217 tree->modCount++;\ 218 tree->count = 0;\ 219 tree->root = NULL;\ 220 tree->rotations = 0;\ 221 }\ 222 /* true when tree is empty */\ 223 scope bool isEmpty##suffix(typeName##t *tree) {\ 224 ret tree->root == NULL;\ 225 }\ 226 /* free all nodes and tree internal buffer, after this the tree is not usable anymore */\ 227 scope void free##suffix(typeName##t *tree) {\ 228 empty##suffix(tree);\ 229 dVectorFree(&tree->treeNodes);\ 230 dVectorFree(&tree->freeNodeList);\ 231 }\ 232 /** insert new (key,value), fail when the key already exists */\ 233 scope bool add##suffix(typeName##t *tree, keyType key, valueType value) {\ 234 bool isnew;\ 235 var node = addOrFindNode##suffix(tree, key, &isnew);\ 236 if (isnew) {\ 237 node->value = value;\ 238 }\ 239 ret isnew;\ 240 }\ 241 /* insert or find key, when the key is not found a new node is created, return value pointer in node otherwise */\ 242 scope valueType* addOrFind##suffix(typeName##t *tree, keyType key, bool *isnew) {\ 243 var node = addOrFindNode##suffix(tree, key, isnew);\ 244 return &node->value;\ 245 }\ 246 /* find key, return value pointer or NULL upon failure */\ 247 scope valueType* find##suffix(typeName##t *tree, keyType key) {\ 248 var node = getNode##suffix(tree, key);\ 249 ret !node ? NULL : &node->value;\ 250 }\ 251 /* get value for key, return value or nullValue upon failure */\ 252 scope valueType get##suffix(typeName##t *tree, keyType key) {\ 253 var node = getNode##suffix(tree, key);\ 254 ret !node ? tree->nullValue : node->value;\ 255 }\ 256 /* get key in node, return key or nullKey upon failure */\ 257 scope keyType getKey##suffix(typeName##t *tree, keyType key) {\ 258 var node = getNode##suffix(tree, key);\ 259 ret !node ? tree->nullKey : node->key;\ 260 }\ 261 /* delete key and value using FREEFUNC */\ 262 scope void del##suffix(typeName##t *tree, keyType key) {\ 263 var node = getNode##suffix(tree, key);\ 264 if (!node) ret;\ 265 delNode##suffix(tree, node);\ 266 }\ 267 internal bool needToRotateLeft##suffix(typeName##Nodet *P) {\ 268 if (!P->left) {\ 269 /* rank of sibling is -1 */\ 270 if (P->rank == 1)\ 271 ret true;\ 272 ret false;\ 273 }\ 274 elif (P->rank >= P->left->rank + 2)\ 275 ret true;\ 276 ret false;\ 277 }\ 278 internal bool needToRotateRight##suffix(typeName##Nodet *P) {\ 279 if (!P->right) {\ 280 /* rank of sibling is -1 */\ 281 if (P->rank == 1)\ 282 ret true;\ 283 ret false;\ 284 }\ 285 elif (P->rank >= P->right->rank + 2)\ 286 ret true;\ 287 ret false;\ 288 }\ 289 internal void rotateLeft##suffix(typeName##t *tree, typeName##Nodet *P) {\ 290 typeName##Nodet *node = P->right;\ 291 P->right = node->left;\ 292 if (node->left)\ 293 node->left->parent = P;\ 294 node->parent = P->parent;\ 295 if (!P->parent)\ 296 tree->root = node;\ 297 elif (P->parent->left == P)\ 298 P->parent->left = node;\ 299 else\ 300 P->parent->right = node;\ 301 node->left = P;\ 302 P->parent = node;\ 303 tree->rotations++;\ 304 }\ 305 internal void rotateRight##suffix(typeName##t *tree, typeName##Nodet *P) {\ 306 typeName##Nodet *node = P->left;\ 307 P->left = node->right;\ 308 if (node->right)\ 309 node->right->parent = P;\ 310 node->parent = P->parent;\ 311 if (!P->parent)\ 312 tree->root = node;\ 313 elif (P->parent->right == P)\ 314 P->parent->right = node;\ 315 else\ 316 P->parent->left = node;\ 317 node->right = P;\ 318 P->parent = node;\ 319 tree->rotations++;\ 320 }\ 321 /** 322 * - If the path of incremented ranks reaches the root of the tree stoP-> 323 * - If the path of incremented ranks reaches a node whose parent's rank previously differed by two and after incrementing now differ by one stoP-> 324 * - If the procedure increases the rank of a node x, so that it becomes equal to the rank of the parent y of x, 325 * but the other child of y has a rank that is smaller by two (so that the rank of y cannot be increased) 326 * then again the rebalancing procedure stops after performing rotations necessary. 327 * 328 * In other words: 329 * After insertion rank difference is 1,2 or 3 - 330 * check these three cases stopping after any rotations, reaching the root or when rank difference was 2 before the insertion. 331 */\ 332 internal void balanceAfterInsert##suffix(typeName##t *tree, typeName##Nodet *node) {\ 333 for(typeName##Nodet *P = node->parent ; P && (node->rank+1 != P->rank) ; node->rank++) {\ 334 if (P->left == node) {\ 335 /* new node was added on the left */\ 336 if (needToRotateRight##suffix(P)) {\ 337 if (!node->left || node->rank >= node->left->rank+2) {\ 338 node->rank--;\ 339 node->right->rank++;\ 340 rotateLeft##suffix(tree, node);\ 341 }\ 342 P->rank--;\ 343 rotateRight##suffix(tree, P);\ 344 break;\ 345 }\ 346 }\ 347 else {\ 348 if (needToRotateLeft##suffix(P)) {\ 349 if (!node->right || node->rank >= node->right->rank+2) {\ 350 node->rank--;\ 351 node->left->rank++;\ 352 rotateRight##suffix(tree, node);\ 353 }\ 354 P->rank--;\ 355 rotateLeft##suffix(tree, P);\ 356 break;\ 357 }\ 358 }\ 359 node = P;\ 360 P = node->parent;\ 361 }\ 362 }\ 363 /* insert or find key, when the key is not found a new node is created, return node pointer */\ 364 scope typeName##Nodet* addOrFindNode##suffix(typeName##t *tree, keyType key, bool *isnew) {\ 365 var O = tree->root;\ 366 if (!O) {\ 367 /* tree is empty, new node is root */\ 368 *isnew = true;\ 369 tree->root = newNode##suffix(tree, key, NULL);\ 370 tree->count = 1;\ 371 tree->modCount++;\ 372 ret tree->root;\ 373 }\ 374 \ 375 /* Find the proper position for this new node */\ 376 int cmp;\ 377 typeName##Nodet *P;\ 378 do {\ 379 P = O;\ 380 cmp = CMPFUNC(key, O->key);\ 381 /* Decide which side of the current parent-under-consideration the 382 * new node to be inserted belongs on. */\ 383 if (cmp < 0)\ 384 O = O->left;\ 385 elif (cmp > 0)\ 386 O = O->right;\ 387 else {\ 388 /* Looks like we collided with an object in the tree which has 389 * the same key as the key in parameters 390 * return previous value */\ 391 *isnew = false;\ 392 ret O;\ 393 }\ 394 /* If we would have run out of valid pointers in the direction we 395 * should be searching, then we are done */\ 396 } while(O);\ 397 \ 398 *isnew = true;\ 399 var e = newNode##suffix(tree, key, P);\ 400 /*logI("New %p", e);*/\ 401 if (cmp < 0) {\ 402 P->left = e;\ 403 }\ 404 else {\ 405 P->right = e;\ 406 }\ 407 \ 408 if (!P->rank) {\ 409 P->rank++;\ 410 balanceAfterInsert##suffix(tree, P);\ 411 }\ 412 \ 413 tree->count++;\ 414 tree->modCount++;\ 415 \ 416 ret e;\ 417 }\ 418 /* get node pointer for key, return node pointer or NULL upon failure */\ 419 scope typeName##Nodet* getNode##suffix(typeName##t *tree, keyType key) {\ 420 var p = tree->root;\ 421 while (p) {\ 422 int cmp = CMPFUNC(key, p->key);\ 423 if (cmp < 0)\ 424 p = p->left;\ 425 elif (cmp > 0)\ 426 p = p->right;\ 427 else {\ 428 /*logI("Entry: %p", P);*/\ 429 ret p;\ 430 }\ 431 }\ 432 ret NULL;\ 433 }\ 434 internal int8_t rank##suffix(typeName##Nodet *node) {\ 435 ret !node ? -1 : node->rank;\ 436 }\ 437 internal bool nodeIsTwoTwo##suffix(typeName##Nodet *node) {\ 438 if (!node || !node->rank)\ 439 ret false;\ 440 if (node->rank == 1) {\ 441 if (!node->left && !node->right)\ 442 ret true;\ 443 else\ 444 ret false;\ 445 }\ 446 else\ 447 ret (node->left->rank == node->right->rank && (node->left->rank + 2 == node->rank));\ 448 }\ 449 internal void balanceAfterDeleteWAVL##suffix(typeName##t *tree, typeName##Nodet *parent, typeName##Nodet *sibling, int8_t nodeRank) {\ 450 typeName##Nodet *node;\ 451 int deltaRank = parent->rank - nodeRank;\ 452 while (deltaRank == 3 || parent->rank == 1 && nodeIsTwoTwo##suffix(parent)) {\ 453 int deltaRankSibling = (!sibling) ? parent->rank + 1 : parent->rank - sibling->rank;\ 454 if (deltaRankSibling == 2) {\ 455 parent->rank--; /* demote and continue loop */\ 456 } \ 457 else {\ 458 int deltaRankSiblingL = sibling->rank - rank##suffix(sibling->left);\ 459 int deltaRankSiblingR = sibling->rank - rank##suffix(sibling->right);\ 460 \ 461 if (deltaRankSiblingL == 2 && deltaRankSiblingR == 2) {\ 462 /* "double demote" in the orig. paper since both parent & sibling demote */\ 463 parent->rank--;\ 464 sibling->rank--;\ 465 }\ 466 elif (parent->right == sibling) {\ 467 /* delete was on the left */\ 468 if (deltaRankSiblingR == 1) {\ 469 /* single rotation */\ 470 sibling->rank++;\ 471 parent->rank--;\ 472 if (!sibling->left)\ 473 parent->rank--; /* demote parent again */\ 474 rotateLeft##suffix(tree, parent);\ 475 }\ 476 else {\ 477 /* double rotation */\ 478 parent->rank -= 2;\ 479 sibling->rank--;\ 480 sibling->left->rank += 2;\ 481 rotateRight##suffix(tree, sibling);\ 482 rotateLeft##suffix(tree, parent);\ 483 }\ 484 break;\ 485 }\ 486 else {\ 487 /* delete was on the right */\ 488 if (deltaRankSiblingL == 1) {\ 489 /* single rotation */\ 490 sibling->rank++;\ 491 parent->rank--;\ 492 if (!sibling->right)\ 493 parent->rank--; /* demote parent again */\ 494 rotateRight##suffix(tree, parent);\ 495 }\ 496 else {\ 497 /* double rotation */\ 498 parent->rank -= 2;\ 499 sibling->rank--;\ 500 sibling->right->rank += 2;\ 501 rotateLeft##suffix(tree, sibling);\ 502 rotateRight##suffix(tree, parent);\ 503 }\ 504 break;\ 505 }\ 506 }\ 507 \ 508 if (!parent->parent)\ 509 ret;\ 510 node = parent;\ 511 parent = parent->parent;\ 512 sibling = (parent->left == node) ? parent->right : parent->left;\ 513 deltaRank = parent->rank - node->rank;\ 514 }\ 515 }\ 516 /* get node pointer for lowest key */\ 517 scope typeName##Nodet *getFirstEntry##suffix(typeName##t *tree) {\ 518 typeName##Nodet *P = tree->root;\ 519 if (P) {\ 520 while (P->left)\ 521 P = P->left;\ 522 }\ 523 ret P;\ 524 }\ 525 /* get node pointer for highest key */\ 526 scope typeName##Nodet *getLastEntry##suffix(typeName##t *tree) {\ 527 typeName##Nodet *P = tree->root;\ 528 if (P) {\ 529 while (P->right)\ 530 P = P->right;\ 531 }\ 532 ret P;\ 533 }\ 534 internal typeName##Nodet *successor##suffix(typeName##Nodet *X) {\ 535 if (!X)\ 536 ret NULL;\ 537 elif (X->right != NULL) {\ 538 typeName##Nodet *P = X->right;\ 539 while (P->left)\ 540 P = P->left;\ 541 ret P;\ 542 }\ 543 else {\ 544 typeName##Nodet *P = X->parent;\ 545 typeName##Nodet *ch = X;\ 546 while (P && ch == P->right) {\ 547 ch = P;\ 548 P = P->parent;\ 549 }\ 550 ret P;\ 551 }\ 552 }\ 553 internal typeName##Nodet *predecessor##suffix(typeName##Nodet *X) {\ 554 if (!X)\ 555 ret NULL;\ 556 elif (X->left) {\ 557 typeName##Nodet *P = X->left;\ 558 while (P->right)\ 559 P = P->right;\ 560 ret P;\ 561 }\ 562 else {\ 563 typeName##Nodet *P = X->parent;\ 564 typeName##Nodet *ch = X;\ 565 while (P && ch == P->left) {\ 566 ch = P;\ 567 P = P->parent;\ 568 }\ 569 ret P;\ 570 }\ 571 }\ 572 /* delete node */\ 573 scope void delNode##suffix(typeName##t *tree, typeName##Nodet *node) {\ 574 tree->modCount++;\ 575 tree->count--;\ 576 \ 577 /* If strictly internal, copy successor's element to p and then make node 578 * point to successor. */\ 579 if (node->left && node->right) {\ 580 typeName##Nodet *X = predecessor##suffix(node);\ 581 node->key = X->key;\ 582 node->value = X->value;\ 583 node = X;\ 584 } /* p has 2 children */\ 585 \ 586 typeName##Nodet *replacement = (node->left ? node->left : node->right);\ 587 if (replacement) {\ 588 /* Link replacement to parent */\ 589 replacement->parent = node->parent;\ 590 typeName##Nodet *sibling = NULL;\ 591 if (!node->parent) {\ 592 tree->root = replacement;\ 593 FREEFUNC(&node->key, &node->value);\ 594 dVectorAppend(&tree->freeNodeList, node->index);\ 595 ret;\ 596 }\ 597 elif (node == node->parent->left) {\ 598 node->parent->left = replacement;\ 599 sibling = node->parent->right;\ 600 }\ 601 else {\ 602 node->parent->right = replacement;\ 603 sibling = node->parent->left;\ 604 }\ 605 \ 606 /* Null out links so they are OK to use by fixAfterDeletion. */\ 607 node->left = node->right = node->parent = NULL;\ 608 FREEFUNC(&node->key, &node->value);\ 609 dVectorAppend(&tree->freeNodeList, node->index);\ 610 balanceAfterDeleteWAVL##suffix(tree, replacement->parent, sibling, replacement->rank);\ 611 }\ 612 elif (!node->parent) {\ 613 /* return if we are the only node. */\ 614 FREEFUNC(&node->key, &node->value);\ 615 dVectorAppend(&tree->freeNodeList, node->index);\ 616 tree->root = NULL;\ 617 ret;\ 618 }\ 619 else {\ 620 /* No children. Use self as phantom replacement and unlink. */\ 621 typeName##Nodet *fixPoint = node->parent;\ 622 typeName##Nodet *sibling = NULL;\ 623 \ 624 if (node == node->parent->left) {\ 625 node->parent->left = NULL;\ 626 sibling = fixPoint->right;\ 627 }\ 628 elif (node == node->parent->right) {\ 629 node->parent->right = NULL;\ 630 sibling = fixPoint->left;\ 631 }\ 632 node->parent = NULL;\ 633 int8_t rk = --node->rank;\ 634 FREEFUNC(&node->key, &node->value);\ 635 dVectorAppend(&tree->freeNodeList, node->index);\ 636 balanceAfterDeleteWAVL##suffix(tree, fixPoint, sibling, rk);\ 637 }\ 638 }\ 639 /* start iteration */\ 640 scope void iterStart##suffix(typeName##t *tree, typeName##Nodet *first) {\ 641 tree->expectedModCount = tree->modCount;\ 642 tree->lastReturned = NULL;\ 643 tree->next = first;\ 644 }\ 645 /* has next node */\ 646 scope bool hasNext##suffix(typeName##t *tree) {\ 647 ret tree->next != NULL;\ 648 }\ 649 /* get next node in iteration */\ 650 scope typeName##Nodet *next##suffix(typeName##t *tree) {\ 651 typeName##Nodet *e = tree->next;\ 652 if (!e) ret NULL;\ 653 if (tree->modCount != tree->expectedModCount) ret NULL;\ 654 tree->next = successor##suffix(e);\ 655 tree->lastReturned = e;\ 656 ret e;\ 657 }\ 658 /* get previous node in iteration */\ 659 scope typeName##Nodet *prev##suffix(typeName##t *tree) {\ 660 typeName##Nodet *e = tree->next;\ 661 if (!e) ret NULL;\ 662 if (tree->modCount != tree->expectedModCount) ret NULL;\ 663 tree->next = predecessor##suffix(e);\ 664 tree->lastReturned = e;\ 665 ret e;\ 666 }\ 667 /* delete current node in iteration, it is possible to continue the iteration after this */\ 668 scope bool delCurrent##suffix(typeName##t *tree) {\ 669 if (!tree->lastReturned) ret false;\ 670 if (tree->modCount != tree->expectedModCount) ret false;\ 671 /* // deleted entries are replaced by their successors */\ 672 /* if (tree->lastReturned.left && tree->lastReturned.right) */\ 673 /* tree->next = tree->lastReturned; */\ 674 delNode##suffix(tree, tree->lastReturned);\ 675 tree->expectedModCount = tree->modCount;\ 676 tree->lastReturned = NULL;\ 677 ret true;\ 678 } 679 680 681 // Internal macros 682 // use the function implementations instead 683 684 #define wavlNodeT(typeName, keyType, valueType)\ 685 typ struct typeName typeName;\ 686 struct typeName {\ 687 keyType key;\ 688 valueType value;\ 689 typeName *left;\ 690 typeName *right;\ 691 typeName *parent;\ 692 i8 rank;\ 693 u32 index; /* node index in treeNodes vector */\ 694 } 695 696 #define wavlTreeT(typeName, nodeType, keyType, valueType)\ 697 dVectorT(UNIQVAR(treeNodest), nodeType);\ 698 dVectorT(UNIQVAR(freeNodest), u32);\ 699 typ struct {\ 700 size_t count; /* number of entries in the tree */\ 701 size_t modCount; /* number of structural modifications to the tree */\ 702 size_t rotations;\ 703 nodeType *root;\ 704 keyType nullKey;\ 705 valueType nullValue;\ 706 /* private iterator */\ 707 size_t expectedModCount;\ 708 nodeType *next;\ 709 nodeType *lastReturned;\ 710 /* end private iterator */\ 711 UNIQVAR(treeNodest) treeNodes;\ 712 UNIQVAR(freeNodest) freeNodeList;\ 713 } typeName 714 715 #define wavlInit(t, nullKeyV, nullValueV) do {\ 716 if (!t) break;\ 717 t->count = 0;\ 718 t->modCount = 0;\ 719 t->rotations = 0;\ 720 t->root = NULL;\ 721 t->nullKey = nullKeyV;\ 722 t->nullValue = nullValueV;\ 723 t->expectedModCount = -1;\ 724 t->next = NULL;\ 725 t->lastReturned = NULL;\ 726 dVectorInit(&t->treeNodes);\ 727 dVectorInit(&t->freeNodeList);\ 728 } while(0) 729 730 #define wavlNewNode(t, k, parent) ({\ 731 typeof(t->root) r = NULL;\ 732 if (dVectorIsEmpty(&t->freeNodeList)) {\ 733 dVectorPush(&t->treeNodes);\ 734 r = dVectorLastPtr(&t->treeNodes);\ 735 r->index = dVectorLastIndex(&t->treeNodes);\ 736 }\ 737 else {\ 738 var UNIQVAR(idx) = dVectorLast(&t->freeNodeList);\ 739 dVectorDelLast(&t->freeNodeList);\ 740 r = dVectorPtr(&t->treeNodes, UNIQVAR(idx));\ 741 r->index = UNIQVAR(idx);\ 742 }\ 743 if (r) {\ 744 r->key = k;\ 745 r->left = NULL;\ 746 r->right = NULL;\ 747 r->parent = parent;\ 748 r->rank = 0;\ 749 }\ 750 r;\ 751 }) 752 753 754 // vim: set expandtab ts=2 sw=2: