Repository: trafficserver Updated Branches: refs/heads/master 742d347a9 -> 860b6737e
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/860b6737 Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/860b6737 Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/860b6737 Branch: refs/heads/master Commit: 860b6737e939c5ed0fa0744dfb1d7844b7395473 Parents: 742d347 Author: Brian Geffon <[email protected]> Authored: Mon Oct 6 22:03:04 2014 -0700 Committer: Brian Geffon <[email protected]> Committed: Mon Oct 6 22:03:04 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 ++++++++++ lib/tsconfig/TsConfigGrammar.c | 688 +++++++++++++++++------------------- lib/tsconfig/TsConfigGrammar.h | 41 +-- 7 files changed, 895 insertions(+), 880 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/860b6737/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/860b6737/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/860b6737/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/860b6737/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/860b6737/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_ */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/860b6737/lib/tsconfig/TsConfigGrammar.c ---------------------------------------------------------------------- diff --git a/lib/tsconfig/TsConfigGrammar.c b/lib/tsconfig/TsConfigGrammar.c index c24f1a9..042a146 100644 --- a/lib/tsconfig/TsConfigGrammar.c +++ b/lib/tsconfig/TsConfigGrammar.c @@ -1,8 +1,10 @@ -/* A Bison parser, made by GNU Bison 2.7. */ -/* Bison implementation for Yacc-like parsers in C +/* A Bison parser, made by GNU Bison 2.4.1. */ + +/* Skeleton implementation for Bison's Yacc-like parsers in C - Copyright (C) 1984, 1989-1990, 2000-2012 Free Software Foundation, Inc. + Copyright (C) 1984, 1989, 1990, 2000, 2001, 2002, 2003, 2004, 2005, 2006 + Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -44,7 +46,7 @@ #define YYBISON 1 /* Bison version. */ -#define YYBISON_VERSION "2.7" +#define YYBISON_VERSION "2.4.1" /* Skeleton name. */ #define YYSKELETON_NAME "yacc.c" @@ -58,8 +60,12 @@ /* Pull parsers. */ #define YYPULL 1 +/* Using locations. */ +#define YYLSP_NEEDED 0 + /* "%code top" blocks. */ -/* Line 349 of yacc.c */ + +/* Line 171 of yacc.c */ #line 26 "TsConfigGrammar.y" # if ! (defined(__clang_analyzer__) || defined(__COVERITY__)) @@ -79,9 +85,9 @@ extern int tsconfiglex(YYSTYPE* yylval, yyscan_t lexer); -/* Line 349 of yacc.c */ -#line 84 "TsConfigGrammar.c" +/* Line 171 of yacc.c */ +#line 91 "TsConfigGrammar.c" /* Substitute the variable and function names. */ #define yyparse tsconfigparse #define yylex tsconfiglex @@ -91,18 +97,17 @@ extern int tsconfiglex(YYSTYPE* yylval, yyscan_t lexer); #define yydebug tsconfigdebug #define yynerrs tsconfignerrs + /* Copy the first part of user declarations. */ -/* Line 371 of yacc.c */ -#line 98 "TsConfigGrammar.c" -# ifndef YY_NULL -# if defined __cplusplus && 201103L <= __cplusplus -# define YY_NULL nullptr -# else -# define YY_NULL 0 -# endif -# endif +/* Line 189 of yacc.c */ +#line 106 "TsConfigGrammar.c" + +/* Enabling traces. */ +#ifndef YYDEBUG +# define YYDEBUG 0 +#endif /* Enabling verbose error messages. */ #ifdef YYERROR_VERBOSE @@ -112,19 +117,14 @@ extern int tsconfiglex(YYSTYPE* yylval, yyscan_t lexer); # define YYERROR_VERBOSE 1 #endif -/* In a future release of Bison, this section will be replaced - by #include "y.tab.h". */ -#ifndef YY_TSCONFIG_TSCONFIGGRAMMAR_H_INCLUDED -# define YY_TSCONFIG_TSCONFIGGRAMMAR_H_INCLUDED -/* Enabling traces. */ -#ifndef YYDEBUG -# define YYDEBUG 0 -#endif -#if YYDEBUG -extern int tsconfigdebug; +/* Enabling the token table. */ +#ifndef YYTOKEN_TABLE +# define YYTOKEN_TABLE 0 #endif + /* "%code requires" blocks. */ -/* Line 387 of yacc.c */ + +/* Line 209 of yacc.c */ #line 1 "TsConfigGrammar.y" /** @file @@ -151,8 +151,9 @@ extern int tsconfigdebug; */ -/* Line 387 of yacc.c */ -#line 156 "TsConfigGrammar.c" + +/* Line 209 of yacc.c */ +#line 157 "TsConfigGrammar.c" /* Tokens. */ #ifndef YYTOKENTYPE @@ -190,6 +191,7 @@ extern int tsconfigdebug; + #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED typedef int YYSTYPE; # define YYSTYPE_IS_TRIVIAL 1 @@ -198,28 +200,14 @@ typedef int YYSTYPE; #endif -#ifdef YYPARSE_PARAM -#if defined __STDC__ || defined __cplusplus -int tsconfigparse (void *YYPARSE_PARAM); -#else -int tsconfigparse (); -#endif -#else /* ! YYPARSE_PARAM */ -#if defined __STDC__ || defined __cplusplus -int tsconfigparse (yyscan_t lexer, struct TsConfigHandlers* handlers); -#else -int tsconfigparse (); -#endif -#endif /* ! YYPARSE_PARAM */ - -#endif /* !YY_TSCONFIG_TSCONFIGGRAMMAR_H_INCLUDED */ - /* Copy the second part of user declarations. */ -/* Line 390 of yacc.c */ -#line 221 "TsConfigGrammar.c" + +/* Line 264 of yacc.c */ +#line 208 "TsConfigGrammar.c" /* Unqualified %code blocks. */ -/* Line 391 of yacc.c */ + +/* Line 265 of yacc.c */ #line 44 "TsConfigGrammar.y" @@ -242,8 +230,9 @@ int tsconfigerror( -/* Line 391 of yacc.c */ -#line 247 "TsConfigGrammar.c" + +/* Line 265 of yacc.c */ +#line 236 "TsConfigGrammar.c" #ifdef short # undef short @@ -293,27 +282,27 @@ typedef short int yytype_int16; #define YYSIZE_MAXIMUM ((YYSIZE_T) -1) #ifndef YY_ -# if defined YYENABLE_NLS && YYENABLE_NLS +# if YYENABLE_NLS # if ENABLE_NLS # include <libintl.h> /* INFRINGES ON USER NAME SPACE */ -# define YY_(Msgid) dgettext ("bison-runtime", Msgid) +# define YY_(msgid) dgettext ("bison-runtime", msgid) # endif # endif # ifndef YY_ -# define YY_(Msgid) Msgid +# define YY_(msgid) msgid # endif #endif /* Suppress unused-variable warnings by "using" E. */ #if ! defined lint || defined __GNUC__ -# define YYUSE(E) ((void) (E)) +# define YYUSE(e) ((void) (e)) #else -# define YYUSE(E) /* empty */ +# define YYUSE(e) /* empty */ #endif /* Identity function, used to suppress warnings about constant conditions. */ #ifndef lint -# define YYID(N) (N) +# define YYID(n) (n) #else #if (defined __STDC__ || defined __C99__FUNC__ \ || defined __cplusplus || defined _MSC_VER) @@ -346,12 +335,11 @@ YYID (yyi) # define alloca _alloca # else # define YYSTACK_ALLOC alloca -# if ! defined _ALLOCA_H && ! defined EXIT_SUCCESS && (defined __STDC__ || defined __C99__FUNC__ \ +# if ! defined _ALLOCA_H && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \ || defined __cplusplus || defined _MSC_VER) # include <stdlib.h> /* INFRINGES ON USER NAME SPACE */ - /* Use EXIT_SUCCESS as a witness for stdlib.h. */ -# ifndef EXIT_SUCCESS -# define EXIT_SUCCESS 0 +# ifndef _STDLIB_H +# define _STDLIB_H 1 # endif # endif # endif @@ -374,24 +362,24 @@ YYID (yyi) # ifndef YYSTACK_ALLOC_MAXIMUM # define YYSTACK_ALLOC_MAXIMUM YYSIZE_MAXIMUM # endif -# if (defined __cplusplus && ! defined EXIT_SUCCESS \ +# if (defined __cplusplus && ! defined _STDLIB_H \ && ! ((defined YYMALLOC || defined malloc) \ && (defined YYFREE || defined free))) # include <stdlib.h> /* INFRINGES ON USER NAME SPACE */ -# ifndef EXIT_SUCCESS -# define EXIT_SUCCESS 0 +# ifndef _STDLIB_H +# define _STDLIB_H 1 # endif # endif # ifndef YYMALLOC # define YYMALLOC malloc -# if ! defined malloc && ! defined EXIT_SUCCESS && (defined __STDC__ || defined __C99__FUNC__ \ +# if ! defined malloc && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \ || defined __cplusplus || defined _MSC_VER) void *malloc (YYSIZE_T); /* INFRINGES ON USER NAME SPACE */ # endif # endif # ifndef YYFREE # define YYFREE free -# if ! defined free && ! defined EXIT_SUCCESS && (defined __STDC__ || defined __C99__FUNC__ \ +# if ! defined free && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \ || defined __cplusplus || defined _MSC_VER) void free (void *); /* INFRINGES ON USER NAME SPACE */ # endif @@ -420,7 +408,23 @@ union yyalloc ((N) * (sizeof (yytype_int16) + sizeof (YYSTYPE)) \ + YYSTACK_GAP_MAXIMUM) -# define YYCOPY_NEEDED 1 +/* Copy COUNT objects from FROM to TO. The source and destination do + not overlap. */ +# ifndef YYCOPY +# if defined __GNUC__ && 1 < __GNUC__ +# define YYCOPY(To, From, Count) \ + __builtin_memcpy (To, From, (Count) * sizeof (*(From))) +# else +# define YYCOPY(To, From, Count) \ + do \ + { \ + YYSIZE_T yyi; \ + for (yyi = 0; yyi < (Count); yyi++) \ + (To)[yyi] = (From)[yyi]; \ + } \ + while (YYID (0)) +# endif +# endif /* Relocate STACK from its old location to the new one. The local variables YYSIZE and YYSTACKSIZE give the old and new number of @@ -440,26 +444,6 @@ union yyalloc #endif -#if defined YYCOPY_NEEDED && YYCOPY_NEEDED -/* Copy COUNT objects from SRC to DST. The source and destination do - not overlap. */ -# ifndef YYCOPY -# if defined __GNUC__ && 1 < __GNUC__ -# define YYCOPY(Dst, Src, Count) \ - __builtin_memcpy (Dst, Src, (Count) * sizeof (*(Src))) -# else -# define YYCOPY(Dst, Src, Count) \ - do \ - { \ - YYSIZE_T yyi; \ - for (yyi = 0; yyi < (Count); yyi++) \ - (Dst)[yyi] = (Src)[yyi]; \ - } \ - while (YYID (0)) -# endif -# endif -#endif /* !YYCOPY_NEEDED */ - /* YYFINAL -- State number of the termination state. */ #define YYFINAL 3 /* YYLAST -- Last index in YYTABLE. */ @@ -547,7 +531,7 @@ static const yytype_uint8 yyrline[] = }; #endif -#if YYDEBUG || YYERROR_VERBOSE || 1 +#if YYDEBUG || YYERROR_VERBOSE || YYTOKEN_TABLE /* YYTNAME[SYMBOL-NUM] -- String name of the symbol SYMBOL-NUM. First, the terminals, then, starting at YYNTOKENS, nonterminals. */ static const char *const yytname[] = @@ -558,7 +542,7 @@ static const char *const yytname[] = "config", "group", "group_open", "group_close", "group_items", "assign", "$@1", "list", "list_open", "list_close", "list_items", "value", "literal", "separator", "path", "path_open", "path_close", "path_item", - "path_tag", YY_NULL + "path_tag", 0 }; #endif @@ -590,8 +574,8 @@ static const yytype_uint8 yyr2[] = 3, 1, 1 }; -/* YYDEFACT[STATE-NAME] -- Default reduction number in state STATE-NUM. - Performed when YYTABLE doesn't specify something else to do. Zero +/* YYDEFACT[STATE-NAME] -- Default rule to reduce with in state + STATE-NUM when YYTABLE doesn't specify something else to do. Zero means the default is an error. */ static const yytype_uint8 yydefact[] = { @@ -630,7 +614,8 @@ static const yytype_int8 yypgoto[] = /* YYTABLE[YYPACT[STATE-NUM]]. What to do in state STATE-NUM. If positive, shift that token. If negative, reduce the rule which - number is the opposite. If YYTABLE_NINF, syntax error. */ + number is the opposite. If zero, do what YYDEFACT says. + If YYTABLE_NINF, syntax error. */ #define YYTABLE_NINF -3 static const yytype_int8 yytable[] = { @@ -640,12 +625,6 @@ static const yytype_int8 yytable[] = 26, 42, 0, 37 }; -#define yypact_value_is_default(Yystate) \ - (!!((Yystate) == (-11))) - -#define yytable_value_is_error(Yytable_value) \ - YYID (0) - static const yytype_int8 yycheck[] = { 6, 1, 0, 3, 4, 5, 6, 7, 8, 1, @@ -677,50 +656,78 @@ static const yytype_uint8 yystos[] = /* Like YYERROR except do call yyerror. This remains here temporarily to ease the transition to the new meaning of YYERROR, for GCC. - Once GCC version 2 has supplanted version 1, this can go. However, - YYFAIL appears to be in use. Nevertheless, it is formally deprecated - in Bison 2.4.2's NEWS entry, where a plan to phase it out is - discussed. */ + Once GCC version 2 has supplanted version 1, this can go. */ #define YYFAIL goto yyerrlab -#if defined YYFAIL - /* This is here to suppress warnings from the GCC cpp's - -Wunused-macros. Normally we don't worry about that warning, but - some users do, and we want to make it easy for users to remove - YYFAIL uses, which will produce warnings from Bison 2.5. */ -#endif #define YYRECOVERING() (!!yyerrstatus) -#define YYBACKUP(Token, Value) \ -do \ - if (yychar == YYEMPTY) \ - { \ - yychar = (Token); \ - yylval = (Value); \ - YYPOPSTACK (yylen); \ - yystate = *yyssp; \ - goto yybackup; \ - } \ - else \ - { \ +#define YYBACKUP(Token, Value) \ +do \ + if (yychar == YYEMPTY && yylen == 1) \ + { \ + yychar = (Token); \ + yylval = (Value); \ + yytoken = YYTRANSLATE (yychar); \ + YYPOPSTACK (1); \ + goto yybackup; \ + } \ + else \ + { \ yyerror (lexer, handlers, YY_("syntax error: cannot back up")); \ YYERROR; \ } \ while (YYID (0)) -/* Error token number */ + #define YYTERROR 1 #define YYERRCODE 256 -/* This macro is provided for backward compatibility. */ +/* YYLLOC_DEFAULT -- Set CURRENT to span from RHS[1] to RHS[N]. + If N is 0, then set CURRENT to the empty location which ends + the previous symbol: RHS[0] (always defined). */ + +#define YYRHSLOC(Rhs, K) ((Rhs)[K]) +#ifndef YYLLOC_DEFAULT +# define YYLLOC_DEFAULT(Current, Rhs, N) \ + do \ + if (YYID (N)) \ + { \ + (Current).first_line = YYRHSLOC (Rhs, 1).first_line; \ + (Current).first_column = YYRHSLOC (Rhs, 1).first_column; \ + (Current).last_line = YYRHSLOC (Rhs, N).last_line; \ + (Current).last_column = YYRHSLOC (Rhs, N).last_column; \ + } \ + else \ + { \ + (Current).first_line = (Current).last_line = \ + YYRHSLOC (Rhs, 0).last_line; \ + (Current).first_column = (Current).last_column = \ + YYRHSLOC (Rhs, 0).last_column; \ + } \ + while (YYID (0)) +#endif + + +/* YY_LOCATION_PRINT -- Print the location on the stream. + This macro was not mandated originally: define only if we know + we won't break user code: when these are the locations we know. */ + #ifndef YY_LOCATION_PRINT -# define YY_LOCATION_PRINT(File, Loc) ((void) 0) +# if YYLTYPE_IS_TRIVIAL +# define YY_LOCATION_PRINT(File, Loc) \ + fprintf (File, "%d.%d-%d.%d", \ + (Loc).first_line, (Loc).first_column, \ + (Loc).last_line, (Loc).last_column) +# else +# define YY_LOCATION_PRINT(File, Loc) ((void) 0) +# endif #endif /* YYLEX -- calling `yylex' with the right arguments. */ + #ifdef YYLEX_PARAM # define YYLEX yylex (&yylval, YYLEX_PARAM) #else @@ -772,8 +779,6 @@ yy_symbol_value_print (yyoutput, yytype, yyvaluep, lexer, handlers) struct TsConfigHandlers* handlers; #endif { - FILE *yyo = yyoutput; - YYUSE (yyo); if (!yyvaluep) return; YYUSE (lexer); @@ -787,7 +792,7 @@ yy_symbol_value_print (yyoutput, yytype, yyvaluep, lexer, handlers) switch (yytype) { default: - break; + break; } } @@ -917,6 +922,7 @@ int yydebug; # define YYMAXDEPTH 10000 #endif + #if YYERROR_VERBOSE @@ -1019,145 +1025,115 @@ yytnamerr (char *yyres, const char *yystr) } # endif -/* Copy into *YYMSG, which is of size *YYMSG_ALLOC, an error message - about the unexpected token YYTOKEN for the state stack whose top is - YYSSP. - - Return 0 if *YYMSG was successfully written. Return 1 if *YYMSG is - not large enough to hold the message. In that case, also set - *YYMSG_ALLOC to the required number of bytes. Return 2 if the - required number of bytes is too large to store. */ -static int -yysyntax_error (YYSIZE_T *yymsg_alloc, char **yymsg, - yytype_int16 *yyssp, int yytoken) +/* Copy into YYRESULT an error message about the unexpected token + YYCHAR while in state YYSTATE. Return the number of bytes copied, + including the terminating null byte. If YYRESULT is null, do not + copy anything; just return the number of bytes that would be + copied. As a special case, return 0 if an ordinary "syntax error" + message will do. Return YYSIZE_MAXIMUM if overflow occurs during + size calculation. */ +static YYSIZE_T +yysyntax_error (char *yyresult, int yystate, int yychar) { - YYSIZE_T yysize0 = yytnamerr (YY_NULL, yytname[yytoken]); - YYSIZE_T yysize = yysize0; - enum { YYERROR_VERBOSE_ARGS_MAXIMUM = 5 }; - /* Internationalized format string. */ - const char *yyformat = YY_NULL; - /* Arguments of yyformat. */ - char const *yyarg[YYERROR_VERBOSE_ARGS_MAXIMUM]; - /* Number of reported tokens (one for the "unexpected", one per - "expected"). */ - int yycount = 0; - - /* There are many possibilities here to consider: - - Assume YYFAIL is not used. It's too flawed to consider. See - <http://lists.gnu.org/archive/html/bison-patches/2009-12/msg00024.html> - for details. YYERROR is fine as it does not invoke this - function. - - If this state is a consistent state with a default action, then - the only way this function was invoked is if the default action - is an error action. In that case, don't check for expected - tokens because there are none. - - The only way there can be no lookahead present (in yychar) is if - this state is a consistent state with a default action. Thus, - detecting the absence of a lookahead is sufficient to determine - that there is no unexpected or expected token to report. In that - case, just report a simple "syntax error". - - Don't assume there isn't a lookahead just because this state is a - consistent state with a default action. There might have been a - previous inconsistent state, consistent state with a non-default - action, or user semantic action that manipulated yychar. - - Of course, the expected token list depends on states to have - correct lookahead information, and it depends on the parser not - to perform extra reductions after fetching a lookahead from the - scanner and before detecting a syntax error. Thus, state merging - (from LALR or IELR) and default reductions corrupt the expected - token list. However, the list is correct for canonical LR with - one exception: it will still contain any token that will not be - accepted due to an error action in a later state. - */ - if (yytoken != YYEMPTY) - { - int yyn = yypact[*yyssp]; - yyarg[yycount++] = yytname[yytoken]; - if (!yypact_value_is_default (yyn)) - { - /* Start YYX at -YYN if negative to avoid negative indexes in - YYCHECK. In other words, skip the first -YYN actions for - this state because they are default actions. */ - int yyxbegin = yyn < 0 ? -yyn : 0; - /* Stay within bounds of both yycheck and yytname. */ - int yychecklim = YYLAST - yyn + 1; - int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS; - int yyx; - - for (yyx = yyxbegin; yyx < yyxend; ++yyx) - if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR - && !yytable_value_is_error (yytable[yyx + yyn])) - { - if (yycount == YYERROR_VERBOSE_ARGS_MAXIMUM) - { - yycount = 1; - yysize = yysize0; - break; - } - yyarg[yycount++] = yytname[yyx]; - { - YYSIZE_T yysize1 = yysize + yytnamerr (YY_NULL, yytname[yyx]); - if (! (yysize <= yysize1 - && yysize1 <= YYSTACK_ALLOC_MAXIMUM)) - return 2; - yysize = yysize1; - } - } - } - } + int yyn = yypact[yystate]; - switch (yycount) + if (! (YYPACT_NINF < yyn && yyn <= YYLAST)) + return 0; + else { -# define YYCASE_(N, S) \ - case N: \ - yyformat = S; \ - break - YYCASE_(0, YY_("syntax error")); - YYCASE_(1, YY_("syntax error, unexpected %s")); - YYCASE_(2, YY_("syntax error, unexpected %s, expecting %s")); - YYCASE_(3, YY_("syntax error, unexpected %s, expecting %s or %s")); - YYCASE_(4, YY_("syntax error, unexpected %s, expecting %s or %s or %s")); - YYCASE_(5, YY_("syntax error, unexpected %s, expecting %s or %s or %s or %s")); -# undef YYCASE_ - } + int yytype = YYTRANSLATE (yychar); + YYSIZE_T yysize0 = yytnamerr (0, yytname[yytype]); + YYSIZE_T yysize = yysize0; + YYSIZE_T yysize1; + int yysize_overflow = 0; + enum { YYERROR_VERBOSE_ARGS_MAXIMUM = 5 }; + char const *yyarg[YYERROR_VERBOSE_ARGS_MAXIMUM]; + int yyx; + +# if 0 + /* This is so xgettext sees the translatable formats that are + constructed on the fly. */ + YY_("syntax error, unexpected %s"); + YY_("syntax error, unexpected %s, expecting %s"); + YY_("syntax error, unexpected %s, expecting %s or %s"); + YY_("syntax error, unexpected %s, expecting %s or %s or %s"); + YY_("syntax error, unexpected %s, expecting %s or %s or %s or %s"); +# endif + char *yyfmt; + char const *yyf; + static char const yyunexpected[] = "syntax error, unexpected %s"; + static char const yyexpecting[] = ", expecting %s"; + static char const yyor[] = " or %s"; + char yyformat[sizeof yyunexpected + + sizeof yyexpecting - 1 + + ((YYERROR_VERBOSE_ARGS_MAXIMUM - 2) + * (sizeof yyor - 1))]; + char const *yyprefix = yyexpecting; + + /* Start YYX at -YYN if negative to avoid negative indexes in + YYCHECK. */ + int yyxbegin = yyn < 0 ? -yyn : 0; + + /* Stay within bounds of both yycheck and yytname. */ + int yychecklim = YYLAST - yyn + 1; + int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS; + int yycount = 1; + + yyarg[0] = yytname[yytype]; + yyfmt = yystpcpy (yyformat, yyunexpected); + + for (yyx = yyxbegin; yyx < yyxend; ++yyx) + if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR) + { + if (yycount == YYERROR_VERBOSE_ARGS_MAXIMUM) + { + yycount = 1; + yysize = yysize0; + yyformat[sizeof yyunexpected - 1] = '\0'; + break; + } + yyarg[yycount++] = yytname[yyx]; + yysize1 = yysize + yytnamerr (0, yytname[yyx]); + yysize_overflow |= (yysize1 < yysize); + yysize = yysize1; + yyfmt = yystpcpy (yyfmt, yyprefix); + yyprefix = yyor; + } - { - YYSIZE_T yysize1 = yysize + yystrlen (yyformat); - if (! (yysize <= yysize1 && yysize1 <= YYSTACK_ALLOC_MAXIMUM)) - return 2; - yysize = yysize1; - } + yyf = YY_(yyformat); + yysize1 = yysize + yystrlen (yyf); + yysize_overflow |= (yysize1 < yysize); + yysize = yysize1; - if (*yymsg_alloc < yysize) - { - *yymsg_alloc = 2 * yysize; - if (! (yysize <= *yymsg_alloc - && *yymsg_alloc <= YYSTACK_ALLOC_MAXIMUM)) - *yymsg_alloc = YYSTACK_ALLOC_MAXIMUM; - return 1; - } + if (yysize_overflow) + return YYSIZE_MAXIMUM; - /* Avoid sprintf, as that infringes on the user's name space. - Don't have undefined behavior even if the translation - produced a string with the wrong number of "%s"s. */ - { - char *yyp = *yymsg; - int yyi = 0; - while ((*yyp = *yyformat) != '\0') - if (*yyp == '%' && yyformat[1] == 's' && yyi < yycount) - { - yyp += yytnamerr (yyp, yyarg[yyi++]); - yyformat += 2; - } - else - { - yyp++; - yyformat++; - } - } - return 0; + if (yyresult) + { + /* Avoid sprintf, as that infringes on the user's name space. + Don't have undefined behavior even if the translation + produced a string with the wrong number of "%s"s. */ + char *yyp = yyresult; + int yyi = 0; + while ((*yyp = *yyf) != '\0') + { + if (*yyp == '%' && yyf[1] == 's' && yyi < yycount) + { + yyp += yytnamerr (yyp, yyarg[yyi++]); + yyf += 2; + } + else + { + yyp++; + yyf++; + } + } + } + return yysize; + } } #endif /* YYERROR_VERBOSE */ + /*-----------------------------------------------. | Release the memory associated to this symbol. | @@ -1190,16 +1166,32 @@ yydestruct (yymsg, yytype, yyvaluep, lexer, handlers) { default: - break; + break; } } +/* Prevent warnings from -Wmissing-prototypes. */ +#ifdef YYPARSE_PARAM +#if defined __STDC__ || defined __cplusplus +int yyparse (void *YYPARSE_PARAM); +#else +int yyparse (); +#endif +#else /* ! YYPARSE_PARAM */ +#if defined __STDC__ || defined __cplusplus +int yyparse (yyscan_t lexer, struct TsConfigHandlers* handlers); +#else +int yyparse (); +#endif +#endif /* ! YYPARSE_PARAM */ + + -/*----------. -| yyparse. | -`----------*/ +/*-------------------------. +| yyparse or yypush_parse. | +`-------------------------*/ #ifdef YYPARSE_PARAM #if (defined __STDC__ || defined __C99__FUNC__ \ @@ -1227,31 +1219,8 @@ yyparse (lexer, handlers) /* The lookahead symbol. */ int yychar; - -#if defined __GNUC__ && 407 <= __GNUC__ * 100 + __GNUC_MINOR__ -/* Suppress an incorrect diagnostic about yylval being uninitialized. */ -# define YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN \ - _Pragma ("GCC diagnostic push") \ - _Pragma ("GCC diagnostic ignored \"-Wuninitialized\"")\ - _Pragma ("GCC diagnostic ignored \"-Wmaybe-uninitialized\"") -# define YY_IGNORE_MAYBE_UNINITIALIZED_END \ - _Pragma ("GCC diagnostic pop") -#else -/* Default value used for initialization, for pacifying older GCCs - or non-GCC compilers. */ -static YYSTYPE yyval_default; -# define YY_INITIAL_VALUE(Value) = Value -#endif -#ifndef YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN -# define YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN -# define YY_IGNORE_MAYBE_UNINITIALIZED_END -#endif -#ifndef YY_INITIAL_VALUE -# define YY_INITIAL_VALUE(Value) /* Nothing. */ -#endif - /* The semantic value of the lookahead symbol. */ -YYSTYPE yylval YY_INITIAL_VALUE(yyval_default); +YYSTYPE yylval; /* Number of syntax errors so far. */ int yynerrs; @@ -1264,7 +1233,7 @@ YYSTYPE yylval YY_INITIAL_VALUE(yyval_default); `yyss': related to states. `yyvs': related to semantic values. - Refer to the stacks through separate pointers, to allow yyoverflow + Refer to the stacks thru separate pointers, to allow yyoverflow to reallocate them elsewhere. */ /* The state stack. */ @@ -1282,7 +1251,7 @@ YYSTYPE yylval YY_INITIAL_VALUE(yyval_default); int yyn; int yyresult; /* Lookahead token as an internal (translated) token number. */ - int yytoken = 0; + int yytoken; /* The variables used to return semantic value and location from the action routines. */ YYSTYPE yyval; @@ -1300,8 +1269,9 @@ YYSTYPE yylval YY_INITIAL_VALUE(yyval_default); Keep to zero when no symbol should be popped. */ int yylen = 0; - yyssp = yyss = yyssa; - yyvsp = yyvs = yyvsa; + yytoken = 0; + yyss = yyssa; + yyvs = yyvsa; yystacksize = YYINITDEPTH; YYDPRINTF ((stderr, "Starting parse\n")); @@ -1310,6 +1280,14 @@ YYSTYPE yylval YY_INITIAL_VALUE(yyval_default); yyerrstatus = 0; yynerrs = 0; yychar = YYEMPTY; /* Cause a token to be read. */ + + /* Initialize stack pointers. + Waste one element of value and location stack + so that they stay on the same level as the state stack. + The wasted elements are never initialized. */ + yyssp = yyss; + yyvsp = yyvs; + goto yysetstate; /*------------------------------------------------------------. @@ -1401,7 +1379,7 @@ yybackup: /* First try to decide what to do without reference to lookahead token. */ yyn = yypact[yystate]; - if (yypact_value_is_default (yyn)) + if (yyn == YYPACT_NINF) goto yydefault; /* Not known => get a lookahead token if don't already have one. */ @@ -1432,8 +1410,8 @@ yybackup: yyn = yytable[yyn]; if (yyn <= 0) { - if (yytable_value_is_error (yyn)) - goto yyerrlab; + if (yyn == 0 || yyn == YYTABLE_NINF) + goto yyerrlab; yyn = -yyn; goto yyreduce; } @@ -1450,9 +1428,7 @@ yybackup: yychar = YYEMPTY; yystate = yyn; - YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN *++yyvsp = yylval; - YY_IGNORE_MAYBE_UNINITIALIZED_END goto yynewstate; @@ -1489,81 +1465,81 @@ yyreduce: switch (yyn) { case 4: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 90 "TsConfigGrammar.y" { HANDLE_EVENT(GroupOpen, (yyvsp[(1) - (1)])); } break; case 5: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 92 "TsConfigGrammar.y" { HANDLE_EVENT(GroupClose, (yyvsp[(1) - (1)])); } break; case 9: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 96 "TsConfigGrammar.y" { HANDLE_EVENT(GroupName, (yyvsp[(1) - (2)])); } break; case 12: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 100 "TsConfigGrammar.y" { HANDLE_EVENT(ListOpen, (yyvsp[(1) - (1)])); } break; case 13: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 102 "TsConfigGrammar.y" { HANDLE_EVENT(ListClose, (yyvsp[(1) - (1)])); } break; case 17: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 106 "TsConfigGrammar.y" { HANDLE_EVENT(LiteralValue, (yyvsp[(1) - (1)])); } break; case 27: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 114 "TsConfigGrammar.y" { HANDLE_EVENT(PathOpen, (yyvsp[(1) - (1)])); } break; case 28: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 116 "TsConfigGrammar.y" { HANDLE_EVENT(PathClose, (yyvsp[(1) - (1)])); } break; case 31: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 120 "TsConfigGrammar.y" { HANDLE_EVENT(PathTag, (yyvsp[(1) - (1)])); } break; case 32: -/* Line 1792 of yacc.c */ + +/* Line 1455 of yacc.c */ #line 120 "TsConfigGrammar.y" { HANDLE_EVENT(PathIndex, (yyvsp[(1) - (1)])); } break; -/* Line 1792 of yacc.c */ -#line 1554 "TsConfigGrammar.c" + +/* Line 1455 of yacc.c */ +#line 1541 "TsConfigGrammar.c" default: break; } - /* User semantic actions sometimes alter yychar, and that requires - that yytoken be updated with the new translation. We take the - approach of translating immediately before every use of yytoken. - One alternative is translating here after every semantic action, - but that translation would be missed if the semantic action invokes - YYABORT, YYACCEPT, or YYERROR immediately after altering yychar or - if it invokes YYBACKUP. In the case of YYABORT or YYACCEPT, an - incorrect destructor might then be invoked immediately. In the - case of YYERROR or YYBACKUP, subsequent parser actions might lead - to an incorrect destructor call or verbose syntax error message - before the lookahead is translated. */ YY_SYMBOL_PRINT ("-> $$ =", yyr1[yyn], &yyval, &yyloc); YYPOPSTACK (yylen); @@ -1591,10 +1567,6 @@ yyreduce: | yyerrlab -- here on detecting error | `------------------------------------*/ yyerrlab: - /* Make sure we have latest lookahead translation. See comments at - user semantic actions for why this is necessary. */ - yytoken = yychar == YYEMPTY ? YYEMPTY : YYTRANSLATE (yychar); - /* If not already recovering from an error, report this error. */ if (!yyerrstatus) { @@ -1602,36 +1574,37 @@ yyerrlab: #if ! YYERROR_VERBOSE yyerror (lexer, handlers, YY_("syntax error")); #else -# define YYSYNTAX_ERROR yysyntax_error (&yymsg_alloc, &yymsg, \ - yyssp, yytoken) { - char const *yymsgp = YY_("syntax error"); - int yysyntax_error_status; - yysyntax_error_status = YYSYNTAX_ERROR; - if (yysyntax_error_status == 0) - yymsgp = yymsg; - else if (yysyntax_error_status == 1) - { - if (yymsg != yymsgbuf) - YYSTACK_FREE (yymsg); - yymsg = (char *) YYSTACK_ALLOC (yymsg_alloc); - if (!yymsg) - { - yymsg = yymsgbuf; - yymsg_alloc = sizeof yymsgbuf; - yysyntax_error_status = 2; - } - else - { - yysyntax_error_status = YYSYNTAX_ERROR; - yymsgp = yymsg; - } - } - yyerror (lexer, handlers, yymsgp); - if (yysyntax_error_status == 2) - goto yyexhaustedlab; + YYSIZE_T yysize = yysyntax_error (0, yystate, yychar); + if (yymsg_alloc < yysize && yymsg_alloc < YYSTACK_ALLOC_MAXIMUM) + { + YYSIZE_T yyalloc = 2 * yysize; + if (! (yysize <= yyalloc && yyalloc <= YYSTACK_ALLOC_MAXIMUM)) + yyalloc = YYSTACK_ALLOC_MAXIMUM; + if (yymsg != yymsgbuf) + YYSTACK_FREE (yymsg); + yymsg = (char *) YYSTACK_ALLOC (yyalloc); + if (yymsg) + yymsg_alloc = yyalloc; + else + { + yymsg = yymsgbuf; + yymsg_alloc = sizeof yymsgbuf; + } + } + + if (0 < yysize && yysize <= yymsg_alloc) + { + (void) yysyntax_error (yymsg, yystate, yychar); + yyerror (lexer, handlers, yymsg); + } + else + { + yyerror (lexer, handlers, YY_("syntax error")); + if (yysize != 0) + goto yyexhaustedlab; + } } -# undef YYSYNTAX_ERROR #endif } @@ -1690,7 +1663,7 @@ yyerrlab1: for (;;) { yyn = yypact[yystate]; - if (!yypact_value_is_default (yyn)) + if (yyn != YYPACT_NINF) { yyn += YYTERROR; if (0 <= yyn && yyn <= YYLAST && yycheck[yyn] == YYTERROR) @@ -1713,9 +1686,7 @@ yyerrlab1: YY_STACK_PRINT (yyss, yyssp); } - YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN *++yyvsp = yylval; - YY_IGNORE_MAYBE_UNINITIALIZED_END /* Shift the error token. */ @@ -1739,7 +1710,7 @@ yyabortlab: yyresult = 1; goto yyreturn; -#if !defined yyoverflow || YYERROR_VERBOSE +#if !defined(yyoverflow) || YYERROR_VERBOSE /*-------------------------------------------------. | yyexhaustedlab -- memory exhaustion comes here. | `-------------------------------------------------*/ @@ -1751,13 +1722,8 @@ yyexhaustedlab: yyreturn: if (yychar != YYEMPTY) - { - /* Make sure we have latest lookahead translation. See comments at - user semantic actions for why this is necessary. */ - yytoken = YYTRANSLATE (yychar); - yydestruct ("Cleanup: discarding lookahead", - yytoken, &yylval, lexer, handlers); - } + yydestruct ("Cleanup: discarding lookahead", + yytoken, &yylval, lexer, handlers); /* Do not reclaim the symbols of the rule which action triggered this YYABORT or YYACCEPT. */ YYPOPSTACK (yylen); @@ -1781,8 +1747,10 @@ yyreturn: } -/* Line 2055 of yacc.c */ + +/* Line 1675 of yacc.c */ #line 122 "TsConfigGrammar.y" # endif // __clang_analyzer__ + http://git-wip-us.apache.org/repos/asf/trafficserver/blob/860b6737/lib/tsconfig/TsConfigGrammar.h ---------------------------------------------------------------------- diff --git a/lib/tsconfig/TsConfigGrammar.h b/lib/tsconfig/TsConfigGrammar.h index 1700ea1..d3581d9 100644 --- a/lib/tsconfig/TsConfigGrammar.h +++ b/lib/tsconfig/TsConfigGrammar.h @@ -1,8 +1,10 @@ -/* A Bison parser, made by GNU Bison 2.7. */ -/* Bison interface for Yacc-like parsers in C +/* A Bison parser, made by GNU Bison 2.4.1. */ + +/* Skeleton interface for Bison's Yacc-like parsers in C - Copyright (C) 1984, 1989-1990, 2000-2012 Free Software Foundation, Inc. + Copyright (C) 1984, 1989, 1990, 2000, 2001, 2002, 2003, 2004, 2005, 2006 + Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -30,17 +32,9 @@ This special exception was added by the Free Software Foundation in version 2.2 of Bison. */ -#ifndef YY_TSCONFIG_TSCONFIGGRAMMAR_H_INCLUDED -# define YY_TSCONFIG_TSCONFIGGRAMMAR_H_INCLUDED -/* Enabling traces. */ -#ifndef YYDEBUG -# define YYDEBUG 0 -#endif -#if YYDEBUG -extern int tsconfigdebug; -#endif /* "%code requires" blocks. */ -/* Line 2058 of yacc.c */ + +/* Line 1676 of yacc.c */ #line 1 "TsConfigGrammar.y" /** @file @@ -67,8 +61,9 @@ extern int tsconfigdebug; */ -/* Line 2058 of yacc.c */ -#line 72 "TsConfigGrammar.h" + +/* Line 1676 of yacc.c */ +#line 67 "TsConfigGrammar.h" /* Tokens. */ #ifndef YYTOKENTYPE @@ -106,6 +101,7 @@ extern int tsconfigdebug; + #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED typedef int YYSTYPE; # define YYSTYPE_IS_TRIVIAL 1 @@ -114,18 +110,5 @@ typedef int YYSTYPE; #endif -#ifdef YYPARSE_PARAM -#if defined __STDC__ || defined __cplusplus -int tsconfigparse (void *YYPARSE_PARAM); -#else -int tsconfigparse (); -#endif -#else /* ! YYPARSE_PARAM */ -#if defined __STDC__ || defined __cplusplus -int tsconfigparse (yyscan_t lexer, struct TsConfigHandlers* handlers); -#else -int tsconfigparse (); -#endif -#endif /* ! YYPARSE_PARAM */ -#endif /* !YY_TSCONFIG_TSCONFIGGRAMMAR_H_INCLUDED */ +
