This is an automated email from the ASF dual-hosted git repository. amc pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push: new 283e00ada8 libswoc - remove legacy RbTree. (#10109) 283e00ada8 is described below commit 283e00ada8983bc71120517dd4b2a68cecd6975c Author: Alan M. Carroll <a...@apache.org> AuthorDate: Fri Jul 28 09:34:34 2023 -0500 libswoc - remove legacy RbTree. (#10109) --- include/tscore/RbTree.h | 219 --------------------------- src/tscore/CMakeLists.txt | 1 - src/tscore/Makefile.am | 1 - src/tscore/RbTree.cc | 370 ---------------------------------------------- 4 files changed, 591 deletions(-) diff --git a/include/tscore/RbTree.h b/include/tscore/RbTree.h deleted file mode 100644 index 2f7dc2ecae..0000000000 --- a/include/tscore/RbTree.h +++ /dev/null @@ -1,219 +0,0 @@ -/** @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. - */ - -#pragma once - -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 { - using self = RBNode; ///< self reference type - - /// Node colors - using Color = enum { - RED, - BLACK, - }; - - /// Directional constants - using Direction = enum { - NONE, - LEFT, - RIGHT, - }; - - /// 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; - } - - 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. - */ - 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() {} - /// 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 = nullptr; - else if (RIGHT == dir) - _right = nullptr; - } - - /** @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 = RED; ///< node color - self *_parent = nullptr; ///< parent node (needed for rotations) - self *_left = nullptr; ///< left child - self *_right = nullptr; ///< right child - self *_next = nullptr; ///< Next node. - self *_prev = nullptr; ///< Previous node. - }; - -} /* namespace detail */ - -} /* namespace ts */ diff --git a/src/tscore/CMakeLists.txt b/src/tscore/CMakeLists.txt index d1e25c7dcd..cae7bdc15c 100644 --- a/src/tscore/CMakeLists.txt +++ b/src/tscore/CMakeLists.txt @@ -56,7 +56,6 @@ add_library(tscore STATIC MatcherUtils.cc ParseRules.cc Random.cc - RbTree.cc Regex.cc Regression.cc SourceLocation.cc diff --git a/src/tscore/Makefile.am b/src/tscore/Makefile.am index 707be7af7e..8ab634398a 100644 --- a/src/tscore/Makefile.am +++ b/src/tscore/Makefile.am @@ -97,7 +97,6 @@ libtscore_a_SOURCES = \ MMH.cc \ ParseRules.cc \ Random.cc \ - RbTree.cc \ Regex.cc \ Regression.cc \ runroot.cc \ diff --git a/src/tscore/RbTree.cc b/src/tscore/RbTree.cc deleted file mode 100644 index 23bb41741d..0000000000 --- a/src/tscore/RbTree.cc +++ /dev/null @@ -1,370 +0,0 @@ -/** @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