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: