trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bri...@apache.org
Subject git commit: Changes to RBNode to make it more generally useful
Date Wed, 08 Oct 2014 18:47:35 GMT
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 <briang@apache.org>
Authored: Tue Oct 7 19:07:53 2014 -0700
Committer: Brian Geffon <briang@apache.org>
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.


Mime
View raw message