1 /* 2 * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@gmx.de>. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 7 #include <util/AVLTreeBase.h> 8 9 #ifndef FS_SHELL 10 # include <algorithm> 11 # include <KernelExport.h> 12 #endif 13 14 #ifdef _KERNEL_MODE 15 # define CHECK_FAILED(message...) panic(message) 16 #else 17 # ifndef FS_SHELL 18 # include <stdio.h> 19 # include <OS.h> 20 # define CHECK_FAILED(message...) \ 21 do { \ 22 fprintf(stderr, message); \ 23 fprintf(stderr, "\n"); \ 24 debugger("AVLTreeBase check failed"); \ 25 } while (false) 26 # else 27 # define CHECK_FAILED(message...) dprintf(message) 28 # endif 29 #endif 30 31 32 // maximal height of a tree 33 static const int kMaxAVLTreeHeight = 32; 34 35 36 // #pragma mark - AVLTreeCompare 37 38 39 AVLTreeCompare::~AVLTreeCompare() 40 { 41 } 42 43 44 // #pragma mark - AVLTreeBase 45 46 47 AVLTreeBase::AVLTreeBase(AVLTreeCompare* compare) 48 : fRoot(NULL), 49 fNodeCount(0), 50 fCompare(compare) 51 { 52 } 53 54 55 AVLTreeBase::~AVLTreeBase() 56 { 57 } 58 59 60 void 61 AVLTreeBase::MakeEmpty() 62 { 63 fRoot = NULL; 64 fNodeCount = 0; 65 } 66 67 68 AVLTreeNode* 69 AVLTreeBase::LeftMost(AVLTreeNode* node) const 70 { 71 if (node) { 72 while (node->left) 73 node = node->left; 74 } 75 76 return node; 77 } 78 79 80 AVLTreeNode* 81 AVLTreeBase::RightMost(AVLTreeNode* node) const 82 { 83 if (node) { 84 while (node->right) 85 node = node->right; 86 } 87 88 return node; 89 } 90 91 92 AVLTreeNode* 93 AVLTreeBase::Previous(AVLTreeNode* node) const 94 { 95 if (node) { 96 // The previous node cannot be in the right subtree. 97 if (node->left) { 98 // We have a left subtree, so go to the right-most node. 99 node = node->left; 100 while (node->right) 101 node = node->right; 102 } else { 103 // No left subtree: Backtrack our path and stop, where we 104 // took the right branch. 105 AVLTreeNode* previous; 106 do { 107 previous = node; 108 node = node->parent; 109 } while (node && previous == node->left); 110 } 111 } 112 113 return node; 114 } 115 116 117 AVLTreeNode* 118 AVLTreeBase::Next(AVLTreeNode* node) const 119 { 120 if (node) { 121 // The next node cannot be in the left subtree. 122 if (node->right) { 123 // We have a right subtree, so go to the left-most node. 124 node = node->right; 125 while (node->left) 126 node = node->left; 127 } else { 128 // No right subtree: Backtrack our path and stop, where we 129 // took the left branch. 130 AVLTreeNode* previous; 131 do { 132 previous = node; 133 node = node->parent; 134 } while (node && previous == node->right); 135 } 136 } 137 138 return node; 139 } 140 141 142 AVLTreeNode* 143 AVLTreeBase::Find(const void* key) const 144 { 145 AVLTreeNode* node = fRoot; 146 147 while (node) { 148 int cmp = fCompare->CompareKeyNode(key, node); 149 if (cmp == 0) 150 return node; 151 152 if (cmp < 0) 153 node = node->left; 154 else 155 node = node->right; 156 } 157 158 return NULL; 159 } 160 161 162 AVLTreeNode* 163 AVLTreeBase::FindClosest(const void* key, bool less) const 164 { 165 AVLTreeNode* node = fRoot; 166 AVLTreeNode* parent = NULL; 167 168 while (node) { 169 int cmp = fCompare->CompareKeyNode(key, node); 170 if (cmp == 0) 171 break; 172 173 parent = node; 174 if (cmp < 0) 175 node = node->left; 176 else 177 node = node->right; 178 } 179 180 // not found: try to get close 181 if (!node && parent) { 182 node = parent; 183 int expectedCmp = (less ? 1 : -1); 184 int cmp = fCompare->CompareKeyNode(key, node); 185 if (cmp != expectedCmp) { 186 // The node's value is less although we were asked for a greater 187 // value, or the other way around. We need to iterate to the next 188 // node in the respective direction. If there is no node, we fail. 189 if (less) 190 return Previous(node); 191 return Next(node); 192 } 193 } 194 195 return node; 196 } 197 198 199 status_t 200 AVLTreeBase::Insert(AVLTreeNode* nodeToInsert) 201 { 202 int result = _Insert(nodeToInsert); 203 switch (result) { 204 case OK: 205 case HEIGHT_CHANGED: 206 return B_OK; 207 case NO_MEMORY: 208 return B_NO_MEMORY; 209 case DUPLICATE: 210 default: 211 return B_BAD_VALUE; 212 } 213 } 214 215 216 AVLTreeNode* 217 AVLTreeBase::Remove(const void* key) 218 { 219 // find node 220 AVLTreeNode* node = fRoot; 221 while (node) { 222 int cmp = fCompare->CompareKeyNode(key, node); 223 if (cmp == 0) 224 break; 225 else { 226 if (cmp < 0) 227 node = node->left; 228 else 229 node = node->right; 230 } 231 } 232 233 // remove it 234 if (node) 235 _Remove(node); 236 237 return node; 238 } 239 240 241 bool 242 AVLTreeBase::Remove(AVLTreeNode* node) 243 { 244 switch (_Remove(node)) { 245 case OK: 246 case HEIGHT_CHANGED: 247 return true; 248 case NOT_FOUND: 249 default: 250 return false; 251 } 252 } 253 254 255 void 256 AVLTreeBase::CheckTree() const 257 { 258 int nodeCount = 0; 259 _CheckTree(NULL, fRoot, nodeCount); 260 if (nodeCount != fNodeCount) { 261 CHECK_FAILED("AVLTreeBase::CheckTree(): node count mismatch: %d vs %d", 262 nodeCount, fNodeCount); 263 } 264 } 265 266 267 void 268 AVLTreeBase::_RotateRight(AVLTreeNode** nodeP) 269 { 270 // rotate the nodes 271 AVLTreeNode* node = *nodeP; 272 AVLTreeNode* left = node->left; 273 274 *nodeP = left; 275 276 left->parent = node->parent; 277 node->left = left->right; 278 if (left->right) 279 left->right->parent = node; 280 left->right = node; 281 node->parent = left; 282 283 // adjust the balance factors 284 // former pivot 285 if (left->balance_factor >= 0) 286 node->balance_factor++; 287 else 288 node->balance_factor += 1 - left->balance_factor; 289 290 // former left 291 if (node->balance_factor <= 0) 292 left->balance_factor++; 293 else 294 left->balance_factor += node->balance_factor + 1; 295 } 296 297 298 void 299 AVLTreeBase::_RotateLeft(AVLTreeNode** nodeP) 300 { 301 // rotate the nodes 302 AVLTreeNode* node = *nodeP; 303 AVLTreeNode* right = node->right; 304 305 *nodeP = right; 306 307 right->parent = node->parent; 308 node->right = right->left; 309 if (right->left) 310 right->left->parent = node; 311 right->left = node; 312 node->parent = right; 313 314 // adjust the balance factors 315 // former pivot 316 if (right->balance_factor <= 0) 317 node->balance_factor--; 318 else 319 node->balance_factor -= right->balance_factor + 1; 320 321 // former right 322 if (node->balance_factor >= 0) 323 right->balance_factor--; 324 else 325 right->balance_factor += node->balance_factor - 1; 326 } 327 328 329 int 330 AVLTreeBase::_BalanceInsertLeft(AVLTreeNode** node) 331 { 332 if ((*node)->balance_factor < LEFT) { 333 // tree is left heavy 334 AVLTreeNode** left = &(*node)->left; 335 if ((*left)->balance_factor == LEFT) { 336 // left left heavy 337 _RotateRight(node); 338 } else { 339 // left right heavy 340 _RotateLeft(left); 341 _RotateRight(node); 342 } 343 return OK; 344 } 345 346 if ((*node)->balance_factor == BALANCED) 347 return OK; 348 349 return HEIGHT_CHANGED; 350 } 351 352 353 int 354 AVLTreeBase::_BalanceInsertRight(AVLTreeNode** node) 355 { 356 if ((*node)->balance_factor > RIGHT) { 357 // tree is right heavy 358 AVLTreeNode** right = &(*node)->right; 359 if ((*right)->balance_factor == RIGHT) { 360 // right right heavy 361 _RotateLeft(node); 362 } else { 363 // right left heavy 364 _RotateRight(right); 365 _RotateLeft(node); 366 } 367 return OK; 368 } 369 370 if ((*node)->balance_factor == BALANCED) 371 return OK; 372 373 return HEIGHT_CHANGED; 374 } 375 376 377 int 378 AVLTreeBase::_Insert(AVLTreeNode* nodeToInsert) 379 { 380 struct node_info { 381 AVLTreeNode** node; 382 bool left; 383 }; 384 385 node_info stack[kMaxAVLTreeHeight]; 386 node_info* top = stack; 387 const node_info* const bottom = stack; 388 AVLTreeNode** node = &fRoot; 389 390 // find insertion point 391 while (*node) { 392 int cmp = fCompare->CompareNodes(nodeToInsert, *node); 393 if (cmp == 0) // duplicate node 394 return DUPLICATE; 395 else { 396 top->node = node; 397 if (cmp < 0) { 398 top->left = true; 399 node = &(*node)->left; 400 } else { 401 top->left = false; 402 node = &(*node)->right; 403 } 404 top++; 405 } 406 } 407 408 // insert node 409 *node = nodeToInsert; 410 nodeToInsert->left = NULL; 411 nodeToInsert->right = NULL; 412 nodeToInsert->balance_factor = BALANCED; 413 fNodeCount++; 414 415 if (top == bottom) 416 nodeToInsert->parent = NULL; 417 else 418 (*node)->parent = *top[-1].node; 419 420 // do the balancing 421 int result = HEIGHT_CHANGED; 422 while (result == HEIGHT_CHANGED && top != bottom) { 423 top--; 424 node = top->node; 425 if (top->left) { 426 // left 427 (*node)->balance_factor--; 428 result = _BalanceInsertLeft(node); 429 } else { 430 // right 431 (*node)->balance_factor++; 432 result = _BalanceInsertRight(node); 433 } 434 } 435 436 return result; 437 } 438 439 440 int 441 AVLTreeBase::_BalanceRemoveLeft(AVLTreeNode** node) 442 { 443 int result = HEIGHT_CHANGED; 444 445 if ((*node)->balance_factor > RIGHT) { 446 // tree is right heavy 447 AVLTreeNode** right = &(*node)->right; 448 if ((*right)->balance_factor == RIGHT) { 449 // right right heavy 450 _RotateLeft(node); 451 } else if ((*right)->balance_factor == BALANCED) { 452 // right none heavy 453 _RotateLeft(node); 454 result = OK; 455 } else { 456 // right left heavy 457 _RotateRight(right); 458 _RotateLeft(node); 459 } 460 } else if ((*node)->balance_factor == RIGHT) 461 result = OK; 462 463 return result; 464 } 465 466 467 int 468 AVLTreeBase::_BalanceRemoveRight(AVLTreeNode** node) 469 { 470 int result = HEIGHT_CHANGED; 471 472 if ((*node)->balance_factor < LEFT) { 473 // tree is left heavy 474 AVLTreeNode** left = &(*node)->left; 475 if ((*left)->balance_factor == LEFT) { 476 // left left heavy 477 _RotateRight(node); 478 } else if ((*left)->balance_factor == BALANCED) { 479 // left none heavy 480 _RotateRight(node); 481 result = OK; 482 } else { 483 // left right heavy 484 _RotateLeft(left); 485 _RotateRight(node); 486 } 487 } else if ((*node)->balance_factor == LEFT) 488 result = OK; 489 490 return result; 491 } 492 493 494 int 495 AVLTreeBase::_RemoveRightMostChild(AVLTreeNode** node, AVLTreeNode** foundNode) 496 { 497 AVLTreeNode** stack[kMaxAVLTreeHeight]; 498 AVLTreeNode*** top = stack; 499 const AVLTreeNode* const* const* const bottom = stack; 500 501 // find the child 502 while ((*node)->right) { 503 *top = node; 504 top++; 505 node = &(*node)->right; 506 } 507 508 // found the rightmost child: remove it 509 // the found node might have a left child: replace the node with the 510 // child 511 *foundNode = *node; 512 AVLTreeNode* left = (*node)->left; 513 if (left) 514 left->parent = (*node)->parent; 515 *node = left; 516 (*foundNode)->left = NULL; 517 (*foundNode)->parent = NULL; 518 519 // balancing 520 int result = HEIGHT_CHANGED; 521 while (result == HEIGHT_CHANGED && top != bottom) { 522 top--; 523 node = *top; 524 (*node)->balance_factor--; 525 result = _BalanceRemoveRight(node); 526 } 527 528 return result; 529 } 530 531 532 int 533 AVLTreeBase::_Remove(AVLTreeNode* node) 534 { 535 if (!node) 536 return NOT_FOUND; 537 538 // remove node 539 AVLTreeNode* parent = node->parent; 540 bool isLeft = (parent && parent->left == node); 541 AVLTreeNode** nodeP 542 = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot); 543 int result = HEIGHT_CHANGED; 544 AVLTreeNode* replace = NULL; 545 546 if (node->left && node->right) { 547 // node has two children 548 result = _RemoveRightMostChild(&node->left, &replace); 549 replace->parent = parent; 550 replace->left = node->left; 551 replace->right = node->right; 552 if (node->left) // check necessary, if node->left == replace 553 node->left->parent = replace; 554 node->right->parent = replace; 555 replace->balance_factor = node->balance_factor; 556 *nodeP = replace; 557 558 if (result == HEIGHT_CHANGED) { 559 replace->balance_factor++; 560 result = _BalanceRemoveLeft(nodeP); 561 } 562 } else if (node->left) { 563 // node has only left child 564 replace = node->left; 565 replace->parent = parent; 566 replace->balance_factor = node->balance_factor + 1; 567 *nodeP = replace; 568 } else if (node->right) { 569 // node has only right child 570 replace = node->right; 571 replace->parent = node->parent; 572 replace->balance_factor = node->balance_factor - 1; 573 *nodeP = replace; 574 } else { 575 // node has no child 576 *nodeP = NULL; 577 } 578 579 node->parent = node->left = node->right = NULL; 580 fNodeCount--; 581 582 // do the balancing 583 while (result == HEIGHT_CHANGED && parent) { 584 node = parent; 585 parent = node->parent; 586 bool oldIsLeft = isLeft; 587 isLeft = (parent && parent->left == node); 588 nodeP = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot); 589 if (oldIsLeft) { 590 // left 591 node->balance_factor++; 592 result = _BalanceRemoveLeft(nodeP); 593 } else { 594 // right 595 node->balance_factor--; 596 result = _BalanceRemoveRight(nodeP); 597 } 598 } 599 600 return result; 601 } 602 603 604 int 605 AVLTreeBase::_CheckTree(AVLTreeNode* parent, AVLTreeNode* node, 606 int& _nodeCount) const 607 { 608 if (node == NULL) { 609 _nodeCount = 0; 610 return 0; 611 } 612 613 if (parent != node->parent) { 614 CHECK_FAILED("AVLTreeBase::_CheckTree(): node %p parent mismatch: " 615 "%p vs %p", node, parent, node->parent); 616 } 617 618 int leftNodeCount; 619 int leftDepth = _CheckTree(node, node->left, leftNodeCount); 620 621 int rightNodeCount; 622 int rightDepth = _CheckTree(node, node->right, rightNodeCount); 623 624 int balance = rightDepth - leftDepth; 625 if (balance < LEFT || balance > RIGHT) { 626 CHECK_FAILED("AVLTreeBase::_CheckTree(): unbalanced subtree: %p", node); 627 } else if (balance != node->balance_factor) { 628 CHECK_FAILED("AVLTreeBase::_CheckTree(): subtree %p balance mismatch: " 629 "%d vs %d", node, balance, node->balance_factor); 630 } 631 632 _nodeCount = leftNodeCount + rightNodeCount + 1; 633 return max_c(leftDepth, rightDepth) + 1; 634 } 635