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
33static const int kMaxAVLTreeHeight = 32;
34
35
36// #pragma mark - AVLTreeCompare
37
38
39AVLTreeCompare::~AVLTreeCompare()
40{
41}
42
43
44// #pragma mark - AVLTreeBase
45
46
47AVLTreeBase::AVLTreeBase(AVLTreeCompare* compare)
48	: fRoot(NULL),
49	  fNodeCount(0),
50	  fCompare(compare)
51{
52}
53
54
55AVLTreeBase::~AVLTreeBase()
56{
57}
58
59
60void
61AVLTreeBase::MakeEmpty()
62{
63	fRoot = NULL;
64	fNodeCount = 0;
65}
66
67
68AVLTreeNode*
69AVLTreeBase::LeftMost(AVLTreeNode* node) const
70{
71	if (node) {
72		while (node->left)
73			node = node->left;
74	}
75
76	return node;
77}
78
79
80AVLTreeNode*
81AVLTreeBase::RightMost(AVLTreeNode* node) const
82{
83	if (node) {
84		while (node->right)
85			node = node->right;
86	}
87
88	return node;
89}
90
91
92AVLTreeNode*
93AVLTreeBase::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
117AVLTreeNode*
118AVLTreeBase::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
142AVLTreeNode*
143AVLTreeBase::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
162AVLTreeNode*
163AVLTreeBase::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
199status_t
200AVLTreeBase::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
216AVLTreeNode*
217AVLTreeBase::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
241bool
242AVLTreeBase::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
255void
256AVLTreeBase::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
267void
268AVLTreeBase::_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
298void
299AVLTreeBase::_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
329int
330AVLTreeBase::_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
353int
354AVLTreeBase::_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
377int
378AVLTreeBase::_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
440int
441AVLTreeBase::_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
467int
468AVLTreeBase::_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
494int
495AVLTreeBase::_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
532int
533AVLTreeBase::_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
603int
604AVLTreeBase::_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}
634