src/system/kernel/util/AVLTreeBase.cpp

   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         fNodeCount--;
 580
 581         // do the balancing
 582         while (result == HEIGHT_CHANGED && parent) {
 583                 node = parent;
 584                 parent = node->parent;
 585                 bool oldIsLeft = isLeft;
 586                 isLeft = (parent && parent->left == node);
 587                 nodeP = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot);
 588                 if (oldIsLeft) {
 589                         // left
 590                         node->balance_factor++;
 591                         result = _BalanceRemoveLeft(nodeP);
 592                 } else {
 593                         // right
 594                         node->balance_factor--;
 595                         result = _BalanceRemoveRight(nodeP);
 596                 }
 597         }
 598
 599         return result;
 600 }
 601
 602
 603 int
 604 AVLTreeBase::_CheckTree(AVLTreeNode* parent, AVLTreeNode* node,
 605         int& _nodeCount) const
 606 {
 607         if (node == NULL) {
 608                 _nodeCount = 0;
 609                 return 0;
 610         }
 611
 612         if (parent != node->parent) {
 613                 CHECK_FAILED("AVLTreeBase::_CheckTree(): node %p parent mismatch: "
 614                         "%p vs %p", node, parent, node->parent);
 615         }
 616
 617         int leftNodeCount;
 618         int leftDepth = _CheckTree(node, node->left, leftNodeCount);
 619
 620         int rightNodeCount;
 621         int rightDepth = _CheckTree(node, node->right, rightNodeCount);
 622
 623         int balance = rightDepth - leftDepth;
 624         if (balance < LEFT || balance > RIGHT) {
 625                 CHECK_FAILED("AVLTreeBase::_CheckTree(): unbalanced subtree: %p", node);
 626         } else if (balance != node->balance_factor) {
 627                 CHECK_FAILED("AVLTreeBase::_CheckTree(): subtree %p balance mismatch: "
 628                         "%d vs %d", node, balance, node->balance_factor);
 629         }
 630
 631         _nodeCount = leftNodeCount + rightNodeCount + 1;
 632         return std::max(leftDepth, rightDepth) + 1;
 633 }