src/tscore/RbTree.cc - trafficserver - Git at Google

 /** @file

   @section license License

   Licensed to the Apache Software Foundation (ASF) under one
   or more contributor license agreements.  See the NOTICE file
   distributed with this work for additional information
   regarding copyright ownership.  The ASF licenses this file
   to you under the Apache License, Version 2.0 (the
   "License"); you may not use this file except in compliance
   with the License.  You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
  */

 #include "tscore/RbTree.h"

 namespace ts
 {
 namespace detail
 {
   /// Equality.
   /// @note If @a n is @c NULL it is treated as having the color @c BLACK.
   /// @return @c true if @a c and the color of @a n are the same.
   inline bool
   operator==(RBNode *n, RBNode::Color c)
   {
     return c == (n ? n->getColor() : RBNode::BLACK);
   }
   /// Equality.
   /// @note If @a n is @c NULL it is treated as having the color @c BLACK.
   /// @return @c true if @a c and the color of @a n are the same.
   inline bool
   operator==(RBNode::Color c, RBNode *n)
   {
     return n == c;
   }

   RBNode *
   RBNode::getChild(Direction d) const
   {
     return d == RIGHT ? _right : d == LEFT ? _left : nullptr;
   }

   RBNode *
   RBNode::rotate(Direction d)
   {
     self *parent        = _parent; // Cache because it can change before we use it.
     Direction child_dir = _parent ? _parent->getChildDirection(this) : NONE;
     Direction other_dir = this->flip(d);
     self *child         = this;

     if (d != NONE && this->getChild(other_dir)) {
       child = this->getChild(other_dir);
       this->clearChild(other_dir);
       this->setChild(child->getChild(d), other_dir);
       child->clearChild(d);
       child->setChild(this, d);
       child->structureFixup();
       this->structureFixup();
       if (parent) {
         parent->clearChild(child_dir);
         parent->setChild(child, child_dir);
       } else {
         child->_parent = nullptr;
       }
     }
     return child;
   }

   RBNode *
   RBNode::setChild(self *n, Direction d)
   {
     if (n) {
       n->_parent = this;
     }
     if (d == RIGHT) {
       _right = n;
     } else if (d == LEFT) {
       _left = n;
     }
     return n;
   }

   // Returns the root node
   RBNode *
   RBNode::rippleStructureFixup()
   {
     self *root = this; // last node seen, root node at the end
     self *p    = this;
     while (p) {
       p->structureFixup();
       root = p;
       p    = root->_parent;
     }
     return root;
   }

   void
   RBNode::replaceWith(self *n)
   {
     n->_color = _color;
     if (_parent) {
       Direction d = _parent->getChildDirection(this);
       _parent->setChild(nullptr, d);
       if (_parent != n) {
         _parent->setChild(n, d);
       }
     } else {
       n->_parent = nullptr;
     }
     n->_left = n->_right = nullptr;
     if (_left && _left != n) {
       n->setChild(_left, LEFT);
     }
     if (_right && _right != n) {
       n->setChild(_right, RIGHT);
     }
     _left = _right = nullptr;
   }

   /* Rebalance the tree. This node is the unbalanced node. */
   RBNode *
   RBNode::rebalanceAfterInsert()
   {
     self *x(this); // the node with the imbalance

     while (x && x->_parent == RED) {
       Direction child_dir = NONE;

       if (x->_parent->_parent) {
         child_dir = x->_parent->_parent->getChildDirection(x->_parent);
       } else {
         break;
       }
       Direction other_dir(flip(child_dir));

       self *y = x->_parent->_parent->getChild(other_dir);
       if (y == RED) {
         x->_parent->_color = BLACK;
         y->_color          = BLACK;
         x                  = x->_parent->_parent;
         x->_color          = RED;
       } else {
         if (x->_parent->getChild(other_dir) == x) {
           x = x->_parent;
           x->rotate(child_dir);
         }
         // Note setting the parent color to BLACK causes the loop to exit.
         x->_parent->_color          = BLACK;
         x->_parent->_parent->_color = RED;
         x->_parent->_parent->rotate(other_dir);
       }
     }

     // every node above this one has a subtree structure change,
     // so notify it. serendipitously, this makes it easy to return
     // the new root node.
     self *root   = this->rippleStructureFixup();
     root->_color = BLACK;

     return root;
   }

   // Returns new root node
   RBNode *
   RBNode::remove()
   {
     self *root = nullptr; // new root node, returned to caller

     /*  Handle two special cases first.
         - This is the only node in the tree, return a new root of NIL
         - This is the root node with only one child, return that child as new root
     */
     if (!_parent && !(_left && _right)) {
       if (_left) {
         _left->_parent = nullptr;
         root           = _left;
         root->_color   = BLACK;
       } else if (_right) {
         _right->_parent = nullptr;
         root            = _right;
         root->_color    = BLACK;
       } // else that was the only node, so leave @a root @c NULL.
       return root;
     }

     /*  The node to be removed from the tree.
         If @c this (the target node) has both children, we remove
         its successor, which cannot have a left child and
         put that node in place of the target node. Otherwise this
         node has at most one child, so we can remove it.
         Note that the successor of a node with a right child is always
         a right descendant of the node. Therefore, remove_node
         is an element of the tree rooted at this node.
         Because of the initial special case checks, we know
         that remove_node is @b not the root node.
     */
     self *remove_node(_left && _right ? _right->leftmostDescendant() : this);

     // This is the color of the node physically removed from the tree.
     // Normally this is the color of @a remove_node
     Color remove_color = remove_node->_color;
     // Need to remember the direction from @a remove_node to @a splice_node
     Direction d(NONE);

     // The child node that will be promoted to replace the removed node.
     // The choice of left or right is irrelevant, as remove_node has at
     // most one child (and splice_node may be NIL if remove_node has no
     // children).
     self *splice_node(remove_node->_left ? remove_node->_left : remove_node->_right);

     if (splice_node) {
       // @c replace_with copies color so in this case the actual color
       // lost is that of the splice_node.
       remove_color = splice_node->_color;
       remove_node->replaceWith(splice_node);
     } else {
       // No children on remove node so we can just clip it off the tree
       // We update splice_node to maintain the invariant that it is
       // the node where the physical removal occurred.
       splice_node = remove_node->_parent;
       // Keep @a d up to date.
       d = splice_node->getChildDirection(remove_node);
       splice_node->setChild(nullptr, d);
     }

     // If the node to pull out of the tree isn't this one,
     // then replace this node in the tree with that removed
     // node in liu of copying the data over.
     if (remove_node != this) {
       // Don't leave @a splice_node referring to a removed node
       if (splice_node == this) {
         splice_node = remove_node;
       }
       this->replaceWith(remove_node);
     }

     root         = splice_node->rebalanceAfterRemove(remove_color, d);
     root->_color = BLACK;
     return root;
   }

   /**
    * Rebalance tree after a deletion
    * Called on the spliced in node or its parent, whichever is not NIL.
    * This modifies the tree structure only if @a c is @c BLACK.
    */
   RBNode *
   RBNode::rebalanceAfterRemove(Color c,    //!< The color of the removed node
                                Direction d //!< Direction of removed node from its parent
   )
   {
     self *root;

     if (BLACK == c) { // only rebalance if too much black
       self *n      = this;
       self *parent = n->_parent;

       // If @a direction is set, then we need to start at a leaf pseudo-node.
       // This is why we need @a parent, otherwise we could just use @a n.
       if (NONE != d) {
         parent = n;
         n      = nullptr;
       }

       while (parent) { // @a n is not the root
         // If the current node is RED, we can just recolor and be done
         if (n && n == RED) {
           n->_color = BLACK;
           break;
         } else {
           // Parameterizing the rebalance logic on the directions. We
           // write for the left child case and flip directions for the
           // right child case
           Direction near(LEFT), far(RIGHT);
           if ((NONE == d && parent->getChildDirection(n) == RIGHT) || RIGHT == d) {
             near = RIGHT;
             far  = LEFT;
           }

           self *w = parent->getChild(far); // sibling(n)

           if (w->_color == RED) {
             w->_color      = BLACK;
             parent->_color = RED;
             parent->rotate(near);
             w = parent->getChild(far);
           }

           self *wfc = w->getChild(far);
           if (w->getChild(near) == BLACK && wfc == BLACK) {
             w->_color = RED;
             n         = parent;
             parent    = n->_parent;
             d         = NONE; // Cancel any leaf node logic
           } else {
             if (wfc == BLACK) {
               w->getChild(near)->_color = BLACK;
               w->_color                 = RED;
               w->rotate(far);
               w   = parent->getChild(far);
               wfc = w->getChild(far); // w changed, update far child cache.
             }
             w->_color      = parent->_color;
             parent->_color = BLACK;
             wfc->_color    = BLACK;
             parent->rotate(near);
             break;
           }
         }
       }
     }
     root = this->rippleStructureFixup();
     return root;
   }

   /** Ensure that the local information associated with each node is
       correct globally This should only be called on debug builds as it
       breaks any efficiencies we have gained from our tree structure.
       */
   int
   RBNode::validate()
   {
 #if 0
   int black_ht = 0;
   int black_ht1, black_ht2;

   if (_left) {
     black_ht1 = _left->validate();
   }
   else
     black_ht1 = 1;

   if (black_ht1 > 0 && _right)
     black_ht2 = _right->validate();
   else
     black_ht2 = 1;

   if (black_ht1 == black_ht2) {
     black_ht = black_ht1;
     if (this->_color == BLACK)
       ++black_ht;
     else {  // No red-red
       if (_left == RED)
         black_ht = 0;
       else if (_right == RED)
         black_ht = 0;
       if (black_ht == 0)
         std::cout << "Red-red child\n";
     }
   } else {
     std::cout << "Height mismatch " << black_ht1 << " " << black_ht2 << "\n";
   }
   if (black_ht > 0 && !this->structureValidate())
     black_ht = 0;

   return black_ht;
 #else
     return 0;
 #endif
   }
 } // namespace detail
 } // namespace ts
	/** @file

	@section license License

	Licensed to the Apache Software Foundation (ASF) under one
	or more contributor license agreements. See the NOTICE file
	distributed with this work for additional information
	regarding copyright ownership. The ASF licenses this file
	to you under the Apache License, Version 2.0 (the
	"License"); you may not use this file except in compliance
	with the License. You may obtain a copy of the License at

	http://www.apache.org/licenses/LICENSE-2.0

	Unless required by applicable law or agreed to in writing, software
	distributed under the License is distributed on an "AS IS" BASIS,
	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	See the License for the specific language governing permissions and
	limitations under the License.
	*/

	#include "tscore/RbTree.h"

	namespace ts
	{
	namespace detail
	{
	/// Equality.
	/// @note If @a n is @c NULL it is treated as having the color @c BLACK.
	/// @return @c true if @a c and the color of @a n are the same.
	inline bool
	operator==(RBNode *n, RBNode::Color c)
	{
	return c == (n ? n->getColor() : RBNode::BLACK);
	}
	/// Equality.
	/// @note If @a n is @c NULL it is treated as having the color @c BLACK.
	/// @return @c true if @a c and the color of @a n are the same.
	inline bool
	operator==(RBNode::Color c, RBNode *n)
	{
	return n == c;
	}

	RBNode *
	RBNode::getChild(Direction d) const
	{
	return d == RIGHT ? _right : d == LEFT ? _left : nullptr;
	}

	RBNode *
	RBNode::rotate(Direction d)
	{
	self *parent = _parent; // Cache because it can change before we use it.
	Direction child_dir = _parent ? _parent->getChildDirection(this) : NONE;
	Direction other_dir = this->flip(d);
	self *child = this;

	if (d != NONE && this->getChild(other_dir)) {
	child = this->getChild(other_dir);
	this->clearChild(other_dir);
	this->setChild(child->getChild(d), other_dir);
	child->clearChild(d);
	child->setChild(this, d);
	child->structureFixup();
	this->structureFixup();
	if (parent) {
	parent->clearChild(child_dir);
	parent->setChild(child, child_dir);
	} else {
	child->_parent = nullptr;
	}
	}
	return child;
	}

	RBNode *
	RBNode::setChild(self *n, Direction d)
	{
	if (n) {
	n->_parent = this;
	}
	if (d == RIGHT) {
	_right = n;
	} else if (d == LEFT) {
	_left = n;
	}
	return n;
	}

	// Returns the root node
	RBNode *
	RBNode::rippleStructureFixup()
	{
	self *root = this; // last node seen, root node at the end
	self *p = this;
	while (p) {
	p->structureFixup();
	root = p;
	p = root->_parent;
	}
	return root;
	}

	void
	RBNode::replaceWith(self *n)
	{
	n->_color = _color;
	if (_parent) {
	Direction d = _parent->getChildDirection(this);
	_parent->setChild(nullptr, d);
	if (_parent != n) {
	_parent->setChild(n, d);
	}
	} else {
	n->_parent = nullptr;
	}
	n->_left = n->_right = nullptr;
	if (_left && _left != n) {
	n->setChild(_left, LEFT);
	}
	if (_right && _right != n) {
	n->setChild(_right, RIGHT);
	}
	_left = _right = nullptr;
	}

	/* Rebalance the tree. This node is the unbalanced node. */
	RBNode *
	RBNode::rebalanceAfterInsert()
	{
	self *x(this); // the node with the imbalance

	while (x && x->_parent == RED) {
	Direction child_dir = NONE;

	if (x->_parent->_parent) {
	child_dir = x->_parent->_parent->getChildDirection(x->_parent);
	} else {
	break;
	}
	Direction other_dir(flip(child_dir));

	self *y = x->_parent->_parent->getChild(other_dir);
	if (y == RED) {
	x->_parent->_color = BLACK;
	y->_color = BLACK;
	x = x->_parent->_parent;
	x->_color = RED;
	} else {
	if (x->_parent->getChild(other_dir) == x) {
	x = x->_parent;
	x->rotate(child_dir);
	}
	// Note setting the parent color to BLACK causes the loop to exit.
	x->_parent->_color = BLACK;
	x->_parent->_parent->_color = RED;
	x->_parent->_parent->rotate(other_dir);
	}
	}

	// every node above this one has a subtree structure change,
	// so notify it. serendipitously, this makes it easy to return
	// the new root node.
	self *root = this->rippleStructureFixup();
	root->_color = BLACK;

	return root;
	}

	// Returns new root node
	RBNode *
	RBNode::remove()
	{
	self *root = nullptr; // new root node, returned to caller

	/* Handle two special cases first.
	- This is the only node in the tree, return a new root of NIL
	- This is the root node with only one child, return that child as new root
	*/
	if (!_parent && !(_left && _right)) {
	if (_left) {
	_left->_parent = nullptr;
	root = _left;
	root->_color = BLACK;
	} else if (_right) {
	_right->_parent = nullptr;
	root = _right;
	root->_color = BLACK;
	} // else that was the only node, so leave @a root @c NULL.
	return root;
	}

	/* The node to be removed from the tree.
	If @c this (the target node) has both children, we remove
	its successor, which cannot have a left child and
	put that node in place of the target node. Otherwise this
	node has at most one child, so we can remove it.
	Note that the successor of a node with a right child is always
	a right descendant of the node. Therefore, remove_node
	is an element of the tree rooted at this node.
	Because of the initial special case checks, we know
	that remove_node is @b not the root node.
	*/
	self *remove_node(_left && _right ? _right->leftmostDescendant() : this);

	// This is the color of the node physically removed from the tree.
	// Normally this is the color of @a remove_node
	Color remove_color = remove_node->_color;
	// Need to remember the direction from @a remove_node to @a splice_node
	Direction d(NONE);

	// The child node that will be promoted to replace the removed node.
	// The choice of left or right is irrelevant, as remove_node has at
	// most one child (and splice_node may be NIL if remove_node has no
	// children).
	self *splice_node(remove_node->_left ? remove_node->_left : remove_node->_right);

	if (splice_node) {
	// @c replace_with copies color so in this case the actual color
	// lost is that of the splice_node.
	remove_color = splice_node->_color;
	remove_node->replaceWith(splice_node);
	} else {
	// No children on remove node so we can just clip it off the tree
	// We update splice_node to maintain the invariant that it is
	// the node where the physical removal occurred.
	splice_node = remove_node->_parent;
	// Keep @a d up to date.
	d = splice_node->getChildDirection(remove_node);
	splice_node->setChild(nullptr, d);
	}

	// If the node to pull out of the tree isn't this one,
	// then replace this node in the tree with that removed
	// node in liu of copying the data over.
	if (remove_node != this) {
	// Don't leave @a splice_node referring to a removed node
	if (splice_node == this) {
	splice_node = remove_node;
	}
	this->replaceWith(remove_node);
	}

	root = splice_node->rebalanceAfterRemove(remove_color, d);
	root->_color = BLACK;
	return root;
	}

	/**
	* Rebalance tree after a deletion
	* Called on the spliced in node or its parent, whichever is not NIL.
	* This modifies the tree structure only if @a c is @c BLACK.
	*/
	RBNode *
	RBNode::rebalanceAfterRemove(Color c, //!< The color of the removed node
	Direction d //!< Direction of removed node from its parent
	)
	{
	self *root;

	if (BLACK == c) { // only rebalance if too much black
	self *n = this;
	self *parent = n->_parent;

	// If @a direction is set, then we need to start at a leaf pseudo-node.
	// This is why we need @a parent, otherwise we could just use @a n.
	if (NONE != d) {
	parent = n;
	n = nullptr;
	}

	while (parent) { // @a n is not the root
	// If the current node is RED, we can just recolor and be done
	if (n && n == RED) {
	n->_color = BLACK;
	break;
	} else {
	// Parameterizing the rebalance logic on the directions. We
	// write for the left child case and flip directions for the
	// right child case
	Direction near(LEFT), far(RIGHT);
	if ((NONE == d && parent->getChildDirection(n) == RIGHT) \|\| RIGHT == d) {
	near = RIGHT;
	far = LEFT;
	}

	self *w = parent->getChild(far); // sibling(n)

	if (w->_color == RED) {
	w->_color = BLACK;
	parent->_color = RED;
	parent->rotate(near);
	w = parent->getChild(far);
	}

	self *wfc = w->getChild(far);
	if (w->getChild(near) == BLACK && wfc == BLACK) {
	w->_color = RED;
	n = parent;
	parent = n->_parent;
	d = NONE; // Cancel any leaf node logic
	} else {
	if (wfc == BLACK) {
	w->getChild(near)->_color = BLACK;
	w->_color = RED;
	w->rotate(far);
	w = parent->getChild(far);
	wfc = w->getChild(far); // w changed, update far child cache.
	}
	w->_color = parent->_color;
	parent->_color = BLACK;
	wfc->_color = BLACK;
	parent->rotate(near);
	break;
	}
	}
	}
	}
	root = this->rippleStructureFixup();
	return root;
	}

	/** Ensure that the local information associated with each node is
	correct globally This should only be called on debug builds as it
	breaks any efficiencies we have gained from our tree structure.
	*/
	int
	RBNode::validate()
	{
	#if 0
	int black_ht = 0;
	int black_ht1, black_ht2;

	if (_left) {
	black_ht1 = _left->validate();
	}
	else
	black_ht1 = 1;

	if (black_ht1 > 0 && _right)
	black_ht2 = _right->validate();
	else
	black_ht2 = 1;

	if (black_ht1 == black_ht2) {
	black_ht = black_ht1;
	if (this->_color == BLACK)
	++black_ht;
	else { // No red-red
	if (_left == RED)
	black_ht = 0;
	else if (_right == RED)
	black_ht = 0;
	if (black_ht == 0)
	std::cout << "Red-red child\n";
	}
	} else {
	std::cout << "Height mismatch " << black_ht1 << " " << black_ht2 << "\n";
	}
	if (black_ht > 0 && !this->structureValidate())
	black_ht = 0;

	return black_ht;
	#else
	return 0;
	#endif
	}
	} // namespace detail
	} // namespace ts