💾 Archived View for gmi.noulin.net › gitRepositories › wavlTree › file › wavlTree.c.gmi captured on 2023-07-10 at 15:54:29. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
wavlTree.c (15382B)
1
2 #include "wavlTree.h"
3
4 #define w (*tree)
5 #define n (*node)
6 #define p (*P)
7 #define o (*O)
8 #define x (*X)
9
10 /* enable/disable logging */
11 #undef pLog
12 #define pLog(...)
13
14 #define freeP(ptr) do{\
15 logI("free(%p);", ptr);\
16 free(ptr);\
17 }while(0)
18
19
20 static int height(t *tree);
21 static int nodeHeight(nodet *node);
22 static nodet *getEntry(t *tree, keyt key);
23 static valuet put(t *tree, keyt k, valuet v);
24 static void inOrderTraversal(nodet *X);
25 static void balanceAfterInsert(t *tree, nodet *X);
26 static bool needToRotateLeft(nodet *P);
27 static bool needToRotateRight(nodet *P);
28 static void rotateLeft(t *tree, nodet *P);
29 static void rotateRight(t *tree, nodet *P);
30 static valuet removeKV(t *tree, keyt k);
31
32 static void deleteEntry(t *tree, nodet *P);
33 static nodet *predecessor(nodet *X);
34 static void balanceAfterDeleteWAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank);
35 static void balanceAfterDeleteAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank);
36
37 static nodet *nodeNew(keyt k, valuet v, nodet *parent) {
38 nodet *r = malloc(sizeof(nodet));
39 if (!r) return NULL;
40 r->key = k;
41 r->value = v;
42 r->left = NULL;
43 r->right = NULL;
44 r->parent = parent;
45 r->rank = 0;
46 return r;
47 }
48
49 int height(t *tree) {
50 return nodeHeight(w.root) - 1;
51 }
52
53 int nodeHeight(nodet *node) {
54 if (!node) {
55 return 0;
56 }
57 return (1 + maxV(nodeHeight(n.left), nodeHeight(n.right)));
58 }
59
60 /**
61 * return the value associated with key k
62 */
63 static valuet get(t *tree, keyt k) {
64 nodet *X = getEntry(tree, k);
65 return !X ? -1 : x.value;
66 }
67
68 /**
69 * return map entry for the given key
70 */
71 static nodet *getEntry(t *tree, keyt key) {
72 nodet *P = w.root;
73 while (P) {
74 int cmp = CMP(key, p.key);
75 if (cmp < 0)
76 P = p.left;
77 else if (cmp > 0)
78 P = p.right;
79 else {
80 logI("Entry: %p", P);
81 return P;
82 }
83 }
84 return NULL;
85 }
86
87 /**
88 * associate value v with key k
89 *
90 * \return
91 * previous value for key k
92 * -1 when k is not already in the tree
93 */
94 static valuet put(t *tree, keyt k, valuet v) {
95 nodet *O = w.root;
96 if (!O) {
97 // tree is empty, new node is root
98 w.root = nodeNew(k, v, NULL);
99 w.count = 1;
100 w.modCount++;
101 //return NULL;
102 return -1;
103 }
104
105 // Find the proper position for this new node
106 int cmp;
107 nodet *P;
108 do {
109 P = O;
110 cmp = CMP(k, o.key);
111 // Decide which side of the current parent-under-consideration the
112 // new node to be inserted belongs on.
113 if (cmp < 0)
114 O = o.left;
115 else if (cmp > 0)
116 O = o.right;
117 else {
118 // Looks like we collided with an object in the tree which has
119 // the same key as the key in parameters
120 // return previous value
121 valuet r = o.value;
122 o.value = v;
123 return r;
124 }
125 // If we would have run out of valid pointers in the direction we
126 // should be searching, then we are done
127 } while(O);
128
129 nodet *e = nodeNew(k, v, P);
130 logI("New %p", e);
131 if (cmp < 0) {
132 p.left = e;
133 }
134 else {
135 p.right = e;
136 }
137
138 if (!p.rank) {
139 p.rank++;
140 balanceAfterInsert(tree, P);
141 }
142
143 w.count++;
144 w.modCount++;
145
146 //return NULL;
147 return -1;
148 }
149
150 static void inOrderTraversal(nodet *X) {
151 if (!X) return;
152
153 /* printf("value %d, rank %d", x.value, x.rank); */
154 /* if (x.left) { */
155 /* printf(" left key %d", x.left->key); */
156 /* } */
157 /* else */
158 /* printf(" no left"); */
159 /* if (x.right) { */
160 /* printf(" right key %d", x.right->key); */
161 /* } */
162 /* else */
163 /* printf(" no right"); */
164 /* printf("\n"); */
165
166 inOrderTraversal(x.left);
167 printf("value %d, rank %d\n", x.value, x.rank);
168 inOrderTraversal(x.right);
169 }
170
171 /**
172 * - If the path of incremented ranks reaches the root of the tree stop.
173 * - 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.
174 * - If the procedure increases the rank of a node x, so that it becomes equal to the rank of the parent y of x,
175 * but the other child of y has a rank that is smaller by two (so that the rank of y cannot be increased)
176 * then again the rebalancing procedure stops after performing rotations necessary.
177 *
178 * In other words:
179 * After insertion rank difference is 1,2 or 3 -
180 * check these three cases stopping after any rotations, reaching the root or when rank difference was 2 before the insertion.
181 */
182 static void balanceAfterInsert(t *tree, nodet *X) {
183 for(nodet *P = x.parent ; P && (x.rank+1 != p.rank) ; x.rank++) {
184 if (p.left == X) {
185 // new node was added on the left
186 if (needToRotateRight(P)) {
187 if (!x.left || x.rank >= x.left->rank+2) {
188 x.rank--;
189 x.right->rank++;
190 rotateLeft(tree, X);
191 }
192 p.rank--;
193 rotateRight(tree, P);
194 break;
195 }
196 }
197 else {
198 if (needToRotateLeft(P)) {
199 if (!x.right || x.rank >= x.right->rank+2) {
200 x.rank--;
201 x.left->rank++;
202 rotateRight(tree, X);
203 }
204 p.rank--;
205 rotateLeft(tree, P);
206 break;
207 }
208 }
209 X = P;
210 P = x.parent;
211 }
212 }
213
214 static bool needToRotateLeft(nodet *P) {
215 if (!p.left) {
216 // rank of sibling is -1
217 if (p.rank == 1)
218 return true;
219 return false;
220 }
221 else if (p.rank >= p.left->rank + 2)
222 return true;
223 return false;
224 }
225
226 static bool needToRotateRight(nodet *P) {
227 if (!p.right) {
228 // rank of sibling is -1
229 if (p.rank == 1)
230 return true;
231 return false;
232 }
233 else if (p.rank >= p.right->rank + 2)
234 return true;
235 return false;
236 }
237
238 static void rotateLeft(t *tree, nodet *P) {
239 nodet *X = p.right;
240 p.right = x.left;
241 if (x.left)
242 x.left->parent = P;
243 x.parent = p.parent;
244 if (!p.parent)
245 w.root = X;
246 else if (p.parent->left == P)
247 p.parent->left = X;
248 else
249 p.parent->right = X;
250 x.left = P;
251 p.parent = X;
252 w.rotations++;
253 }
254
255 static void rotateRight(t *tree, nodet *P) {
256 nodet *X = p.left;
257 p.left = x.right;
258 if (x.right)
259 x.right->parent = P;
260 x.parent = p.parent;
261 if (!p.parent)
262 w.root = X;
263 else if (p.parent->right == P)
264 p.parent->right = X;
265 else
266 p.parent->left = X;
267 x.right = P;
268 p.parent = X;
269 w.rotations++;
270 }
271
272 /**
273 * remove key and value if key is present in tree
274 *
275 * \return
276 * previous value for key k
277 * -1 when k was not in the tree
278 */
279 valuet removeKV(t *tree, keyt k) {
280 nodet *P = getEntry(tree, k);
281 if (!P)
282 //return NULL;
283 return -1;
284
285 valuet oldValue = p.value;
286 deleteEntry(tree, P);
287 return oldValue;
288 }
289
290 /**
291 * delete node P and then rebalance the tree
292 */
293 static void deleteEntry(t *tree, nodet *P) {
294 w.modCount++;
295 w.count--;
296
297 // If strictly internal, copy successor's element to p and then make p
298 // point to successor.
299 if (p.left && p.right) {
300 nodet *X = predecessor(P);
301 p.key = x.key;
302 p.value = x.value;
303 P = X;
304 } // p has 2 children
305
306 nodet *replacement = (p.left ? p.left : p.right);
307 if (replacement) {
308 // Link replacement to parent
309 replacement->parent = p.parent;
310 nodet *sibling = NULL;
311 if (!p.parent) {
312 w.root = replacement;
313 freeP(P);
314 return;
315 }
316 else if (P == p.parent->left) {
317 p.parent->left = replacement;
318 sibling = p.parent->right;
319 } else {
320 p.parent->right = replacement;
321 sibling = p.parent->left;
322 }
323
324 // Null out links so they are OK to use by fixAfterDeletion.
325 p.left = p.right = p.parent = NULL;
326 freeP(P);
327 if (w.deleteWAVL)
328 balanceAfterDeleteWAVL(tree, replacement->parent, sibling, replacement->rank);
329 else
330 balanceAfterDeleteAVL(tree, replacement->parent, sibling, replacement->rank);
331 }
332 else if (!p.parent) {
333 // return if we are the only node.
334 freeP(P);
335 w.root = NULL;
336 return;
337 }
338 else {
339 // No children. Use self as phantom replacement and unlink.
340 nodet *fixPoint = p.parent;
341 nodet *sibling = NULL;
342
343 if (P == p.parent->left) {
344 p.parent->left = NULL;
345 sibling = fixPoint->right;
346 }
347 else if (P == p.parent->right) {
348 p.parent->right = NULL;
349 sibling = fixPoint->left;
350 }
351 p.parent = NULL;
352 int8_t rk = --p.rank;
353 freeP(P);
354 if (w.deleteWAVL)
355 balanceAfterDeleteWAVL(tree, fixPoint, sibling, rk);
356 else
357 balanceAfterDeleteAVL(tree, fixPoint, sibling, rk);
358 }
359 }
360
361 static int8_t rank(nodet *node) {
362 return !node ? -1 : n.rank;
363 }
364
365 static bool nodeIsTwoTwo(nodet *node) {
366 if (!node || !n.rank)
367 return false;
368 if (n.rank == 1) {
369 if (!n.left && !n.right)
370 return true;
371 else
372 return false;
373 }
374 else
375 return (n.left->rank == n.right->rank && (n.left->rank + 2 == n.rank));
376 }
377
378 static void balanceAfterDeleteWAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank) {
379 nodet *node;
380 int deltaRank = parent->rank - nodeRank;
381 while (deltaRank == 3 || parent->rank == 1 && nodeIsTwoTwo(parent)) {
382 int deltaRankSibling = (!sibling) ? parent->rank + 1 : parent->rank - sibling->rank;
383 if (deltaRankSibling == 2) {
384 parent->rank--; // demote and continue loop
385 } else {
386 int deltaRankSiblingL = sibling->rank - rank(sibling->left);
387 int deltaRankSiblingR = sibling->rank - rank(sibling->right);
388
389 if (deltaRankSiblingL == 2 && deltaRankSiblingR == 2) {
390 // "double demote" in the orig. paper since both parent & sibling demote
391 parent->rank--;
392 sibling->rank--;
393 }
394 else if (parent->right == sibling) {
395 // delete was on the left
396 if (deltaRankSiblingR == 1) {
397 // single rotation
398 sibling->rank++;
399 parent->rank--;
400 if (!sibling->left)
401 parent->rank--; // demote parent again
402 rotateLeft(tree, parent);
403 }
404 else {
405 // double rotation
406 parent->rank -= 2;
407 sibling->rank--;
408 sibling->left->rank += 2;
409 rotateRight(tree, sibling);
410 rotateLeft(tree, parent);
411 }
412 break;
413 }
414 else {
415 // delete was on the right
416 if (deltaRankSiblingL == 1) {
417 // single rotation
418 sibling->rank++;
419 parent->rank--;
420 if (!sibling->right)
421 parent->rank--; // demote parent again
422 rotateRight(tree, parent);
423 }
424 else {
425 // double rotation
426 parent->rank -= 2;
427 sibling->rank--;
428 sibling->right->rank += 2;
429 rotateLeft(tree, sibling);
430 rotateRight(tree, parent);
431 }
432 break;
433 }
434 }
435
436 if (!parent->parent)
437 return;
438 node = parent;
439 parent = parent->parent;
440 sibling = (parent->left == node) ? parent->right : parent->left;
441 deltaRank = parent->rank - n.rank;
442 }
443 }
444
445 static void balanceAfterDeleteAVL(t *tree, nodet *parent, nodet *sibling, int8_t nodeRank) {
446 nodet *node;
447 int balance;
448 if (!sibling)
449 // remove sibling null check inside loop by testing once here
450 balance = -1 - nodeRank;
451 else
452 balance = sibling->rank - nodeRank;
453
454 while (balance != 1) {
455 // balance == 1 means prior to delete parent was balanced, break;
456 if (balance == 0) {
457 // side of delete was taller, decrement and continue
458 parent->rank--;
459 }
460 else if (parent->left == sibling) {
461 parent->rank -= 2;
462 int siblingBalance = rank(sibling->right) - rank(sibling->left);
463 if (siblingBalance == 0) {
464 // parent height unchanged after rotate so break
465 sibling->rank++;
466 parent->rank++;
467 rotateRight(tree, parent);
468 break;
469 }
470 else if (siblingBalance > 0) {
471 sibling->right->rank++;
472 sibling->rank--;
473 rotateLeft(tree, sibling);
474 }
475 rotateRight(tree, parent);
476 parent = parent->parent;
477 }
478 else {
479 // delete on left
480 parent->rank -= 2;
481 int siblingBalance = rank(sibling->right) - rank(sibling->left);
482 if (siblingBalance == 0) {
483 // parent height unchanged after rotate so break
484 sibling->rank++;
485 parent->rank++;
486 rotateLeft(tree, parent);
487 break;
488 }
489 else if (siblingBalance < 0) {
490 sibling->left->rank++;
491 sibling->rank--;
492 rotateRight(tree, sibling);
493 }
494 rotateLeft(tree, parent);
495 parent = parent->parent;
496 }
497
498 if (!parent->parent)
499 return;
500 node = parent;
501 parent = parent->parent;
502 sibling = (parent->left == node) ? parent->right : parent->left;
503 balance = sibling->rank - n.rank;
504 }
505 }
506
507 static void freeNodes(nodet *X) {
508 if (!X) return;
509 freeNodes(x.left);
510 freeNodes(x.right);
511 freeP(X);
512 }
513
514 static void clear(t *tree) {
515 freeNodes(w.root);
516 w.modCount++;
517 w.count = 0;
518 w.root = NULL;
519 w.rotations = 0;
520 w.deleteWAVL = false;
521 }
522
523 static nodet *getFirstEntry(t *tree) {
524 nodet *P = w.root;
525 if (P) {
526 while (p.left)
527 P = p.left;
528 }
529 return P;
530 }
531
532 static nodet *getLastEntry(t *tree) {
533 nodet *P = w.root;
534 if (P) {
535 while (p.right)
536 P = p.right;
537 }
538 return P;
539 }
540
541 // TODO add leftMost, rightMost pointer in tree
542
543 static nodet *successor(nodet *X) {
544 if (!X)
545 return NULL;
546 else if (x.right != NULL) {
547 nodet *P = x.right;
548 while (p.left)
549 P = p.left;
550 return P;
551 }
552 else {
553 nodet *P = x.parent;
554 nodet *ch = X;
555 while (P && ch == p.right) {
556 ch = P;
557 P = p.parent;
558 }
559 return P;
560 }
561 }
562
563 static nodet *predecessor(nodet *X) {
564 if (!X)
565 return NULL;
566 else if (x.left) {
567 nodet *P = x.left;
568 while (p.right)
569 P = p.right;
570 return P;
571 }
572 else {
573 nodet *P = x.parent;
574 nodet *ch = X;
575 while (P && ch == p.left) {
576 ch = P;
577 P = p.parent;
578 }
579 return P;
580 }
581 }
582
583 static void iterStart(t *tree, nodet *first) {
584 w.expectedModCount = w.modCount;
585 w.lastReturned = NULL;
586 w.next = first;
587 }
588
589 static bool hasNext(t *tree) {
590 return w.next != NULL;
591 }
592
593 static nodet *nextEntry(t *tree) {
594 nodet *e = w.next;
595 if (!e) return NULL;
596 if (w.modCount != w.expectedModCount) return NULL;
597 w.next = successor(e);
598 w.lastReturned = e;
599 return e;
600 }
601
602 static nodet *prevEntry(t *tree) {
603 nodet *e = w.next;
604 if (!e) return NULL;
605 if (w.modCount != w.expectedModCount) return NULL;
606 w.next = predecessor(e);
607 w.lastReturned = e;
608 return e;
609 }
610
611 static bool removeCurrent(t *tree) {
612 if (!w.lastReturned) return false;
613 if (w.modCount != w.expectedModCount) return false;
614 /* // deleted entries are replaced by their successors */
615 /* if (w.lastReturned.left && w.lastReturned.right) */
616 /* w.next = w.lastReturned; */
617 deleteEntry(tree, w.lastReturned);
618 w.expectedModCount = w.modCount;
619 w.lastReturned = NULL;
620 return true;
621 }
622
623 /**
624 * initialize tree data
625 */
626 bool init(t *tree) {
627 if (!tree) return false;
628
629 w.count = 0;
630 w.modCount = 0;
631 w.rotations = 0;
632 w.deleteWAVL = false;
633 w.root = NULL;
634
635 w.get = get;
636 w.put = put;
637 w.treeHeight = height;
638 w.remove = removeKV;
639 w.inOrderTraversal = inOrderTraversal;
640 w.clear = clear;
641 w.getFirstEntry = getFirstEntry;
642 w.getLastEntry = getLastEntry;
643 w.iterStart = iterStart;
644 w.hasNext = hasNext;
645 w.nextEntry = nextEntry;
646 w.prevEntry = prevEntry;
647 w.removeCurrent = removeCurrent;
648
649 return true;
650 }
651
652 // vim: set expandtab ts=2 sw=2: