💾 Archived View for gmi.noulin.net › gitRepositories › tree › file › wavl.h.gmi captured on 2023-07-10 at 15:54:09. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
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: