Repository: trafficserver Updated Branches: refs/heads/master 860b6737e -> 5ee27f38d
Apparently we check in generated code now :( I should have caught this, I'll back it out then add this back in properly Revert "TS-3114: Refactor IpMap to make the RB tree a shared data structure" This reverts commit 860b6737e939c5ed0fa0744dfb1d7844b7395473. Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/5ee27f38 Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/5ee27f38 Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/5ee27f38 Branch: refs/heads/master Commit: 5ee27f38dd247a2429572e2902442e1116f4a3b8 Parents: 860b673 Author: Brian Geffon <[email protected]> Authored: Mon Oct 6 22:06:04 2014 -0700 Committer: Brian Geffon <[email protected]> Committed: Mon Oct 6 22:06: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, 880 insertions(+), 895 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5ee27f38/lib/ts/IpMap.cc ---------------------------------------------------------------------- diff --git a/lib/ts/IpMap.cc b/lib/ts/IpMap.cc index 4b879ff..9a9421a 100644 --- a/lib/ts/IpMap.cc +++ b/lib/ts/IpMap.cc @@ -97,6 +97,332 @@ 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/5ee27f38/lib/ts/IpMap.h ---------------------------------------------------------------------- diff --git a/lib/ts/IpMap.h b/lib/ts/IpMap.h index 7afb9a6..917158f 100644 --- a/lib/ts/IpMap.h +++ b/lib/ts/IpMap.h @@ -3,7 +3,6 @@ # 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> @@ -57,6 +56,170 @@ 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/5ee27f38/lib/ts/Makefile.am ---------------------------------------------------------------------- diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am index 00ff352..d1bcc89 100644 --- a/lib/ts/Makefile.am +++ b/lib/ts/Makefile.am @@ -177,9 +177,7 @@ libtsutil_la_SOURCES = \ ink_time.h \ libts.h \ llqueue.cc \ - lockfile.cc \ - RbTree.cc \ - RbTree.h + lockfile.cc #test_UNUSED_SOURCES = \ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5ee27f38/lib/ts/RbTree.cc ---------------------------------------------------------------------- diff --git a/lib/ts/RbTree.cc b/lib/ts/RbTree.cc deleted file mode 100644 index 926a063..0000000 --- a/lib/ts/RbTree.cc +++ /dev/null @@ -1,355 +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 "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/5ee27f38/lib/ts/RbTree.h ---------------------------------------------------------------------- diff --git a/lib/ts/RbTree.h b/lib/ts/RbTree.h deleted file mode 100644 index 8bf5f3e..0000000 --- a/lib/ts/RbTree.h +++ /dev/null @@ -1,196 +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. - */ - -#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/5ee27f38/lib/tsconfig/TsConfigGrammar.c ---------------------------------------------------------------------- diff --git a/lib/tsconfig/TsConfigGrammar.c b/lib/tsconfig/TsConfigGrammar.c index 042a146..c24f1a9 100644 --- a/lib/tsconfig/TsConfigGrammar.c +++ b/lib/tsconfig/TsConfigGrammar.c @@ -1,10 +1,8 @@ +/* A Bison parser, made by GNU Bison 2.7. */ -/* A Bison parser, made by GNU Bison 2.4.1. */ - -/* Skeleton implementation for Bison's Yacc-like parsers in C +/* Bison implementation for Yacc-like parsers in C - Copyright (C) 1984, 1989, 1990, 2000, 2001, 2002, 2003, 2004, 2005, 2006 - Free Software Foundation, Inc. + Copyright (C) 1984, 1989-1990, 2000-2012 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 @@ -46,7 +44,7 @@ #define YYBISON 1 /* Bison version. */ -#define YYBISON_VERSION "2.4.1" +#define YYBISON_VERSION "2.7" /* Skeleton name. */ #define YYSKELETON_NAME "yacc.c" @@ -60,12 +58,8 @@ /* Pull parsers. */ #define YYPULL 1 -/* Using locations. */ -#define YYLSP_NEEDED 0 - /* "%code top" blocks. */ - -/* Line 171 of yacc.c */ +/* Line 349 of yacc.c */ #line 26 "TsConfigGrammar.y" # if ! (defined(__clang_analyzer__) || defined(__COVERITY__)) @@ -85,9 +79,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 @@ -97,17 +91,18 @@ 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" -/* Line 189 of yacc.c */ -#line 106 "TsConfigGrammar.c" - -/* Enabling traces. */ -#ifndef YYDEBUG -# define YYDEBUG 0 -#endif +# ifndef YY_NULL +# if defined __cplusplus && 201103L <= __cplusplus +# define YY_NULL nullptr +# else +# define YY_NULL 0 +# endif +# endif /* Enabling verbose error messages. */ #ifdef YYERROR_VERBOSE @@ -117,14 +112,19 @@ extern int tsconfiglex(YYSTYPE* yylval, yyscan_t lexer); # define YYERROR_VERBOSE 1 #endif -/* Enabling the token table. */ -#ifndef YYTOKEN_TABLE -# define YYTOKEN_TABLE 0 +/* 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; #endif - /* "%code requires" blocks. */ - -/* Line 209 of yacc.c */ +/* Line 387 of yacc.c */ #line 1 "TsConfigGrammar.y" /** @file @@ -151,9 +151,8 @@ extern int tsconfiglex(YYSTYPE* yylval, yyscan_t lexer); */ - -/* Line 209 of yacc.c */ -#line 157 "TsConfigGrammar.c" +/* Line 387 of yacc.c */ +#line 156 "TsConfigGrammar.c" /* Tokens. */ #ifndef YYTOKENTYPE @@ -191,7 +190,6 @@ extern int tsconfiglex(YYSTYPE* yylval, yyscan_t lexer); - #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED typedef int YYSTYPE; # define YYSTYPE_IS_TRIVIAL 1 @@ -200,14 +198,28 @@ typedef int YYSTYPE; #endif -/* Copy the second part of user declarations. */ +#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 */ -/* Line 264 of yacc.c */ -#line 208 "TsConfigGrammar.c" -/* Unqualified %code blocks. */ +/* Copy the second part of user declarations. */ -/* Line 265 of yacc.c */ +/* Line 390 of yacc.c */ +#line 221 "TsConfigGrammar.c" +/* Unqualified %code blocks. */ +/* Line 391 of yacc.c */ #line 44 "TsConfigGrammar.y" @@ -230,9 +242,8 @@ int tsconfigerror( - -/* Line 265 of yacc.c */ -#line 236 "TsConfigGrammar.c" +/* Line 391 of yacc.c */ +#line 247 "TsConfigGrammar.c" #ifdef short # undef short @@ -282,27 +293,27 @@ typedef short int yytype_int16; #define YYSIZE_MAXIMUM ((YYSIZE_T) -1) #ifndef YY_ -# if YYENABLE_NLS +# if defined YYENABLE_NLS && 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) @@ -335,11 +346,12 @@ YYID (yyi) # define alloca _alloca # else # define YYSTACK_ALLOC alloca -# if ! defined _ALLOCA_H && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \ +# if ! defined _ALLOCA_H && ! defined EXIT_SUCCESS && (defined __STDC__ || defined __C99__FUNC__ \ || defined __cplusplus || defined _MSC_VER) # include <stdlib.h> /* INFRINGES ON USER NAME SPACE */ -# ifndef _STDLIB_H -# define _STDLIB_H 1 + /* Use EXIT_SUCCESS as a witness for stdlib.h. */ +# ifndef EXIT_SUCCESS +# define EXIT_SUCCESS 0 # endif # endif # endif @@ -362,24 +374,24 @@ YYID (yyi) # ifndef YYSTACK_ALLOC_MAXIMUM # define YYSTACK_ALLOC_MAXIMUM YYSIZE_MAXIMUM # endif -# if (defined __cplusplus && ! defined _STDLIB_H \ +# if (defined __cplusplus && ! defined EXIT_SUCCESS \ && ! ((defined YYMALLOC || defined malloc) \ && (defined YYFREE || defined free))) # include <stdlib.h> /* INFRINGES ON USER NAME SPACE */ -# ifndef _STDLIB_H -# define _STDLIB_H 1 +# ifndef EXIT_SUCCESS +# define EXIT_SUCCESS 0 # endif # endif # ifndef YYMALLOC # define YYMALLOC malloc -# if ! defined malloc && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \ +# if ! defined malloc && ! defined EXIT_SUCCESS && (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 _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \ +# if ! defined free && ! defined EXIT_SUCCESS && (defined __STDC__ || defined __C99__FUNC__ \ || defined __cplusplus || defined _MSC_VER) void free (void *); /* INFRINGES ON USER NAME SPACE */ # endif @@ -408,23 +420,7 @@ union yyalloc ((N) * (sizeof (yytype_int16) + sizeof (YYSTYPE)) \ + YYSTACK_GAP_MAXIMUM) -/* 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 +# define YYCOPY_NEEDED 1 /* Relocate STACK from its old location to the new one. The local variables YYSIZE and YYSTACKSIZE give the old and new number of @@ -444,6 +440,26 @@ 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. */ @@ -531,7 +547,7 @@ static const yytype_uint8 yyrline[] = }; #endif -#if YYDEBUG || YYERROR_VERBOSE || YYTOKEN_TABLE +#if YYDEBUG || YYERROR_VERBOSE || 1 /* YYTNAME[SYMBOL-NUM] -- String name of the symbol SYMBOL-NUM. First, the terminals, then, starting at YYNTOKENS, nonterminals. */ static const char *const yytname[] = @@ -542,7 +558,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", 0 + "path_tag", YY_NULL }; #endif @@ -574,8 +590,8 @@ static const yytype_uint8 yyr2[] = 3, 1, 1 }; -/* YYDEFACT[STATE-NAME] -- Default rule to reduce with in state - STATE-NUM when YYTABLE doesn't specify something else to do. Zero +/* YYDEFACT[STATE-NAME] -- Default reduction number in state STATE-NUM. + Performed when YYTABLE doesn't specify something else to do. Zero means the default is an error. */ static const yytype_uint8 yydefact[] = { @@ -614,8 +630,7 @@ 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 zero, do what YYDEFACT says. - If YYTABLE_NINF, syntax error. */ + number is the opposite. If YYTABLE_NINF, syntax error. */ #define YYTABLE_NINF -3 static const yytype_int8 yytable[] = { @@ -625,6 +640,12 @@ 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, @@ -656,78 +677,50 @@ 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. */ + 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. */ #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 && yylen == 1) \ - { \ - yychar = (Token); \ - yylval = (Value); \ - yytoken = YYTRANSLATE (yychar); \ - YYPOPSTACK (1); \ - goto yybackup; \ - } \ - else \ - { \ +#define YYBACKUP(Token, Value) \ +do \ + if (yychar == YYEMPTY) \ + { \ + yychar = (Token); \ + yylval = (Value); \ + YYPOPSTACK (yylen); \ + yystate = *yyssp; \ + 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 -/* 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. */ - +/* This macro is provided for backward compatibility. */ #ifndef YY_LOCATION_PRINT -# 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 +# define YY_LOCATION_PRINT(File, Loc) ((void) 0) #endif /* YYLEX -- calling `yylex' with the right arguments. */ - #ifdef YYLEX_PARAM # define YYLEX yylex (&yylval, YYLEX_PARAM) #else @@ -779,6 +772,8 @@ yy_symbol_value_print (yyoutput, yytype, yyvaluep, lexer, handlers) struct TsConfigHandlers* handlers; #endif { + FILE *yyo = yyoutput; + YYUSE (yyo); if (!yyvaluep) return; YYUSE (lexer); @@ -792,7 +787,7 @@ yy_symbol_value_print (yyoutput, yytype, yyvaluep, lexer, handlers) switch (yytype) { default: - break; + break; } } @@ -922,7 +917,6 @@ int yydebug; # define YYMAXDEPTH 10000 #endif - #if YYERROR_VERBOSE @@ -1025,115 +1019,145 @@ yytnamerr (char *yyres, const char *yystr) } # endif -/* 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) -{ - int yyn = yypact[yystate]; +/* 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. - if (! (YYPACT_NINF < yyn && yyn <= YYLAST)) - return 0; - else + 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) +{ + 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 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; - } + 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; + } + } + } + } - yyf = YY_(yyformat); - yysize1 = yysize + yystrlen (yyf); - yysize_overflow |= (yysize1 < yysize); - yysize = yysize1; + switch (yycount) + { +# 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_ + } - if (yysize_overflow) - return YYSIZE_MAXIMUM; + { + YYSIZE_T yysize1 = yysize + yystrlen (yyformat); + if (! (yysize <= yysize1 && yysize1 <= YYSTACK_ALLOC_MAXIMUM)) + return 2; + yysize = yysize1; + } - 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; + if (*yymsg_alloc < yysize) + { + *yymsg_alloc = 2 * yysize; + if (! (yysize <= *yymsg_alloc + && *yymsg_alloc <= YYSTACK_ALLOC_MAXIMUM)) + *yymsg_alloc = YYSTACK_ALLOC_MAXIMUM; + return 1; } + + /* 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; } #endif /* YYERROR_VERBOSE */ - /*-----------------------------------------------. | Release the memory associated to this symbol. | @@ -1166,32 +1190,16 @@ 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 or yypush_parse. | -`-------------------------*/ +/*----------. +| yyparse. | +`----------*/ #ifdef YYPARSE_PARAM #if (defined __STDC__ || defined __C99__FUNC__ \ @@ -1219,8 +1227,31 @@ 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; +YYSTYPE yylval YY_INITIAL_VALUE(yyval_default); /* Number of syntax errors so far. */ int yynerrs; @@ -1233,7 +1264,7 @@ YYSTYPE yylval; `yyss': related to states. `yyvs': related to semantic values. - Refer to the stacks thru separate pointers, to allow yyoverflow + Refer to the stacks through separate pointers, to allow yyoverflow to reallocate them elsewhere. */ /* The state stack. */ @@ -1251,7 +1282,7 @@ YYSTYPE yylval; int yyn; int yyresult; /* Lookahead token as an internal (translated) token number. */ - int yytoken; + int yytoken = 0; /* The variables used to return semantic value and location from the action routines. */ YYSTYPE yyval; @@ -1269,9 +1300,8 @@ YYSTYPE yylval; Keep to zero when no symbol should be popped. */ int yylen = 0; - yytoken = 0; - yyss = yyssa; - yyvs = yyvsa; + yyssp = yyss = yyssa; + yyvsp = yyvs = yyvsa; yystacksize = YYINITDEPTH; YYDPRINTF ((stderr, "Starting parse\n")); @@ -1280,14 +1310,6 @@ YYSTYPE yylval; 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; /*------------------------------------------------------------. @@ -1379,7 +1401,7 @@ yybackup: /* First try to decide what to do without reference to lookahead token. */ yyn = yypact[yystate]; - if (yyn == YYPACT_NINF) + if (yypact_value_is_default (yyn)) goto yydefault; /* Not known => get a lookahead token if don't already have one. */ @@ -1410,8 +1432,8 @@ yybackup: yyn = yytable[yyn]; if (yyn <= 0) { - if (yyn == 0 || yyn == YYTABLE_NINF) - goto yyerrlab; + if (yytable_value_is_error (yyn)) + goto yyerrlab; yyn = -yyn; goto yyreduce; } @@ -1428,7 +1450,9 @@ yybackup: yychar = YYEMPTY; yystate = yyn; + YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN *++yyvsp = yylval; + YY_IGNORE_MAYBE_UNINITIALIZED_END goto yynewstate; @@ -1465,81 +1489,81 @@ yyreduce: switch (yyn) { case 4: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 90 "TsConfigGrammar.y" { HANDLE_EVENT(GroupOpen, (yyvsp[(1) - (1)])); } break; case 5: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 92 "TsConfigGrammar.y" { HANDLE_EVENT(GroupClose, (yyvsp[(1) - (1)])); } break; case 9: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 96 "TsConfigGrammar.y" { HANDLE_EVENT(GroupName, (yyvsp[(1) - (2)])); } break; case 12: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 100 "TsConfigGrammar.y" { HANDLE_EVENT(ListOpen, (yyvsp[(1) - (1)])); } break; case 13: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 102 "TsConfigGrammar.y" { HANDLE_EVENT(ListClose, (yyvsp[(1) - (1)])); } break; case 17: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 106 "TsConfigGrammar.y" { HANDLE_EVENT(LiteralValue, (yyvsp[(1) - (1)])); } break; case 27: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 114 "TsConfigGrammar.y" { HANDLE_EVENT(PathOpen, (yyvsp[(1) - (1)])); } break; case 28: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 116 "TsConfigGrammar.y" { HANDLE_EVENT(PathClose, (yyvsp[(1) - (1)])); } break; case 31: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 120 "TsConfigGrammar.y" { HANDLE_EVENT(PathTag, (yyvsp[(1) - (1)])); } break; case 32: - -/* Line 1455 of yacc.c */ +/* Line 1792 of yacc.c */ #line 120 "TsConfigGrammar.y" { HANDLE_EVENT(PathIndex, (yyvsp[(1) - (1)])); } break; - -/* Line 1455 of yacc.c */ -#line 1541 "TsConfigGrammar.c" +/* Line 1792 of yacc.c */ +#line 1554 "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); @@ -1567,6 +1591,10 @@ 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) { @@ -1574,37 +1602,36 @@ yyerrlab: #if ! YYERROR_VERBOSE yyerror (lexer, handlers, YY_("syntax error")); #else +# define YYSYNTAX_ERROR yysyntax_error (&yymsg_alloc, &yymsg, \ + yyssp, yytoken) { - 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; - } + 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; } +# undef YYSYNTAX_ERROR #endif } @@ -1663,7 +1690,7 @@ yyerrlab1: for (;;) { yyn = yypact[yystate]; - if (yyn != YYPACT_NINF) + if (!yypact_value_is_default (yyn)) { yyn += YYTERROR; if (0 <= yyn && yyn <= YYLAST && yycheck[yyn] == YYTERROR) @@ -1686,7 +1713,9 @@ yyerrlab1: YY_STACK_PRINT (yyss, yyssp); } + YY_IGNORE_MAYBE_UNINITIALIZED_BEGIN *++yyvsp = yylval; + YY_IGNORE_MAYBE_UNINITIALIZED_END /* Shift the error token. */ @@ -1710,7 +1739,7 @@ yyabortlab: yyresult = 1; goto yyreturn; -#if !defined(yyoverflow) || YYERROR_VERBOSE +#if !defined yyoverflow || YYERROR_VERBOSE /*-------------------------------------------------. | yyexhaustedlab -- memory exhaustion comes here. | `-------------------------------------------------*/ @@ -1722,8 +1751,13 @@ yyexhaustedlab: yyreturn: if (yychar != YYEMPTY) - yydestruct ("Cleanup: discarding lookahead", - yytoken, &yylval, lexer, handlers); + { + /* 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); + } /* Do not reclaim the symbols of the rule which action triggered this YYABORT or YYACCEPT. */ YYPOPSTACK (yylen); @@ -1747,10 +1781,8 @@ yyreturn: } - -/* Line 1675 of yacc.c */ +/* Line 2055 of yacc.c */ #line 122 "TsConfigGrammar.y" # endif // __clang_analyzer__ - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5ee27f38/lib/tsconfig/TsConfigGrammar.h ---------------------------------------------------------------------- diff --git a/lib/tsconfig/TsConfigGrammar.h b/lib/tsconfig/TsConfigGrammar.h index d3581d9..1700ea1 100644 --- a/lib/tsconfig/TsConfigGrammar.h +++ b/lib/tsconfig/TsConfigGrammar.h @@ -1,10 +1,8 @@ +/* A Bison parser, made by GNU Bison 2.7. */ -/* A Bison parser, made by GNU Bison 2.4.1. */ - -/* Skeleton interface for Bison's Yacc-like parsers in C +/* Bison interface for Yacc-like parsers in C - Copyright (C) 1984, 1989, 1990, 2000, 2001, 2002, 2003, 2004, 2005, 2006 - Free Software Foundation, Inc. + Copyright (C) 1984, 1989-1990, 2000-2012 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 @@ -32,9 +30,17 @@ 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 1676 of yacc.c */ +/* Line 2058 of yacc.c */ #line 1 "TsConfigGrammar.y" /** @file @@ -61,9 +67,8 @@ */ - -/* Line 1676 of yacc.c */ -#line 67 "TsConfigGrammar.h" +/* Line 2058 of yacc.c */ +#line 72 "TsConfigGrammar.h" /* Tokens. */ #ifndef YYTOKENTYPE @@ -101,7 +106,6 @@ - #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED typedef int YYSTYPE; # define YYSTYPE_IS_TRIVIAL 1 @@ -110,5 +114,18 @@ 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 */
