BIND 10 trac2750, updated. 091b8584615ed5da2441c579bc37cf1e9681db80 [2750] Make various updates (see full log)
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Sep 2 09:36:40 UTC 2013
The branch, trac2750 has been updated
via 091b8584615ed5da2441c579bc37cf1e9681db80 (commit)
via 2a07912bb6cb95f4df5caffdc6df4b07219b5dc3 (commit)
via 275d63283fe322e93ede93045b6ad870a6eaac68 (commit)
via 23078e9f9718a8dd92180f15a419ef2db1e4c69b (commit)
via 73d7a9538986f78b96584f5f9ce4946f86f05536 (commit)
from 927411d1d221265f82608e62a22683c203103209 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 091b8584615ed5da2441c579bc37cf1e9681db80
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 2 15:02:13 2013 +0530
[2750] Make various updates (see full log)
* Use safer isRed() and isBlack() static functions which test for
NULL pointers (as we use NULL black leaves)
* Add code comments explaining various RB rebalance cases
* Simplify code by rearranging it
* Optimize code by re-assigning sibling only where necessary
* Add some assertions
commit 2a07912bb6cb95f4df5caffdc6df4b07219b5dc3
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 2 10:31:59 2013 +0530
[2750] Update some checks
commit 275d63283fe322e93ede93045b6ad870a6eaac68
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 2 10:09:56 2013 +0530
[2750] Recompute sibling after rotations
commit 23078e9f9718a8dd92180f15a419ef2db1e4c69b
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 2 09:54:29 2013 +0530
[2750] Remove redundant argument
commit 73d7a9538986f78b96584f5f9ce4946f86f05536
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 2 09:04:22 2013 +0530
[2750] Simplify condition
It has the same effect, but is simpler to read.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 151 ++++++++++++++++++++++++++---------
1 file changed, 114 insertions(+), 37 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 666db59..de23276 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -361,11 +361,26 @@ private:
return (getColor() == BLACK);
}
+ /// \brief Static variant of isBlack() that also allows NULL nodes.
+ static bool isBlack(DomainTreeNode<T>* node) {
+ if (!node) {
+ // NULL nodes are black.
+ return (true);
+ }
+
+ return (node->isBlack());
+ }
+
/// \brief Returns if the node color is red
bool isRed() const {
return (!isBlack());
}
+ /// \brief Static variant of isRed() that also allows NULL nodes.
+ static bool isRed(DomainTreeNode<T>* node) {
+ return (!isBlack(node));
+ }
+
/// \brief Sets the color of this node
void setColor(const DomainTreeNodeColor color) {
if (color == RED) {
@@ -1713,7 +1728,7 @@ private:
void
removeRebalance(typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr,
- DomainTreeNode<T>* child, DomainTreeNode<T>* parent);
+ DomainTreeNode<T>* child);
DomainTreeNode<T>*
rightRotate(typename DomainTreeNode<T>::DomainTreeNodePtr* root,
@@ -2334,7 +2349,7 @@ DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
// red-black tree again.
typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr =
upper_node ? &(upper_node->down_) : &root_;
- removeRebalance(root_ptr, child, node->getParent());
+ removeRebalance(root_ptr, child);
}
}
@@ -2657,67 +2672,129 @@ template <typename T>
void
DomainTree<T>::removeRebalance
(typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr,
- DomainTreeNode<T>* child, DomainTreeNode<T>* parent)
+ DomainTreeNode<T>* child)
{
- while (&(parent->down_) != root_ptr) {
+ // Case 1. Repeat until we reach the root node of this subtree in
+ // the forest.
+ while (child && (!child->isSubTreeRoot())) {
+ DomainTreeNode<T>* parent = child->getParent();
+
// A sibling node is defined as the parent's other child. It
// exists at the same level as child. Note that child can be
// NULL here.
DomainTreeNode<T>* sibling = (parent->getLeft() == child) ?
parent->getRight() : parent->getLeft();
- if (sibling && sibling->isRed()) {
+ // NOTE #1: Understand this clearly. We are here only because in
+ // the path through parent--child, a BLACK node was removed,
+ // i.e., the sibling's side in the path through parent--sibling
+ // is heavier by 1 extra BLACK node in its path. Because this
+ // can be an iterative process up the tree, the key is to
+ // understand this point when entering the block here.
+
+ // NOTE #2: sibling cannot be NULL here as parent--child has
+ // fewer BLACK nodes than parent--sibling.
+ assert(sibling);
+
+ // If sibling is RED, convert the tree to a form where sibling
+ // is BLACK.
+ if (DomainTreeNode<T>::isRed(sibling)) {
+ // Case 2. Here, the sibling is RED. We do a tree rotation
+ // at the parent such that sibling is the new parent, and
+ // the old parent is sibling's child. We also invert the
+ // colors of the two nodes. This step is done to convert the
+ // tree to a form for steps below.
+
+ /* Parent (P) has to be BLACK here as its child sibling (S)
+ * is RED.
+ *
+ * P(B) S(B)
+ * / \ / \
+ * C(?) S(R) => P(R) y(B)
+ * / \ / \ / \
+ * x(B) y(B) C(?) x(B)
+ * / \
+ */
+
parent->setColor(DomainTreeNode<T>::RED);
sibling->setColor(DomainTreeNode<T>::BLACK);
+
if (parent->getLeft() == child) {
leftRotate(root_ptr, parent);
} else {
rightRotate(root_ptr, parent);
}
- }
- // FIXME: Can sibling be NULL here?
- if (parent->isBlack() &&
- sibling->isBlack() &&
- ((!sibling->getLeft()) || sibling->getLeft()->isBlack()) &&
- ((!sibling->getRight()) || sibling->getRight()->isBlack()))
- {
- sibling->setColor(DomainTreeNode<T>::RED);
- child = parent;
- parent = parent->getParent();
- continue;
+ // Re-compute child's sibling due to the tree adjustment
+ // above.
+ sibling = (parent->getLeft() == child) ?
+ parent->getRight() : parent->getLeft();
}
- // FIXME: Can sibling be NULL here?
- if (parent->isRed() &&
- sibling->isBlack() &&
- ((!sibling->getLeft()) || sibling->getLeft()->isBlack()) &&
- ((!sibling->getRight()) || sibling->getRight()->isBlack()))
+ // NOTE #3: From above, sibling must be BLACK here. If a tree
+ // rotation happened above, the new sibling's side through
+ // parent--sibling [x(B)] above is still heavier than
+ // parent--child by 1 extra BLACK node in its path.
+ assert(DomainTreeNode<T>::isBlack(sibling));
+
+ // NOTE #4: sibling still cannot be NULL here as parent--child
+ // has fewer BLACK nodes than parent--sibling.
+ assert(sibling);
+
+ // Case 3. If both of sibling's children are BLACK, then set the
+ // sibling's color to RED. This reduces the number of BLACK
+ // nodes in parent--sibling path by 1 and balances the BLACK
+ // nodes count on both sides of parent. But this introduces
+ // another issue which is that the path through one child
+ // (=parent) of parent's parent (child's grandparent) has fewer
+ // BLACK nodes now than the other child (parent's sibling).
+ //
+ // To fix this: (a) if parent is colored RED, we can change its
+ // color to BLACK (to increment the number of black nodes in
+ // grandparent--parent-->path) and we're done with the
+ // rebalacing; (b) if parent is colored BLACK, then we set
+ // child=parent and go back to the beginning of the loop to
+ // repeat the original rebalancing problem 1 node higher up the
+ // tree (see NOTE #1 above).
+ if ((DomainTreeNode<T>::isBlack(sibling->getLeft()) &&
+ DomainTreeNode<T>::isBlack(sibling->getRight())))
{
sibling->setColor(DomainTreeNode<T>::RED);
- parent->setColor(DomainTreeNode<T>::BLACK);
- break;
+
+ if (parent->isBlack()) {
+ child = parent;
+ continue;
+ } else {
+ parent->setColor(DomainTreeNode<T>::BLACK);
+ break;
+ }
}
if (sibling->isBlack()) {
- if ((parent->getLeft() == child) &&
- (sibling->getLeft() && sibling->getLeft()->isRed()) &&
- ((!sibling->getRight()) || sibling->getRight()->isBlack()))
+ DomainTreeNode<T>* ss1 = sibling->getLeft();
+ DomainTreeNode<T>* ss2 = sibling->getRight();
+
+ if (parent->getLeft() != child) {
+ std::swap(ss1, ss2);
+ }
+
+ if (DomainTreeNode<T>::isRed(ss1) &&
+ DomainTreeNode<T>::isBlack(ss2))
{
sibling->setColor(DomainTreeNode<T>::RED);
- if (sibling->getLeft()) {
- sibling->getLeft()->setColor(DomainTreeNode<T>::BLACK);
+ if (ss1) {
+ ss1->setColor(DomainTreeNode<T>::BLACK);
}
- rightRotate(root_ptr, sibling);
- } else if ((parent->getRight() == child) &&
- (sibling->getRight() && sibling->getRight()->isRed()) &&
- ((!sibling->getLeft()) || sibling->getLeft()->isBlack()))
- {
- sibling->setColor(DomainTreeNode<T>::RED);
- if (sibling->getRight()) {
- sibling->getRight()->setColor(DomainTreeNode<T>::BLACK);
+
+ if (parent->getLeft() != child) {
+ rightRotate(root_ptr, sibling);
+ } else {
+ leftRotate(root_ptr, sibling);
}
- leftRotate(root_ptr, sibling);
+ // Re-compute child's sibling due to the tree adjustment
+ // above.
+ sibling = (parent->getLeft() == child) ?
+ parent->getRight() : parent->getLeft();
}
}
More information about the bind10-changes
mailing list