kernel/util/AVLTreeBase.cpp

69 AVLTreeBase::LeftMost(AVLTreeNode* node) const
71 	if (node) {
72 		while (node->left)
73 			node = node->left;
76 	return node;
81 AVLTreeBase::RightMost(AVLTreeNode* node) const
83 	if (node) {
84 		while (node->right)
85 			node = node->right;
88 	return node;
93 AVLTreeBase::Previous(AVLTreeNode* node) const
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;
107 				previous = node;
108 				node = node->parent;
109 			} while (node && previous == node->left);
113 	return node;
118 AVLTreeBase::Next(AVLTreeNode* node) const
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;
132 				previous = node;
133 				node = node->parent;
134 			} while (node && previous == node->right);
138 	return node;
145 	AVLTreeNode* node = fRoot;
147 	while (node) {
148 		int cmp = fCompare->CompareKeyNode(key, node);
150 			return node;
153 			node = node->left;
155 			node = node->right;
165 	AVLTreeNode* node = fRoot;
168 	while (node) {
169 		int cmp = fCompare->CompareKeyNode(key, node);
173 		parent = node;
175 			node = node->left;
177 			node = node->right;
181 	if (!node && parent) {
182 		node = parent;
184 		int cmp = fCompare->CompareKeyNode(key, node);
186 			// The node's value is less although we were asked for a greater
188 			// node in the respective direction. If there is no node, we fail.
190 				return Previous(node);
191 			return Next(node);
195 	return node;
219 	// find node
220 	AVLTreeNode* node = fRoot;
221 	while (node) {
222 		int cmp = fCompare->CompareKeyNode(key, node);
227 				node = node->left;
229 				node = node->right;
234 	if (node)
235 		_Remove(node);
237 	return node;
242 AVLTreeBase::Remove(AVLTreeNode* node)
244 	switch (_Remove(node)) {
261 		CHECK_FAILED("AVLTreeBase::CheckTree(): node count mismatch: %d vs %d",
271 	AVLTreeNode* node = *nodeP;
272 	AVLTreeNode* left = node->left;
276 	left->parent = node->parent;
277 	node->left = left->right;
279 		left->right->parent = node;
280 	left->right = node;
281 	node->parent = left;
286 		node->balance_factor++;
288 		node->balance_factor += 1 - left->balance_factor;
291 	if (node->balance_factor <= 0)
294 		left->balance_factor += node->balance_factor + 1;
302 	AVLTreeNode* node = *nodeP;
303 	AVLTreeNode* right = node->right;
307 	right->parent = node->parent;
308 	node->right = right->left;
310 		right->left->parent = node;
311 	right->left = node;
312 	node->parent = right;
317 		node->balance_factor--;
319 		node->balance_factor -= right->balance_factor + 1;
322 	if (node->balance_factor >= 0)
325 		right->balance_factor += node->balance_factor - 1;
330 AVLTreeBase::_BalanceInsertLeft(AVLTreeNode** node)
332 	if ((*node)->balance_factor < LEFT) {
334 		AVLTreeNode** left = &(*node)->left;
337 			_RotateRight(node);
341 			_RotateRight(node);
346 	if ((*node)->balance_factor == BALANCED)
354 AVLTreeBase::_BalanceInsertRight(AVLTreeNode** node)
356 	if ((*node)->balance_factor > RIGHT) {
358 		AVLTreeNode** right = &(*node)->right;
361 			_RotateLeft(node);
365 			_RotateLeft(node);
370 	if ((*node)->balance_factor == BALANCED)
381 		AVLTreeNode**	node;
388 	AVLTreeNode** node = &fRoot;
391 	while (*node) {
392 		int cmp = fCompare->CompareNodes(nodeToInsert, *node);
393 		if (cmp == 0)	// duplicate node
396 			top->node = node;
399 				node = &(*node)->left;
402 				node = &(*node)->right;
408 	// insert node
409 	*node = nodeToInsert;
418 		(*node)->parent = *top[-1].node;
424 		node = top->node;
427 			(*node)->balance_factor--;
428 			result = _BalanceInsertLeft(node);
431 			(*node)->balance_factor++;
432 			result = _BalanceInsertRight(node);
441 AVLTreeBase::_BalanceRemoveLeft(AVLTreeNode** node)
445 	if ((*node)->balance_factor > RIGHT) {
447 		AVLTreeNode** right = &(*node)->right;
450 			_RotateLeft(node);
453 			_RotateLeft(node);
458 			_RotateLeft(node);
460 	} else if ((*node)->balance_factor == RIGHT)
468 AVLTreeBase::_BalanceRemoveRight(AVLTreeNode** node)
472 	if ((*node)->balance_factor < LEFT) {
474 		AVLTreeNode** left = &(*node)->left;
477 			_RotateRight(node);
480 			_RotateRight(node);
485 			_RotateRight(node);
487 	} else if ((*node)->balance_factor == LEFT)
495 AVLTreeBase::_RemoveRightMostChild(AVLTreeNode** node, AVLTreeNode** foundNode)
502 	while ((*node)->right) {
503 		*top = node;
505 		node = &(*node)->right;
509 	// the found node might have a left child: replace the node with the
511 	*foundNode = *node;
512 	AVLTreeNode* left = (*node)->left;
514 		left->parent = (*node)->parent;
515 	*node = left;
523 		node = *top;
524 		(*node)->balance_factor--;
525 		result = _BalanceRemoveRight(node);
533 AVLTreeBase::_Remove(AVLTreeNode* node)
535 	if (!node)
538 	// remove node
539 	AVLTreeNode* parent = node->parent;
540 	bool isLeft = (parent && parent->left == node);
546 	if (node->left && node->right) {
547 		// node has two children
548 		result = _RemoveRightMostChild(&node->left, &replace);
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;
562 	} else if (node->left) {
563 		// node has only left child
564 		replace = node->left;
566 		replace->balance_factor = node->balance_factor + 1;
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;
575 		// node has no child
583 		node = parent;
584 		parent = node->parent;
586 		isLeft = (parent && parent->left == node);
590 			node->balance_factor++;
594 			node->balance_factor--;
604 AVLTreeBase::_CheckTree(AVLTreeNode* parent, AVLTreeNode* node,
607 	if (node == NULL) {
612 	if (parent != node->parent) {
613 		CHECK_FAILED("AVLTreeBase::_CheckTree(): node %p parent mismatch: "
614 			"%p vs %p", node, parent, node->parent);
618 	int leftDepth = _CheckTree(node, node->left, leftNodeCount);
621 	int rightDepth = _CheckTree(node, node->right, rightNodeCount);
625 		CHECK_FAILED("AVLTreeBase::_CheckTree(): unbalanced subtree: %p", node);
626 	} else if (balance != node->balance_factor) {
628 			"%d vs %d", node, balance, node->balance_factor);