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
~AVLTreeCompare()39 AVLTreeCompare::~AVLTreeCompare()
40 {
41 }
42
43
44 // #pragma mark - AVLTreeBase
45
46
AVLTreeBase(AVLTreeCompare * compare)47 AVLTreeBase::AVLTreeBase(AVLTreeCompare* compare)
48 : fRoot(NULL),
49 fNodeCount(0),
50 fCompare(compare)
51 {
52 }
53
54
~AVLTreeBase()55 AVLTreeBase::~AVLTreeBase()
56 {
57 }
58
59
60 void
MakeEmpty()61 AVLTreeBase::MakeEmpty()
62 {
63 fRoot = NULL;
64 fNodeCount = 0;
65 }
66
67
68 AVLTreeNode*
LeftMost(AVLTreeNode * node) const69 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*
RightMost(AVLTreeNode * node) const81 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*
Previous(AVLTreeNode * node) const93 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*
Next(AVLTreeNode * node) const118 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*
Find(const void * key) const143 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*
FindClosest(const void * key,bool less) const163 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
Insert(AVLTreeNode * nodeToInsert)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*
Remove(const void * key)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
Remove(AVLTreeNode * node)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
CheckTree() const256 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
_RotateRight(AVLTreeNode ** nodeP)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
_RotateLeft(AVLTreeNode ** nodeP)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
_BalanceInsertLeft(AVLTreeNode ** node)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
_BalanceInsertRight(AVLTreeNode ** node)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
_Insert(AVLTreeNode * nodeToInsert)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
_BalanceRemoveLeft(AVLTreeNode ** node)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
_BalanceRemoveRight(AVLTreeNode ** node)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
_RemoveRightMostChild(AVLTreeNode ** node,AVLTreeNode ** foundNode)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
_Remove(AVLTreeNode * node)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
_CheckTree(AVLTreeNode * parent,AVLTreeNode * node,int & _nodeCount) const605 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