Repository: trafficserver Updated Branches: refs/heads/master f1bedb41e -> 0999715dd
Changes to RBNode to make it more generally useful Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/0999715d Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/0999715d Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/0999715d Branch: refs/heads/master Commit: 0999715dd7581f9911809a5dfc7a8dd5f45f150e Parents: f1bedb4 Author: Brian Geffon <[email protected]> Authored: Tue Oct 7 19:07:53 2014 -0700 Committer: Brian Geffon <[email protected]> Committed: Tue Oct 7 19:07:53 2014 -0700 ---------------------------------------------------------------------- lib/ts/RbTree.cc | 4 ++-- lib/ts/RbTree.h | 8 ++++++++ 2 files changed, 10 insertions(+), 2 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0999715d/lib/ts/RbTree.cc ---------------------------------------------------------------------- diff --git a/lib/ts/RbTree.cc b/lib/ts/RbTree.cc index 926a063..ba7d2a0 100644 --- a/lib/ts/RbTree.cc +++ b/lib/ts/RbTree.cc @@ -36,7 +36,7 @@ inline bool operator == ( RBNode::Color c, RBNode* n ) { return n == c; } -inline RBNode* +RBNode* RBNode::getChild(Direction d) const { return d == RIGHT ? _right : d == LEFT ? _left @@ -181,7 +181,7 @@ RBNode::remove() { 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); + 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 http://git-wip-us.apache.org/repos/asf/trafficserver/blob/0999715d/lib/ts/RbTree.h ---------------------------------------------------------------------- diff --git a/lib/ts/RbTree.h b/lib/ts/RbTree.h index 8bf5f3e..5c8ac43 100644 --- a/lib/ts/RbTree.h +++ b/lib/ts/RbTree.h @@ -66,6 +66,14 @@ struct RBNode { /// @return The color of the node. Color getColor() const { return _color; } + self* leftmostDescendant() const { + const self* n = this; + while (n->_left) + n = n->_left; + + return const_cast<self*>(n); + } + /** Reverse a direction @return @c LEFT if @a d is @c RIGHT, @c RIGHT if @a d is @c LEFT, @c NONE otherwise.
