Changes in kernel/generic/src/adt/avl.c [1b20da0:a35b458] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/avl.c
r1b20da0 ra35b458 66 66 { 67 67 avltree_node_t *p; 68 68 69 69 /* 70 70 * Iteratively descend to the leaf that can contain the searched key. … … 92 92 { 93 93 avltree_node_t *p = t->root; 94 94 95 95 /* 96 96 * Check whether the tree is empty. … … 98 98 if (!p) 99 99 return NULL; 100 100 101 101 /* 102 102 * Iteratively descend to the leftmost leaf in the tree. … … 104 104 while (p->lft != NULL) 105 105 p = p->lft; 106 106 107 107 return p; 108 108 } … … 151 151 #define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1) 152 152 #define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1) 153 153 154 154 /** Insert new node into AVL tree. 155 155 * … … 172 172 */ 173 173 key = newnode->key + t->base; 174 174 175 175 /* 176 176 * Iteratively descend to the leaf that can contain the new node. … … 244 244 } 245 245 } 246 246 247 247 /* 248 248 * To balance the tree, we must check and balance top node. … … 260 260 */ 261 261 assert(par->balance == 1); 262 262 263 263 REBALANCE_INSERT_LR(); 264 264 } … … 275 275 */ 276 276 assert(par->balance == -1); 277 277 278 278 REBALANCE_INSERT_RL(); 279 279 } … … 375 375 assert(t); 376 376 assert(node); 377 377 378 378 if (node->lft == NULL) { 379 379 if (node->rgt) { … … 451 451 cur->par = node->par; 452 452 } 453 453 454 454 /* 455 455 * Repair the parent node's pointer which pointed previously to the … … 457 457 */ 458 458 (void) repair(t, node, node, cur, NULL, false); 459 459 460 460 /* 461 461 * Repair cycle which repairs balances of nodes on the way from from the … … 484 484 * RL rotation. 485 485 */ 486 486 487 487 cur = par->lft; 488 488 par->lft = cur->rgt; … … 490 490 gpa->rgt = cur->lft; 491 491 cur->lft = gpa; 492 492 493 493 /* 494 494 * Repair balances and paternity of … … 497 497 */ 498 498 REBALANCE_DELETE_RL(); 499 499 500 500 /* 501 501 * Repair paternity. … … 513 513 * RR rotation. 514 514 */ 515 515 516 516 gpa->rgt = par->lft; 517 517 if (par->lft) 518 518 par->lft->par = gpa; 519 519 par->lft = gpa; 520 520 521 521 /* 522 522 * Repair paternity. … … 524 524 par->par = gpa->par; 525 525 gpa->par = par; 526 526 527 527 if (par->balance == 0) { 528 528 /* … … 575 575 */ 576 576 par = gpa->lft; 577 577 578 578 if (par->balance == 1) { 579 579 /* 580 580 * LR rotation. 581 581 */ 582 582 583 583 cur = par->rgt; 584 584 par->rgt = cur->lft; … … 586 586 gpa->lft = cur->rgt; 587 587 cur->rgt = gpa; 588 588 589 589 /* 590 590 * Repair balances and paternity of … … 619 619 par->par = gpa->par; 620 620 gpa->par = par; 621 621 622 622 if (par->balance == 0) { 623 623 /* … … 630 630 par->balance = 1; 631 631 gpa->balance = -1; 632 632 633 633 (void) repair(t, par, gpa, par, 634 634 NULL, false); … … 637 637 par->balance = 0; 638 638 gpa->balance = 0; 639 639 640 640 if (!repair(t, par, gpa, par, 641 641 &dir, false)) … … 667 667 { 668 668 avltree_node_t *node; 669 669 670 670 /* 671 671 * Start searching for the smallest key in the tree starting in the root … … 673 673 * must have the smallest key). 674 674 */ 675 675 676 676 node = t->root; 677 677 if (!node) 678 678 return false; 679 679 680 680 while (node->lft != NULL) 681 681 node = node->lft; 682 682 683 683 avltree_delete(t, node); 684 684
Note:
See TracChangeset
for help on using the changeset viewer.