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