Repository: trafficserver Updated Branches: refs/heads/master 5ee27f38d -> 4d8e09ec4
TS-3114: Refactor IpMap to make the RB tree a shared data structure Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/4d8e09ec Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/4d8e09ec Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/4d8e09ec Branch: refs/heads/master Commit: 4d8e09ec4f76da5574d6de13c152058eeda7dd93 Parents: 5ee27f3 Author: Brian Geffon <[email protected]> Authored: Mon Oct 6 22:09:32 2014 -0700 Committer: Brian Geffon <[email protected]> Committed: Mon Oct 6 22:09:32 2014 -0700 ---------------------------------------------------------------------- lib/ts/IpMap.cc | 326 -------------------------------------------- lib/ts/IpMap.h | 165 +--------------------- lib/ts/Makefile.am | 4 +- lib/ts/RbTree.cc | 355 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/ts/RbTree.h | 196 ++++++++++++++++++++++++++ 5 files changed, 555 insertions(+), 491 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/4d8e09ec/lib/ts/IpMap.cc ---------------------------------------------------------------------- diff --git a/lib/ts/IpMap.cc b/lib/ts/IpMap.cc index 9a9421a..4b879ff 100644 --- a/lib/ts/IpMap.cc +++ b/lib/ts/IpMap.cc @@ -97,332 +97,6 @@ inline bool operator>(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) { return ts::detail::cmp(lhs, *rhs) > 0; } -/// 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; -} - -inline RBNode* -RBNode::getChild(Direction d) const { - return d == RIGHT ? _right - : d == LEFT ? _left - : 0 - ; -} - -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 = 0; - } - } - 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(0, d); - if (_parent != n) _parent->setChild(n, d); - } else { - n->_parent = 0; - } - n->_left = n->_right = 0; - if (_left && _left != n) n->setChild(_left, LEFT); - if (_right && _right != n) n->setChild(_right, RIGHT); - _left = _right = 0; -} - -/* 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 = 0; // 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 = 0; - root = _left; - root->_color = BLACK; - } else if (_right) { - _right->_parent = 0; - 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 ? _next : 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(0, 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 psuedo-node. - // This is why we need @a parent, otherwise we could just use @a n. - if (NONE != d) { - parent = n; - n = 0; - } - - while (parent) { // @a n is not the root - // If the current node is RED, we can just recolor and be done - if (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->_color == 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 -} - /** Base template class for IP maps. This class is templated by the @a N type which must be a subclass of @c RBNode. This class carries information about the addresses stored http://git-wip-us.apache.org/repos/asf/trafficserver/blob/4d8e09ec/lib/ts/IpMap.h ---------------------------------------------------------------------- diff --git a/lib/ts/IpMap.h b/lib/ts/IpMap.h index 917158f..7afb9a6 100644 --- a/lib/ts/IpMap.h +++ b/lib/ts/IpMap.h @@ -3,6 +3,7 @@ # include "ink_platform.h" # include "ink_defs.h" +# include "RbTree.h" # include <ts/ink_inet.h> # include <ts/IntrusiveDList.h> # include <ts/ink_assert.h> @@ -56,170 +57,6 @@ namespace ts { namespace detail { class Ip4Map; // Forward declare. class Ip6Map; // Forward declare. - /** A node in a red/black tree. - - This class provides only the basic tree operations. The client - must provide the search and decision logic. This enables this - class to be a base class for templated nodes with much less code - duplication. - */ - struct RBNode { - typedef RBNode self; ///< self reference type - - /// Node colors - typedef enum { RED, BLACK } Color; - - /// Directional constants - typedef enum { NONE, LEFT, RIGHT } Direction; - - /// Get a child by direction. - /// @return The child in the direction @a d if it exists, - /// @c NULL if not. - self* getChild( - Direction d //!< The direction of the desired child - ) const; - - /** Determine which child a node is - @return @c LEFT if @a n is the left child, - @c RIGHT if @a n is the right child, - @c NONE if @a n is not a child - */ - Direction getChildDirection( - self* const& n //!< The presumed child node - ) const { - return (n == _left) ? LEFT : (n == _right) ? RIGHT : NONE; - } - - /** Get the parent node. - @return A Node* to the parent node or a @c nil Node* if no parent. - */ - self* getParent() const { return const_cast<self*>(_parent); } - - /// @return The color of the node. - Color getColor() const { return _color; } - - /** Reverse a direction - @return @c LEFT if @a d is @c RIGHT, @c RIGHT if @a d is @c LEFT, - @c NONE otherwise. - */ - Direction flip(Direction d) { - return LEFT == d ? RIGHT : RIGHT == d ? LEFT : NONE; - } - - /** Perform internal validation checks. - @return 0 on failure, black height of the tree on success. - */ - int validate(); - - /// Default constructor. - RBNode() - : _color(RED) - , _parent(0) - , _left(0) - , _right(0) - , _next(0) - , _prev(0) { - } - - /// Destructor (force virtual). - virtual ~RBNode() { } - - /** Rotate the subtree rooted at this node. - The node is rotated in to the position of one of its children. - Which child is determined by the direction parameter @a d. The - child in the other direction becomes the new root of the subtree. - - If the parent pointer is set, then the child pointer of the original - parent is updated so that the tree is left in a consistent state. - - @note If there is no child in the other direction, the rotation - fails and the original node is returned. It is @b not required - that a child exist in the direction specified by @a d. - - @return The new root node for the subtree. - */ - self* rotate( - Direction d //!< The direction to rotate - ); - - /** Set the child node in direction @a d to @a n. - The @a d child is set to the node @a n. The pointers in this - node and @a n are set correctly. This can only be called if - there is no child node already present. - - @return @a n. - */ - self* setChild( - self* n, //!< The node to set as the child - Direction d //!< The direction of the child - ); - - /** Remove this node from the tree. - The tree is rebalanced after removal. - @return The new root node. - */ - self* remove(); - - void clearChild(Direction dir) { - if (LEFT == dir) _left = 0; - else if (RIGHT == dir) _right = 0; - } - - /** @name Subclass hook methods */ - //@{ - /** Structural change notification. - This method is called if the structure of the subtree rooted at - this node was changed. - - This is intended a hook. The base method is empty so that subclasses - are not required to override. - */ - virtual void structureFixup() {} - - /** Called from @c validate to perform any additional validation checks. - Clients should chain this if they wish to perform additional checks. - @return @c true if the validation is successful, @c false otherwise. - @note The base method simply returns @c true. - */ - virtual bool structureValidate() { return true; } - //@} - - /** Replace this node with another node. - This is presumed to be non-order modifying so the next reference - is @b not updated. - */ - void replaceWith( - self* n //!< Node to put in place of this node. - ); - - //! Rebalance the tree starting at this node - /** The tree is rebalanced so that all of the invariants are - true. The (potentially new) root of the tree is returned. - - @return The root node of the tree after the rebalance. - */ - self* rebalanceAfterInsert(); - - /** Rebalance the tree after a deletion. - Called on the lowest modified node. - @return The new root of the tree. - */ - self* rebalanceAfterRemove( - Color c, //!< The color of the removed node. - Direction d //!< Direction of removed node from parent - ); - - //! Invoke @c structure_fixup() on this node and all of its ancestors. - self* rippleStructureFixup(); - - Color _color; ///< node color - self* _parent; ///< parent node (needed for rotations) - self* _left; ///< left child - self* _right; ///< right child - self* _next; ///< Next node. - self* _prev; ///< Previous node. - }; - }} // namespace ts::detail /** Map from IP addresses to client data. http://git-wip-us.apache.org/repos/asf/trafficserver/blob/4d8e09ec/lib/ts/Makefile.am ---------------------------------------------------------------------- diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am index d1bcc89..00ff352 100644 --- a/lib/ts/Makefile.am +++ b/lib/ts/Makefile.am @@ -177,7 +177,9 @@ libtsutil_la_SOURCES = \ ink_time.h \ libts.h \ llqueue.cc \ - lockfile.cc + lockfile.cc \ + RbTree.cc \ + RbTree.h #test_UNUSED_SOURCES = \ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/4d8e09ec/lib/ts/RbTree.cc ---------------------------------------------------------------------- diff --git a/lib/ts/RbTree.cc b/lib/ts/RbTree.cc new file mode 100644 index 0000000..926a063 --- /dev/null +++ b/lib/ts/RbTree.cc @@ -0,0 +1,355 @@ +/** @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 "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; +} + +inline RBNode* +RBNode::getChild(Direction d) const { + return d == RIGHT ? _right + : d == LEFT ? _left + : 0 + ; +} + +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 = 0; + } + } + 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(0, d); + if (_parent != n) _parent->setChild(n, d); + } else { + n->_parent = 0; + } + n->_left = n->_right = 0; + if (_left && _left != n) n->setChild(_left, LEFT); + if (_right && _right != n) n->setChild(_right, RIGHT); + _left = _right = 0; +} + +/* 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 = 0; // 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 = 0; + root = _left; + root->_color = BLACK; + } else if (_right) { + _right->_parent = 0; + 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 ? _next : 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(0, 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 psuedo-node. + // This is why we need @a parent, otherwise we could just use @a n. + if (NONE != d) { + parent = n; + n = 0; + } + + while (parent) { // @a n is not the root + // If the current node is RED, we can just recolor and be done + if (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->_color == 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 +} + +}} + + + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/4d8e09ec/lib/ts/RbTree.h ---------------------------------------------------------------------- diff --git a/lib/ts/RbTree.h b/lib/ts/RbTree.h new file mode 100644 index 0000000..8bf5f3e --- /dev/null +++ b/lib/ts/RbTree.h @@ -0,0 +1,196 @@ +/** @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. + */ + +#ifndef RBTREE_H_ +#define RBTREE_H_ + +namespace ts { namespace detail { + +/** A node in a red/black tree. + + This class provides only the basic tree operations. The client + must provide the search and decision logic. This enables this + class to be a base class for templated nodes with much less code + duplication. +*/ +struct RBNode { + typedef RBNode self; ///< self reference type + + /// Node colors + typedef enum { RED, BLACK } Color; + + /// Directional constants + typedef enum { NONE, LEFT, RIGHT } Direction; + + /// Get a child by direction. + /// @return The child in the direction @a d if it exists, + /// @c NULL if not. + self* getChild( + Direction d //!< The direction of the desired child + ) const; + + /** Determine which child a node is + @return @c LEFT if @a n is the left child, + @c RIGHT if @a n is the right child, + @c NONE if @a n is not a child + */ + Direction getChildDirection( + self* const& n //!< The presumed child node + ) const { + return (n == _left) ? LEFT : (n == _right) ? RIGHT : NONE; + } + + /** Get the parent node. + @return A Node* to the parent node or a @c nil Node* if no parent. + */ + self* getParent() const { return const_cast<self*>(_parent); } + + /// @return The color of the node. + Color getColor() const { return _color; } + + /** Reverse a direction + @return @c LEFT if @a d is @c RIGHT, @c RIGHT if @a d is @c LEFT, + @c NONE otherwise. + */ + Direction flip(Direction d) { + return LEFT == d ? RIGHT : RIGHT == d ? LEFT : NONE; + } + + /** Perform internal validation checks. + @return 0 on failure, black height of the tree on success. + */ + int validate(); + + /// Default constructor. + RBNode() + : _color(RED) + , _parent(0) + , _left(0) + , _right(0) + , _next(0) + , _prev(0) { + } + + /// Destructor (force virtual). + virtual ~RBNode() { } + + /** Rotate the subtree rooted at this node. + The node is rotated in to the position of one of its children. + Which child is determined by the direction parameter @a d. The + child in the other direction becomes the new root of the subtree. + + If the parent pointer is set, then the child pointer of the original + parent is updated so that the tree is left in a consistent state. + + @note If there is no child in the other direction, the rotation + fails and the original node is returned. It is @b not required + that a child exist in the direction specified by @a d. + + @return The new root node for the subtree. + */ + self* rotate( + Direction d //!< The direction to rotate + ); + + /** Set the child node in direction @a d to @a n. + The @a d child is set to the node @a n. The pointers in this + node and @a n are set correctly. This can only be called if + there is no child node already present. + + @return @a n. + */ + self* setChild( + self* n, //!< The node to set as the child + Direction d //!< The direction of the child + ); + + /** Remove this node from the tree. + The tree is rebalanced after removal. + @return The new root node. + */ + self* remove(); + + void clearChild(Direction dir) { + if (LEFT == dir) _left = 0; + else if (RIGHT == dir) _right = 0; + } + + /** @name Subclass hook methods */ + //@{ + /** Structural change notification. + This method is called if the structure of the subtree rooted at + this node was changed. + + This is intended a hook. The base method is empty so that subclasses + are not required to override. + */ + virtual void structureFixup() {} + + /** Called from @c validate to perform any additional validation checks. + Clients should chain this if they wish to perform additional checks. + @return @c true if the validation is successful, @c false otherwise. + @note The base method simply returns @c true. + */ + virtual bool structureValidate() { return true; } + //@} + + /** Replace this node with another node. + This is presumed to be non-order modifying so the next reference + is @b not updated. + */ + void replaceWith( + self* n //!< Node to put in place of this node. + ); + + //! Rebalance the tree starting at this node + /** The tree is rebalanced so that all of the invariants are + true. The (potentially new) root of the tree is returned. + + @return The root node of the tree after the rebalance. + */ + self* rebalanceAfterInsert(); + + /** Rebalance the tree after a deletion. + Called on the lowest modified node. + @return The new root of the tree. + */ + self* rebalanceAfterRemove( + Color c, //!< The color of the removed node. + Direction d //!< Direction of removed node from parent + ); + + //! Invoke @c structure_fixup() on this node and all of its ancestors. + self* rippleStructureFixup(); + + Color _color; ///< node color + self* _parent; ///< parent node (needed for rotations) + self* _left; ///< left child + self* _right; ///< right child + self* _next; ///< Next node. + self* _prev; ///< Previous node. +}; + +} /* namespace detail */ + +} /* namespace ts */ + + +#endif /* RBTREE_H_ */
