trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bri...@apache.org
Subject git commit: TS-3114: Refactor IpMap to make the RB tree a shared data structure
Date Tue, 07 Oct 2014 05:09:45 GMT
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 <briang@apache.org>
Authored: Mon Oct 6 22:09:32 2014 -0700
Committer: Brian Geffon <briang@apache.org>
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_ */


Mime
View raw message