You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2011/05/24 06:11:39 UTC
svn commit: r1126862 [3/4] - in /trafficserver/traffic/branches/ssc:
iocore/aio/ iocore/cache/ iocore/cluster/ iocore/dns/ iocore/eventsystem/
iocore/hostdb/ iocore/hostdb/include/ iocore/net/ iocore/utils/
lib/records/ lib/ts/ lib/wccp/ mgmt/ mgmt/api...
Added: trafficserver/traffic/branches/ssc/lib/ts/IpMap.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/IpMap.cc?rev=1126862&view=auto
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/IpMap.cc (added)
+++ trafficserver/traffic/branches/ssc/lib/ts/IpMap.cc Tue May 24 04:11:36 2011
@@ -0,0 +1,1101 @@
+# include "IpMap.h"
+// # include <iostream>
+
+/* Don't bother to look at this code if you don't know how a
+ red/black tree works. There are so many good references on the
+ subject it's a waste to have some inferior version here. The
+ methods on @c Node follow the standard implementation except for
+ being parameterized by direction (so that, for instance, right
+ rotate and left rotate are both done by the @c rotate method with
+ a direction argument).
+*/
+
+// Validation / printing disabled until I figure out how to generalize so
+// as to not tie reporting into a particular project environment.
+
+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;
+ d = splice_node->getChildDirection(remove_node); // The direction is by rebalance
+ 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
+ in the map. This includes the type, the common argument type, and
+ some utility methods to operate on the address.
+*/
+template <
+ typename N ///< Node type.
+> struct IpMapBase {
+ friend class ::IpMap;
+
+ typedef IpMapBase self; ///< Self reference type.
+ typedef typename N::ArgType ArgType; ///< Import type.
+ typedef typename N::Metric Metric; ///< Import type.g482
+
+ IpMapBase() : _root(0) {}
+ ~IpMapBase() { this->erase(); }
+
+ /** Mark a range.
+ All addresses in the range [ @a min , @a max ] are marked with @a data.
+ @return This object.
+ */
+ self& mark(
+ ArgType min, ///< Minimum value in range.
+ ArgType max, ///< Maximum value in range.
+ void* data = 0 ///< Client data payload.
+ );
+ /** Unmark addresses.
+
+ All addresses in the range [ @a min , @a max ] are cleared
+ (removed from the map), no longer marked.
+
+ @return This object.
+ */
+ self& unmark(
+ ArgType min,
+ ArgType max
+ );
+
+ /** Test for membership.
+
+ @return @c true if the address is in the map, @c false if not.
+ If the address is in the map and @a ptr is not @c NULL, @c *ptr
+ is set to the client data for the address.
+ */
+ bool contains(
+ ArgType target, ///< Search target value.
+ void **ptr = 0 ///< Client data return.
+ );
+
+ /** Erase entire map.
+
+ All addresses are discarded.
+
+ @note This is much faster than using @c unmark with a range of
+ all addresses.
+
+ @return This map.
+ */
+ self& erase();
+
+ /** Lower bound for @a target. @return The node whose minimum value
+ is the largest that is not greater than @a target, or @c NULL if
+ all minimum values are larger than @a target.
+ */
+ N* lowerBound(ArgType target);
+
+ /** Insert @a n after @a spot.
+ Caller is responsible for ensuring that @a spot is in this container
+ and the proper location for @a n.
+ */
+ void insertAfter(
+ N* spot, ///< Node in list.
+ N* n ///< Node to insert.
+ );
+ /** Insert @a n before @a spot.
+ Caller is responsible for ensuring that @a spot is in this container
+ and the proper location for @a n.
+ */
+ void insertBefore(
+ N* spot, ///< Node in list.
+ N* n ///< Node to insert.
+ );
+ /// Add node @a n as the first node.
+ void prepend(
+ N* n
+ );
+ /// Add node @a n as the last node.
+ void append(
+ N* n
+ );
+ /// Remove a node.
+ void remove(
+ N* n ///< Node to remove.
+ );
+
+ /** Validate internal data structures.
+ @note Intended for debugging, not general client use.
+ */
+ void validate();
+
+ /// Print all spans.
+ /// @return This map.
+ self& print();
+
+ // Helper methods.
+ N* prev(RBNode* n) { return static_cast<N*>(n->_prev); }
+ N* next(RBNode* n) { return static_cast<N*>(n->_next); }
+ N* parent(RBNode* n) { return static_cast<N*>(n->_parent); }
+ N* left(RBNode* n) { return static_cast<N*>(n->_left); }
+ N* right(RBNode* n) { return static_cast<N*>(n->_right); }
+ N* getHead() { return static_cast<N*>(_list.getHead()); }
+ N* getTail() { return static_cast<N*>(_list.getTail()); }
+
+ N* _root; ///< Root node.
+ /// In order list of nodes.
+ /// For ugly compiler reasons, this is a list of base class pointers
+ /// even though we really store @a N instances on it.
+ typedef IntrusiveDList<RBNode, &RBNode::_next, &RBNode::_prev> NodeList;
+ /// This keeps track of all allocated nodes in order.
+ /// Iteration depends on this list being maintained.
+ NodeList _list;
+};
+
+template < typename N > N*
+IpMapBase<N>::lowerBound(ArgType target) {
+ N* n = _root; // current node to test.
+ N* zret = 0; // best node so far.
+ while (n) {
+ if (target < n->_min) n = left(n);
+ else {
+ zret = n; // this is a better candidate.
+ if (n->_max < target) n = right(n);
+ else break;
+ }
+ }
+ return zret;
+}
+
+template < typename N > IpMapBase<N>&
+IpMapBase<N>::erase() {
+ // Delete everything.
+ N* n = static_cast<N*>(_list.getHead());
+ while (n) {
+ N* x = n;
+ n = next(n);
+ delete x;
+ }
+ _list.clear();
+ _root = 0;
+ return *this;
+}
+
+template < typename N > IpMapBase<N>&
+IpMapBase<N>::mark(ArgType min, ArgType max, void* payload) {
+ N* n = this->lowerBound(min); // current node.
+ N* x = 0; // New node, gets set if we re-use an existing one.
+
+ /* We have lots of special cases here primarily to minimize memory allocation
+ by re-using an existing node as often as possible.
+ */
+ if (n) {
+ Metric min_1 = N::deref(min);
+ N::dec(min_1);
+ if (n->_min == min) {
+ // Could be another span further left which is adjacent.
+ // Coalesce if the data is the same.
+ if (n->_prev && prev(n)->_data == payload && prev(n)->_max == min_1) {
+ x = prev(n);
+ n = x; // need to back up n because we've moved our frame of reference back.
+ x->setMax(max);
+ } else if (n->_max <= max) {
+ // Span will be subsumed by request span so it's available for use.
+ x = n;
+ x->setMax(max).setData(payload);
+ } else if (n->_data == payload) {
+ return *this; // request is covered by existing span with the same data
+ } else {
+ Metric max_plus = N::deref(max);
+ N::inc(max_plus);
+ // request span is covered by existing span.
+ x = new N(min, max, payload); //
+ n->setMin(max_plus); // clip existing.
+ this->insertBefore(n, x);
+ return *this;
+ }
+ } else if (n->_data == payload && n->_max >= min_1) {
+ x = n;
+ // If the existing span covers the requested span, we're done.
+ if (x->_max >= max) return *this;
+ x->setMax(max);
+ } else if (n->_max <= max) {
+ // Can only have left skew overlap, otherwise disjoint.
+ // Clip if overlap.
+ if (n->_max >= min) n->setMax(min_1);
+ else if (next(n) && n->_max <= max) {
+ // request region covers next span so we can re-use that node.
+ x = next(n);
+ x->setMin(min).setMax(max).setData(payload);
+ n = x; // this gets bumped again, which is correct.
+ }
+ } else {
+ // Existing span covers new span but with a different payload.
+ // We split it, put the new span in between and we're done.
+ N* r;
+ Metric max_plus = N::deref(max);
+ N::inc(max_plus);
+ x = new N(min, max, payload);
+ r = new N(max_plus, n->_max, n->_data);
+ n->setMax(min_1);
+ this->insertAfter(n, x);
+ this->insertAfter(x, r);
+ return *this; // done.
+ }
+ n = next(n); // lower bound span handled, move on.
+ if (!x) {
+ x = new N(min, max, payload);
+ if (n) this->insertBefore(n, x);
+ else this->append(x); // note that since n == 0 we'll just return.
+ }
+ } else {
+ x = new N(min, max, payload);
+ this->prepend(x);
+ n = next(x);
+ }
+
+ // At this point, @a x has the node for this span and all existing spans of
+ // interest start at or past this span.
+ while (n) {
+ if (n->_max <= max) {
+ x = n;
+ n = next(n);
+ this->remove(x);
+ } else if (n->_min > max) {
+ // no overlap so we're done.
+ break;
+ } else {
+ Metric max_plus = N::deref(max);
+ // just right overlap, clip and we're done.
+ N::inc(max_plus);
+ n->setMin(max_plus);
+ break;
+ }
+ }
+
+ return *this;
+}
+
+template <typename N> IpMapBase<N>&
+IpMapBase<N>::unmark(ArgType min, ArgType max) {
+ N* n = this->lowerBound(min);
+ N* x; // temp for deletes.
+
+ // Need to handle special case where first span starts to the left.
+ if (n && n->_min < min) {
+ if (n->_max >= min) { // some overlap
+ Metric min_1 = N::deref(min);
+ N::dec(min_1);
+ if (n->_max > max) {
+ // request span is covered by existing span - split existing span.
+ Metric max_plus = N::deref(max);
+ N::inc(max_plus);
+ x = new N(max_plus, n->_max, n->_data);
+ n->setMax(min_1);
+ this->insertAfter(n, x);
+ return *this; // done.
+ } else {
+ n->setMax(min_1); // just clip overloap.
+ }
+ } // else disjoint so just skip it.
+ n = next(n);
+ }
+ // n and all subsequent spans start at >= min.
+ while (n) {
+ x = n;
+ n = next(n);
+ if (x->_max <= max) {
+ this->remove(x);
+ } else {
+ if (x->_min <= max) { // clip overlap
+ Metric max_plus = N::deref(max);
+ N::inc(max_plus);
+ x->setMin(max_plus);
+ }
+ break;
+ }
+ }
+ return *this;
+}
+
+template <typename N> void
+IpMapBase<N>::insertAfter(N* spot, N* n) {
+ N* c = right(spot);
+ if (!c) spot->setChild(n, N::RIGHT);
+ else spot->_next->setChild(n, N::LEFT);
+
+ _list.insertAfter(spot, n);
+ _root = static_cast<N*>(n->rebalanceAfterInsert());
+}
+
+template <typename N> void
+IpMapBase<N>::insertBefore(N* spot, N* n) {
+ N* c = left(spot);
+ if (!c) spot->setChild(n, N::LEFT);
+ else spot->_prev->setChild(n, N::RIGHT);
+
+ _list.insertBefore(spot, n);
+ _root = static_cast<N*>(n->rebalanceAfterInsert());
+}
+
+template <typename N> void
+IpMapBase<N>::prepend(N* n) {
+ if (!_root) _root = n;
+ else _root = static_cast<N*>(_list.getHead()->setChild(n, N::LEFT)->rebalanceAfterInsert());
+ _list.prepend(n);
+}
+
+template <typename N> void
+IpMapBase<N>::append(N* n) {
+ if (!_root) _root = n;
+ else _root = static_cast<N*>(_list.getTail()->setChild(n, N::RIGHT)->rebalanceAfterInsert());
+ _list.append(n);
+}
+
+template <typename N> void
+IpMapBase<N>::remove(N* n) {
+ _root = static_cast<N*>(n->remove());
+ _list.take(n);
+ delete n;
+}
+
+template <typename N> bool
+IpMapBase<N>::contains(ArgType x, void** ptr) {
+ bool zret = false;
+ N* n = _root; // current node to test.
+ while (n) {
+ if (x < n->_min) n = left(n);
+ else if (n->_max < x) n = right(n);
+ else {
+ if (ptr) *ptr = n->_data;
+ zret = true;
+ break;
+ }
+ }
+ return zret;
+}
+//----------------------------------------------------------------------------
+template <typename N> void
+IpMapBase<N>::validate() {
+# if 0
+ if (_root) _root->validate();
+ for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
+ Node* x;
+ if (0 != (x = n->_next)) {
+ if (x->_prev != n)
+ std::cout << "Broken list" << std::endl;
+ if (n->_max >= x->_min)
+ std::cout << "Out of order - " << n->_max << " > " << x->_min << std::endl;
+ if (n->_parent == n || n->_left == n || n->_right == n)
+ std::cout << "Looped node" << std::endl;
+ }
+ }
+# endif
+}
+
+template <typename N> IpMapBase<N>&
+IpMapBase<N>::print() {
+# if 0
+ for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
+ std::cout
+ << n << ": " << n->_min << '-' << n->_max << " [" << n->_data << "] "
+ << (n->_color == Node::BLACK ? "Black " : "Red ") << "P=" << n->_parent << " L=" << n->_left << " R=" << n->_right
+ << std::endl;
+ }
+# endif
+ return *this;
+}
+
+//----------------------------------------------------------------------------
+typedef Interval<uint32_t, uint32_t> Ip4Span;
+
+/** Node for IPv4 map.
+ We store the address in host order in the @a _min and @a _max
+ members for performance. We store copies in the @a _sa member
+ for API compliance (which requires @c sockaddr_storage* access).
+*/
+class Ip4Node : public IpMap::Node, protected Ip4Span {
+ friend class IpMapBase<Ip4Node>;
+public:
+ typedef Ip4Node self; ///< Self reference type.
+
+ /// Construct with values.
+ Ip4Node(
+ ArgType min, ///< Minimum address (network order).
+ ArgType max, ///< Maximum address (network order).
+ void* data ///< Client data.
+ ) : Node(data), Ip4Span(ntohl(min), ntohl(max)) {
+ ink_inet_ip4_set(ink_inet_ss_cast(&_sa._min), min);
+ ink_inet_ip4_set(ink_inet_ss_cast(&_sa._max), max);
+ }
+ /// @return The minimum value of the interval.
+ virtual sockaddr_storage const* min() {
+ return ink_inet_ss_cast(&_sa._min);
+ }
+ /// @return The maximum value of the interval.
+ virtual sockaddr_storage const* max() {
+ return ink_inet_ss_cast(&_sa._max);
+ }
+ /// Set the client data.
+ self& setData(
+ void* data ///< Client data.
+ ) {
+ _data = data;
+ return *this;
+ }
+protected:
+
+ /// Set the minimum value of the interval.
+ /// @return This interval.
+ self& setMin(
+ ArgType min ///< Minimum value (host order).
+ ) {
+ _min = min;
+ _sa._min.sin_addr.s_addr = htonl(min);
+ return *this;
+ }
+
+ /// Set the maximum value of the interval.
+ /// @return This interval.
+ self& setMax(
+ ArgType max ///< Maximum value (host order).
+ ) {
+ _max = max;
+ _sa._max.sin_addr.s_addr = htonl(max);
+ return *this;
+ }
+
+ // Static helper methods for Metric.
+
+ /** Compare two metrics.
+ @return
+ - -1 if @a lhs < @a rhs
+ - 0 if @a lhs == @a rhs
+ - 1 if @a lhs > @a rhs
+ */
+ static int cmp(
+ ArgType lhs,
+ ArgType rhs
+ ) {
+ return lhs < rhs ? -1
+ : lhs > rhs ? 1
+ : 0
+ ;
+ }
+
+ /// Increment a metric.
+ static void inc(
+ Metric& m ///< Incremented in place.
+ ) {
+ ++m;
+ }
+
+ /// Decrement a metric.
+ static void dec(
+ Metric& m ///< Decremented in place.
+ ) {
+ --m;
+ }
+
+ /// @return Dereferenced @a addr.
+ static Metric deref(
+ ArgType addr ///< Argument to dereference.
+ ) {
+ return addr;
+ }
+
+ struct {
+ sockaddr_in _min;
+ sockaddr_in _max;
+ } _sa; ///< Addresses in API compliant form.
+
+};
+
+class Ip4Map : public IpMapBase<Ip4Node> {
+ friend class ::IpMap;
+};
+
+//----------------------------------------------------------------------------
+typedef Interval<sockaddr_in6> Ip6Span;
+
+/** Node for IPv6 map.
+*/
+class Ip6Node : public IpMap::Node, protected Ip6Span {
+ friend class IpMapBase<Ip6Node>;
+public:
+ typedef Ip6Node self; ///< Self reference type.
+ typedef Metric const* ArgType; ///< Override from @c Interval.
+
+ /// Construct with values.
+ Ip6Node(
+ ArgType min, ///< Minimum address (network order).
+ ArgType max, ///< Maximum address (network order).
+ void* data ///< Client data.
+ ) : Node(data), Ip6Span(*min, *max) {
+ }
+ /// Construct with values.
+ Ip6Node(
+ Metric const& min, ///< Minimum address (network order).
+ Metric const& max, ///< Maximum address (network order).
+ void* data ///< Client data.
+ ) : Node(data), Ip6Span(min, max) {
+ }
+ /// @return The minimum value of the interval.
+ virtual sockaddr_storage const* min() {
+ return ink_inet_ss_cast(&_min);
+ }
+ /// @return The maximum value of the interval.
+ virtual sockaddr_storage const* max() {
+ return ink_inet_ss_cast(&_max);
+ }
+ /// Set the client data.
+ self& setData(
+ void* data ///< Client data.
+ ) {
+ _data = data;
+ return *this;
+ }
+protected:
+
+ /// Set the minimum value of the interval.
+ /// @return This interval.
+ self& setMin(
+ ArgType min ///< Minimum value (host order).
+ ) {
+ ink_inet_copy(ink_inet_ss_cast(&_min), ink_inet_ss_cast(min));
+ return *this;
+ }
+
+ /// Set the minimum value of the interval.
+ /// @return This interval.
+ self& setMin(
+ Metric const& min ///< Minimum value (host order).
+ ) {
+ return this->setMin(&min);
+ }
+
+ /// Set the maximum value of the interval.
+ /// @return This interval.
+ self& setMax(
+ ArgType max ///< Maximum value (host order).
+ ) {
+ ink_inet_copy(ink_inet_ss_cast(&_max), ink_inet_ss_cast(max));
+ return *this;
+ }
+ /// Set the maximum value of the interval.
+ /// @return This interval.
+ self& setMax(
+ Metric const& max ///< Maximum value (host order).
+ ) {
+ return this->setMax(&max);
+ }
+
+ // Static helper methods for Metric.
+
+ /** Compare two metrics.
+ @return
+ - -1 if @a lhs < @a rhs
+ - 0 if @a lhs == @a rhs
+ - 1 if @a lhs > @a rhs
+ */
+ static int cmp(
+ ArgType lhs,
+ ArgType rhs
+ ) {
+ return ink_inet_cmp(ink_inet_ss_cast(lhs), ink_inet_ss_cast(rhs));
+ }
+
+ /// Increment a metric.
+ static void inc(
+ Metric& m ///< Incremented in place.
+ ) {
+ uint8_t* addr = m.sin6_addr.__in6_u.__u6_addr8;
+ uint8_t* b = addr + INK_IP6_SIZE;
+ do {
+ ++*--b;
+ } while (b > addr && 0 == *b);
+ }
+
+ /// Decrement a metric.
+ static void dec(
+ Metric& m ///< Decremented in place.
+ ) {
+ uint8_t* addr = m.sin6_addr.__in6_u.__u6_addr8;
+ uint8_t* b = addr + INK_IP6_SIZE;
+ do {
+ --*--b;
+ } while (b > addr && static_cast<uint8_t>(0xFF) == *b);
+ }
+ /// @return Dereferenced @a addr.
+ static Metric const& deref(
+ ArgType addr ///< Argument to dereference.
+ ) {
+ return *addr;
+ }
+
+};
+
+inline int cmp(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
+ return memcmp(lhs.sin6_addr.__in6_u.__u6_addr8, rhs.sin6_addr.__in6_u.__u6_addr8, INK_IP6_SIZE);
+}
+
+// Helper functions
+
+/// Less than.
+inline bool operator<(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) {
+ return -1 == ts::detail::cmp(*lhs, rhs);
+}
+/// Less than.
+inline bool operator<(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+ return -1 == ts::detail::cmp(lhs, *rhs);
+}
+/// Equality.
+inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+ return 0 == ts::detail::cmp(lhs, *rhs);
+}
+/// Equality.
+inline bool operator==(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) {
+ return 0 == ts::detail::cmp(*lhs, rhs);
+}
+/// Equality.
+inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
+ return 0 == ts::detail::cmp(lhs, rhs);
+}
+/// Less than or equal.
+inline bool operator<=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+ return 1 != ts::detail::cmp(lhs, *rhs);
+}
+/// Greater than or equal.
+inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
+ return -1 != ts::detail::cmp(lhs, rhs);
+}
+/// Greater than or equal.
+inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+ return -1 != ts::detail::cmp(lhs, *rhs);
+}
+/// Greater than.
+inline bool operator>(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+ return 1 == ts::detail::cmp(lhs, *rhs);
+}
+
+class Ip6Map : public IpMapBase<Ip6Node> {
+ friend class ::IpMap;
+};
+
+}} // end namespaces
+
+//----------------------------------------------------------------------------
+namespace {
+ ///< @return The network order IPv4 address in @a target.
+ inline uint32_t const& ip4_addr(sockaddr_storage const* target) {
+ return ink_inet_ip4_cast(target)->sin_addr.s_addr;
+ }
+}
+IpMap::~IpMap() {
+ delete _m4;
+ delete _m6;
+}
+
+inline ts::detail::Ip4Map*
+IpMap::force4() {
+ if (!_m4) _m4 = new ts::detail::Ip4Map;
+ return _m4;
+}
+
+bool
+IpMap::contains(sockaddr_storage const* target, void** ptr) {
+ bool zret = false;
+ if (AF_INET == target->ss_family) {
+ if (_m4) {
+ zret = _m4->contains(ntohl(ip4_addr(target)));
+ }
+ } else if (AF_INET6 == target->ss_family) {
+ if (_m6) {
+ zret = _m6->contains(ink_inet_ip6_cast(target));
+ }
+ }
+ return zret;
+}
+
+IpMap&
+IpMap::mark(
+ sockaddr_storage const* min,
+ sockaddr_storage const* max,
+ void* data
+) {
+ ink_assert(min->ss_family == max->ss_family);
+ if (AF_INET == min->ss_family) {
+ this->force4()->mark(ip4_addr(min), ip4_addr(max), data);
+ } else if (AF_INET6 == min->ss_family) {
+ if (!_m6) _m6 = new ts::detail::Ip6Map;
+ _m6->mark(ink_inet_ip6_cast(min), ink_inet_ip6_cast(max));
+ }
+ return *this;
+}
+
+IpMap&
+IpMap::mark(uint32_t min, uint32_t max, void* data) {
+ this->force4()->mark(min, max, data);
+ return *this;
+}
+
+IpMap&
+IpMap::unmark(
+ sockaddr_storage const* min,
+ sockaddr_storage const* max
+) {
+ ink_assert(min->ss_family == max->ss_family);
+ if (AF_INET == min->ss_family) {
+ if (_m4) _m4->unmark(ip4_addr(min), ip4_addr(max));
+ } else if (AF_INET6 == min->ss_family) {
+ if (_m6) _m6->unmark(ink_inet_ip6_cast(min), ink_inet_ip6_cast(max));
+ }
+ return *this;
+}
+
+IpMap::iterator
+IpMap::begin() {
+ Node* x;
+ if (_m4) x = _m4->getHead();
+ if (!x && _m6) x = _m6->getHead();
+ return iterator(this, x);
+}
+
+IpMap::iterator&
+IpMap::iterator::operator ++ () {
+ if (_node) {
+ // If we go past the end of the list see if it was the v4 list
+ // and if so, move to the v6 list (if it's there).
+ Node* x = static_cast<Node*>(_node->_next);
+ if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m4->getTail())
+ x = _tree->_m6->getTail();
+ _node = x;
+ }
+ return *this;
+}
+
+inline IpMap::iterator&
+IpMap::iterator::operator--() {
+ if (_node) {
+ // At a node, try to back up. Handle the case where we back over the
+ // start of the v6 addresses and switch to the v4, if there are any.
+ Node* x = static_cast<Node*>(_node->_prev);
+ if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m6->getHead())
+ x = _tree->_m4->getTail();
+ _node = x;
+ } else if (_tree) {
+ // We were at the end. Back up to v6 if possible, v4 if not.
+ if (_tree->_m6) _node = _tree->_m6->getTail();
+ if (!_node && _tree->_m4) _node = _tree->_m4->getTail();
+ }
+ return *this;
+}
+
+
+//----------------------------------------------------------------------------
+//----------------------------------------------------------------------------
+
Added: trafficserver/traffic/branches/ssc/lib/ts/IpMap.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/IpMap.h?rev=1126862&view=auto
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/IpMap.h (added)
+++ trafficserver/traffic/branches/ssc/lib/ts/IpMap.h Tue May 24 04:11:36 2011
@@ -0,0 +1,432 @@
+# if ! defined(TS_RED_BLACK_TREE_HEADER)
+# define TS_RED_BLACK_TREE_HEADER
+
+# include <ts/ink_inet.h>
+# include <ts/IntrusiveDList.h>
+
+/** @file
+
+ Map of IP addresses to client data.
+
+ @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.
+*/
+
+namespace ts { namespace detail {
+
+ /** Interval class.
+ This holds an interval based on a metric @a T along with
+ client data.
+ */
+ template <
+ typename T, ///< Metric for span.
+ typename A = T const& ///< Argument type.
+ > struct Interval {
+ typedef T Metric; ///< Metric type.
+ typedef A ArgType; ///< Type of metric parameter.
+
+ Interval() {} ///< Default constructor.
+ /// Construct with values.
+ Interval(
+ ArgType min, ///< Minimum value in span.
+ ArgType max ///< Maximum value in span.
+ ) : _min(min), _max(max) {}
+ Metric _min; ///< Minimum value in span.
+ Metric _max; ///< Maximum value in span.
+ };
+
+ 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.
+ };
+
+}}
+
+/** Map from IP addresses to client data.
+
+ Conceptually this class maps the entire space of IP addresses to
+ client data. Client data is stored as a @c (void*). Memory
+ management of the data is left to the client. The interface
+ supports marking ranges of addresses with a specific client
+ data. Marking takes a painter's algorithm approach -- any marking
+ overwrites any previous marking on an address. Details of marking
+ calls are discarded and only the final results are kept. That is,
+ a client cannot unmark expliticly any previous marking. Only a
+ specific range of addresses can be unmarked.
+
+ Both IPv4 and IPv6 are supported in the same map. Mixed ranges are
+ not supported (any particular range of addresses must be a single
+ protocol but ranges of both types can be in the map).
+
+ Use @c mark to mark / set/ add addresses to the map.
+ Use @c unmark to unset addresses (setting the client data to 0 does
+ @b not remove the address -- this is for the convenience of clients
+ that do not need data, only membership). @c contains tests for
+ membership and retrieves the client data.
+
+ Ranges can be marked and unmarked arbitrarily. The internal
+ representation keeps a minimal set of ranges to describe the
+ current addresses. Search time is O(log n) where n is the number
+ of disjoint ranges. Marking and unmarking can take O(log n) and
+ may require memory allocation / deallocation although this is
+ minimized.
+
+*/
+
+class IpMap {
+public:
+ typedef IpMap self; ///< Self reference type.
+
+ class iterator; // forward declare.
+
+ /** Public API for intervals in the map.
+ */
+ class Node : protected ts::detail::RBNode {
+ friend class iterator;
+ friend class IpMap;
+ public:
+ typedef Node self; ///< Self reference type.
+ /// Default constructor.
+ Node() : _data(0) {}
+ /// Construct with @a data.
+ Node(void* data) : _data(data) {}
+ /// @return Client data for the node.
+ virtual void* data() { return _data; }
+ /// Set client data.
+ virtual self& setData(
+ void* data ///< Client data pointer to store.
+ ) {
+ _data = data;
+ return *this;
+ }
+ /// @return Minimum value of the interval.
+ virtual sockaddr_storage const* min() = 0;
+ /// @return Maximum value of the interval.
+ virtual sockaddr_storage const* max() = 0;
+ protected:
+ void* _data; ///< Client data.
+ };
+
+ /** Iterator over nodes / intervals.
+
+ The iteration is over all nodes, regardless of which node is
+ used to create the iterator. The node passed to the constructor
+ just sets the current location.
+ */
+ class iterator {
+ friend class IpMap;
+ public:
+ typedef iterator self; ///< Self reference type.
+ typedef Node value_type; ///< Referenced type for iterator.
+ typedef int difference_type; ///< Distance type.
+ typedef Node* pointer; ///< Pointer to referent.
+ typedef Node& reference; ///< Reference to referent.
+ typedef std::bidirectional_iterator_tag iterator_category;
+ /// Default constructor.
+ iterator() : _tree(0), _node(0) {}
+
+ reference operator* (); //!< value operator
+ pointer operator -> (); //!< dereference operator
+ self& operator++(); //!< next node (prefix)
+ self operator++(int); //!< next node (postfix)
+ self& operator--(); ///< previous node (prefix)
+ self operator--(int); ///< next node (postfix)
+
+ /** Equality.
+ @return @c true if the iterators refer to the same node.
+ */
+ bool operator==(self const& that) const;
+ /** Inequality.
+ @return @c true if the iterators refer to different nodes.
+ */
+ bool operator!=(self const& that) const { return ! (*this == that); }
+ private:
+ /// Construct a valid iterator.
+ iterator(IpMap* tree, Node* node) : _tree(tree), _node(node) {}
+ IpMap* _tree; ///< Container.
+ Node* _node; //!< Current node.
+ };
+
+ IpMap(); ///< Default constructor.
+ ~IpMap(); ///< Destructor.
+
+ /** Mark a range.
+ All addresses in the range [ @a min , @a max ] are marked with @a data.
+ @return This object.
+ */
+ self& mark(
+ sockaddr_storage const* min, ///< Minimum value in range.
+ sockaddr_storage const* max, ///< Maximum value in range.
+ void* data = 0 ///< Client data payload.
+ );
+
+ /** Mark a range.
+ All addresses in the range [ @a min , @a max ] are marked with @a data.
+ @note Convenience overload for IPv4 addresses.
+ @return This object.
+ */
+ self& mark(
+ uint32_t min, ///< Minimum address (network order).
+ uint32_t max, ///< Maximum address (network order).
+ void* data = 0 ///< Client data.
+ );
+
+ /** Unmark addresses.
+
+ All addresses in the range [ @a min , @a max ] are cleared
+ (removed from the map), no longer marked.
+
+ @return This object.
+ */
+ self& unmark(
+ sockaddr_storage const* min, ///< Minimum value.
+ sockaddr_storage const* max ///< Maximum value.
+ );
+
+ /** Test for membership.
+
+ @return @c true if the address is in the map, @c false if not.
+ If the address is in the map and @a ptr is not @c NULL, @c *ptr
+ is set to the client data for the address.
+ */
+ bool contains(
+ sockaddr_storage const* target, ///< Search target value.
+ void **ptr = 0 ///< Client data return.
+ );
+
+ /// Iterator for first element.
+ iterator begin();
+ /// Iterator past last element.
+ iterator end();
+
+ /** Validate internal data structures.
+ @note Intended for debugging, not general client use.
+ */
+ void validate();
+
+ /// Print all spans.
+ /// @return This map.
+ self& print();
+
+protected:
+ /// Force the IPv4 map to exist.
+ /// @return The IPv4 map.
+ ts::detail::Ip4Map* force4();
+
+ ts::detail::Ip4Map* _m4; ///< Map of IPv4 addresses.
+ ts::detail::Ip6Map* _m6; ///< Map of IPv6 addresses.
+
+};
+
+inline IpMap::iterator
+IpMap::end() {
+ return iterator(this, 0);
+}
+
+inline IpMap::iterator
+IpMap::iterator::operator ++ (int) {
+ iterator old(*this);
+ ++*this;
+ return old;
+}
+
+inline IpMap::iterator
+IpMap::iterator::operator--(int) {
+ self tmp(*this);
+ --*this;
+ return tmp;
+}
+
+inline bool
+IpMap::iterator::operator == (iterator const& that) const {
+ return _tree == that._tree && _node == that._node;
+}
+
+inline IpMap::iterator::reference
+IpMap::iterator::operator * () {
+ return *_node;
+}
+
+inline IpMap::iterator::pointer
+IpMap::iterator::operator -> () {
+ return _node;
+}
+
+inline IpMap::IpMap() : _m4(0), _m6(0) {}
+
+# endif // TS_RED_BLACK_TREE_HEADER
Added: trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.cc?rev=1126862&view=auto
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.cc (added)
+++ trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.cc Tue May 24 04:11:36 2011
@@ -0,0 +1,156 @@
+/** @file
+
+ Loading @c IpMap from a configuration 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.
+ */
+
+// Copied from IPRange.cc for backwards compatibility.
+
+# include <ts/IpMap.h>
+
+#define TEST(_x)
+
+// #define TEST(_x) _x
+
+#define ERR_STRING_LEN 100
+
+// Returns 0 if successful, 1 if failed
+int
+read_addr(char *line, sockaddr_storage* ss, int *i, int n)
+{
+ int k;
+ char s[17];
+ while ((*i) < n && isspace(line[(*i)]))
+ ++(*i);
+ if (*i == n) {
+ TEST(printf("Socks Configuration (read_an_ip1): Invalid Syntax in line %s\n", line);
+ );
+ return 1;
+ }
+ for (k = 0; k < 17 && (isdigit(line[(*i)]) || (line[(*i)] == '.')); ++k, ++(*i)) {
+ s[k] = line[(*i)];
+ }
+ if (k == 17) {
+ TEST(printf("Socks Configuration (read_an_ip2): Invalid Syntax in line %s, k %d\n", line, k);
+ );
+ return 1;
+ }
+ s[k] = '\0';
+ ++k;
+ TEST(printf("IP address read %s\n", s));
+ if (0 != ink_inet_pton(s, ss)) {
+ TEST(printf("Socks Configuration: Illegal IP address read %s, %u\n", s, *ip);
+ );
+ return 1;
+ }
+ return 0;
+}
+
+char *
+Load_IpMap_From_File(IpMap* map, int fd, const char *key_str) {
+ char* zret = 0;
+ FILE* f = fdopen(dup(fd), "r"); // dup so we don't close the original fd.
+ if (f) zret = Load_IpMap_From_File(map, f, key_str);
+ else {
+ zret = (char *) xmalloc(ERR_STRING_LEN);
+ snprintf(zret, ERR_STRING_LEN, "Unable to reopen file descriptor as stream %d:%s", errno, strerror(errno));
+ }
+ return zret;
+}
+
+// Returns 0 if successful, error string otherwise
+char *
+Load_IpMap_From_File(IpMap* map, FILE* f, const char *key_str)
+{
+ int i, n, line_no;
+ int key_len = strlen(key_str);
+ sockaddr_storage ss;
+ char line[MAX_LINE_SIZE];
+
+ // First hardcode 127.0.0.1 into the table
+ map->mark(INADDR_LOOPBACK, INADDR_LOOPBACK);
+
+ line_no = 0;
+ while (fgets(line, MAX_LINE_SIZE, f)) {
+ ++line_no;
+ n = strlen(line);
+ // Find first white space which terminates the line key.
+ for ( i = 0 ; i < n && ! isspace(line[i]); ++i )
+ ;
+ if (i != key_len || 0 != strncmp(line, key_str, key_len))
+ continue;
+ // Now look for IP address
+ while (true) {
+ while (i < n && isspace(line[i]))
+ ++i;
+ if (i == n)
+ break;
+
+ if (read_addr(line, &ss, &i, n) == 1) {
+ char *error_str = (char *) xmalloc(ERR_STRING_LEN);
+ snprintf(error_str, ERR_STRING_LEN, "Incorrect Syntax in Socks Configuration at Line %d", line_no);
+ return error_str;
+ }
+
+ while (i < n && isspace(line[i]))
+ ++i;
+ if (i == n || line[i] == ',') {
+ // You have read an IP address. Enter it in the table
+ this->mark(&ss, &ss);
+ if (i == n)
+ break;
+ else
+ ++i;
+ } else if (line[i] == '-') {
+ sockaddr_storage ss2;
+ // What you have just read is the start of the range,
+ // Now, read the end of the IP range
+ ++i;
+ if (read_addr(line, &ss2, &i, n) == 1) {
+ char *error_str = (char *) xmalloc(ERR_STRING_LEN);
+ snprintf(error_str, ERR_STRING_LEN, "Incorrect Syntax in Socks Configuration at Line %d", line_no);
+ return error_str;
+ }
+ map->mark(&ss, &ss2);
+ while (i < n && isspace(line[i]))
+ i++;
+ if (i == n)
+ break;
+ if (line[i] != ',') {
+ TEST(printf("Socks Configuration (read_table_from_file1):Invalid Syntax in line %s\n", (char *) line);
+ );
+ char *error_str = (char *) xmalloc(ERR_STRING_LEN);
+ snprintf(error_str, ERR_STRING_LEN, "Incorrect Syntax in Socks Configuration at Line %d", line_no);
+ return error_str;
+ }
+ ++i;
+ } else {
+ TEST(printf("Socks Configuration (read_table_from_file2):Invalid Syntax in line %s\n", (char *) line);
+ );
+ char *error_str = (char *) xmalloc(ERR_STRING_LEN);
+ snprintf(error_str, ERR_STRING_LEN, "Incorrect Syntax in Socks Configuration at Line %d", line_no);
+ return error_str;
+ }
+ }
+ }
+ TEST(printf("Socks Conf File Read\n");
+ );
+ return 0;
+}
Added: trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.h?rev=1126862&view=auto
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.h (added)
+++ trafficserver/traffic/branches/ssc/lib/ts/IpMapConf.h Tue May 24 04:11:36 2011
@@ -0,0 +1,31 @@
+/** @file
+
+ Loading @c IpMap from a configuration 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.
+ */
+
+// Copied from IPRange.cc for backwards compatibility.
+
+class IpMap; // declare in name only.
+
+// Returns 0 if successful, error string otherwise
+char * Load_IpMap_From_File(IpMap* map, int fd, const char *key_str);
+// Returns 0 if successful, error string otherwise
+char *Load_IpMap_From_File(IpMap* map, FILE* f, const char *key_str);
Modified: trafficserver/traffic/branches/ssc/lib/ts/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/Makefile.am?rev=1126862&r1=1126861&r2=1126862&view=diff
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/Makefile.am (original)
+++ trafficserver/traffic/branches/ssc/lib/ts/Makefile.am Tue May 24 04:11:36 2011
@@ -20,6 +20,8 @@ noinst_PROGRAMS = mkdfa CompileParseRule
check_PROGRAMS = test_atomic test_freelist test_arena test_List test_Map test_Vec
TESTS = $(check_PROGRAMS)
+AM_CPPFLAGS = -I$(top_srcdir)/lib
+
lib_LTLIBRARIES = libtsutil.la
libtsutil_la_LDFLAGS = -no-undefined -version-info @TS_LIBTOOL_VERSION@
@@ -118,6 +120,8 @@ libtsutil_la_SOURCES = \
fastlz.h \
fastlz.c \
I_Version.h \
+ IntrusiveDList.h \
+ IpMap.h IpMap.cc \
List.h \
llqueue.cc \
lockfile.cc \
Modified: trafficserver/traffic/branches/ssc/lib/ts/Vec.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/Vec.h?rev=1126862&r1=1126861&r2=1126862&view=diff
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/Vec.h (original)
+++ trafficserver/traffic/branches/ssc/lib/ts/Vec.h Tue May 24 04:11:36 2011
@@ -48,16 +48,20 @@ class Vec {
int i; // size index for sets, reserve for vectors
C *v;
C e[VEC_INTEGRAL_SIZE];
+
+ typedef C element_type; ///< Type of elements in this container.
+ typedef C* iterator; ///< Iterator type for STL-like access.
Vec();
Vec<C,A,S>(const Vec<C,A,S> &vv);
Vec<C,A,S>(const C c);
~Vec();
- C &operator[](int i) const { return v[i]; }
+ C &operator[](int i) { return v[i]; }
+ C const&operator[](int i) const { return v[i]; }
- C get(int i);
- void add(C a);
+ C get(int i) const;
+ void add(C const& a);
void push_back(C a) { add(a); } // std::vector name
int add_exclusive(C a);
C& add();
@@ -102,7 +106,10 @@ class Vec {
void push(C a) { insert(0, a); }
void reverse();
void reserve(int n);
- C* end() const { return v + n; }
+ C* begin() { return v; }
+ C const* begin() const { return v; }
+ C* end() { return v + n; }
+ C const* end() const { return v + n; }
C &first() const { return v[0]; }
C &last() const { return v[n-1]; }
Vec<C,A,S>& operator=(Vec<C,A,S> &v) { this->copy(v); return *this; }
@@ -111,6 +118,7 @@ class Vec {
int write(int fd);
int read(int fd);
void qsort(bool (*lt)(C,C));
+ void qsort(bool (*lt)(C const&,C const&));
// private:
void move_internal(Vec<C,A,S> &v);
@@ -182,7 +190,7 @@ Vec<C,A,S>::Vec(C c) {
}
template <class C, class A, int S> inline C
-Vec<C,A,S>::get(int i) {
+Vec<C,A,S>::get(int i) const {
if (i < n && i >= 0)
return v[i];
else
@@ -190,7 +198,7 @@ Vec<C,A,S>::get(int i) {
}
template <class C, class A, int S> inline void
-Vec<C,A,S>::add(C a) {
+Vec<C,A,S>::add(C const& a) {
if (n & (VEC_INTEGRAL_SIZE-1))
v[n++] = a;
else if (!v)
@@ -770,7 +778,7 @@ inline void qsort_Vec(C *left, C *right,
}
template <class C>
-inline void qsort_VecRef(C *left, C *right, bool (*lt)(C&,C&)) {
+inline void qsort_VecRef(C *left, C *right, bool (*lt)(C const&,C const&)) {
Lagain:
if (right - left < 5) {
for (C *y = right - 1; y > left; y--) {
@@ -811,6 +819,12 @@ inline void Vec<C,A,S>::qsort(bool (*lt)
qsort_Vec<C>(&v[0], end(), lt);
}
+template <class C, class A, int S>
+inline void Vec<C,A,S>::qsort(bool (*lt)(C const&,C const&)) {
+ if (n)
+ qsort_VecRef<C>(&v[0], end(), lt);
+}
+
void test_vec();
#endif
Modified: trafficserver/traffic/branches/ssc/lib/ts/ink_inet.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/ink_inet.cc?rev=1126862&r1=1126861&r2=1126862&view=diff
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/ink_inet.cc (original)
+++ trafficserver/traffic/branches/ssc/lib/ts/ink_inet.cc Tue May 24 04:11:36 2011
@@ -163,34 +163,54 @@ ink_inet_addr(const char *s)
return htonl((uint32_t) - 1);
}
-const char *ink_inet_ntop(const struct sockaddr *addr, char *dst, size_t size)
-{
- void *address = NULL;
+const char *ink_inet_ntop(
+ const sockaddr_storage *addr,
+ char *dst, size_t size
+) {
+ void const* ptr = NULL;
- switch (addr->sa_family) {
+ switch (addr->ss_family) {
case AF_INET:
- address = &((struct sockaddr_in *)addr)->sin_addr;
+ ptr = &(ink_inet_ip4_cast(addr)->sin_addr);
break;
case AF_INET6:
- address = &((struct sockaddr_in6 *)addr)->sin6_addr;
+ ptr = &(ink_inet_ip6_cast(addr)->sin6_addr);
+ break;
+ default:
+ snprintf(dst, size, "Bad address type: %d", addr->ss_family);
break;
}
- return inet_ntop(addr->sa_family, address, dst, size);
+ return ptr ?
+ inet_ntop(addr->ss_family, ptr, dst, size)
+ : dst
+ ;
}
-uint16_t ink_inet_port(const struct sockaddr *addr)
-{
- uint16_t port = 0;
+const char *ink_inet_nptop(
+ const sockaddr_storage *addr,
+ char *dst, size_t size
+) {
+ char buff[INET6_ADDRSTRLEN];
+ snprintf(dst, size, "%s:%u",
+ ink_inet_ntop(addr, buff, sizeof(buff)),
+ ink_inet_get_port(addr)
+ );
+ return dst;
+}
- switch (addr->sa_family) {
- case AF_INET:
- port = ntohs(((struct sockaddr_in *)addr)->sin_port);
- break;
- case AF_INET6:
- port = ntohs(((struct sockaddr_in6 *)addr)->sin6_port);
- break;
+int ink_inet_pton(char const* text, sockaddr_storage* ss) {
+ int zret = -1;
+ addrinfo hints; // [out]
+ addrinfo *ai; // [in]
+
+ memset(&hints, 0, sizeof(hints));
+ hints.ai_family = PF_UNSPEC;
+ hints.ai_flags = AI_NUMERICHOST|AI_PASSIVE;
+ if (0 == (zret = getaddrinfo(text, 0, &hints, &ai))) {
+ if (ink_inet_copy(*ss, *ink_inet_ss_cast(ai->ai_addr)))
+ zret = 0;
+ freeaddrinfo(ai);
}
-
- return port;
+ return zret;
}
Modified: trafficserver/traffic/branches/ssc/lib/ts/ink_inet.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/ink_inet.h?rev=1126862&r1=1126861&r2=1126862&view=diff
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/ink_inet.h (original)
+++ trafficserver/traffic/branches/ssc/lib/ts/ink_inet.h Tue May 24 04:11:36 2011
@@ -1,6 +1,13 @@
/** @file
- A brief file description
+ IP related functions.
+
+ This includes various casting functions for working with the
+ @c sockaddr_storage data type. For generality this type is used
+ for storing IP address related information. In most cases this
+ is sufficient as the data can be used directly with system calls.
+ The casting functionsa are used when more specific information is
+ needed from the data.
@section license License
@@ -28,12 +35,15 @@
#include "ink_platform.h"
#include "ink_port.h"
#include "ink_apidefs.h"
+# include <ts/ink_assert.h>
#define INK_GETHOSTBYNAME_R_DATA_SIZE 1024
#define INK_GETHOSTBYADDR_R_DATA_SIZE 1024
-struct ink_gethostbyname_r_data
-{
+/// Size in bytes of an IPv6 address.
+size_t const INK_IP6_SIZE = 16;
+
+struct ink_gethostbyname_r_data {
int herrno;
struct hostent ent;
char buf[INK_GETHOSTBYNAME_R_DATA_SIZE];
@@ -88,7 +98,484 @@ struct hostent *ink_gethostbyaddr_r(char
*/
inkcoreapi uint32_t ink_inet_addr(const char *s);
-const char *ink_inet_ntop(const struct sockaddr *addr, char *dst, size_t size);
-uint16_t ink_inet_port(const struct sockaddr *addr);
+/** Write a null terminated string for @a addr to @a dst.
+ A buffer of size INET6_ADDRSTRLEN suffices, including a terminating nul.
+ */
+char const* ink_inet_ntop(
+ const sockaddr_storage *addr, ///< Address.
+ char *dst, ///< Output buffer.
+ size_t size ///< Length of buffer.
+);
+
+static size_t const INET6_ADDRPORTSTRLEN = INET6_ADDRSTRLEN + 6;
+
+/** Write a null terminated string for @a addr to @a dst with port.
+ A buffer of size INET6_ADDRPORTSTRLEN suffices, including a terminating nul.
+ */
+char const* ink_inet_nptop(
+ const sockaddr_storage *addr, ///< Address.
+ char *dst, ///< Output buffer.
+ size_t size ///< Length of buffer.
+);
+
+/** Convert @a text to an IP address and write it to @a addr.
+
+ @a test is expected to be an explicit address, not a hostname. No
+ hostname resolution is done.
+
+ @note This uses @c getaddrinfo internally and so involves memory
+ allocation.
+
+ @return 0 on success, non-zero on failure.
+*/
+int ink_inet_pton(
+ char const* text, ///< [in] text.
+ sockaddr_storage* addr ///< [out] address
+);
+
+/// Reset an address to invalid.
+/// @note Useful for marking a member as not yet set.
+inline void ink_inet_invalidate(sockaddr_storage* addr) {
+ addr->ss_family = AF_UNSPEC;
+}
+/// Reset an address to invalid.
+/// Convenience overload.
+/// @note Useful for marking a member as not yet set.
+inline void ink_inet_invalidate(sockaddr_storage& addr) {
+ addr.ss_family = AF_UNSPEC;
+}
+/// Test for validity.
+/// @return @c false if the address is reset, @c true otherwise.
+inline bool ink_inet_is_valid(sockaddr_storage const* addr) {
+ return addr->ss_family != AF_UNSPEC;
+}
+/// Test for validity.
+/// Convenience overload.
+/// @return @c false if the address is reset, @c true otherwise.
+inline bool ink_inet_is_valid(sockaddr_storage const& addr) {
+ return addr.ss_family != AF_UNSPEC;
+}
+/// Set to all zero.
+inline void ink_inet_init(sockaddr_storage& addr) {
+ memset(&addr, 0, sizeof(addr));
+ ink_inet_invalidate(addr);
+}
+
+/// Test for IP protocol.
+/// @return @c true if the address is IP, @c false otherwise.
+inline bool ink_inet_is_ip(sockaddr_storage const& addr) {
+ return AF_INET == addr.ss_family || AF_INET6 == addr.ss_family;
+}
+/// Test for IP protocol.
+/// Convenience overload.
+/// @return @c true if the address is IP, @c false otherwise.
+inline bool ink_inet_is_ip(sockaddr_storage const* addr) {
+ return AF_INET == addr->ss_family || AF_INET6 == addr->ss_family;
+}
+/// Test for IPv4 protocol.
+/// @return @c true if the address is IPv4, @c false otherwise.
+inline bool ink_inet_is_ip4(sockaddr_storage const& addr) {
+ return AF_INET == addr.ss_family;
+}
+/// Test for IPv4 protocol.
+/// Convenience overload.
+/// @return @c true if the address is IPv4, @c false otherwise.
+inline bool ink_inet_is_ip4(sockaddr_storage const* addr) {
+ return AF_INET == addr->ss_family;
+}
+/// Test for IPv6 protocol.
+/// @return @c true if the address is IPv6, @c false otherwise.
+inline bool ink_inet_is_ip6(sockaddr_storage const& addr) {
+ return AF_INET6 == addr.ss_family;
+}
+/// Test for IPv6 protocol.
+/// Convenience overload.
+/// @return @c true if the address is IPv6, @c false otherwise.
+inline bool ink_inet_is_ip6(sockaddr_storage const* addr) {
+ return AF_INET6 == addr->ss_family;
+}
+/// @return @c true if the address families are compatible.
+inline bool ink_inet_are_compatible(
+ sockaddr_storage const* lhs, ///< Address to test.
+ sockaddr_storage const* rhs ///< Address to test.
+) {
+ return lhs->ss_family == rhs->ss_family;
+}
+
+// IP address casting.
+// sa_cast to cast to sockaddr*.
+// ss_cast to cast to sockaddr_storage*.
+// ip4_cast converts to sockaddr_in (because that's effectively an IPv4 addr).
+// ip6_cast converts to sockaddr_in6
+inline sockaddr* ink_inet_sa_cast(sockaddr_storage* a) {
+ return static_cast<sockaddr*>(static_cast<void*>(a));
+}
+inline sockaddr const* ink_inet_sa_cast(sockaddr_storage const* a) {
+ return static_cast<sockaddr const*>(static_cast<void const*>(a));
+}
+inline sockaddr_storage* ink_inet_ss_cast(sockaddr* a) {
+ return static_cast<sockaddr_storage*>(static_cast<void*>(a));
+}
+inline sockaddr_storage const* ink_inet_ss_cast(sockaddr const* a) {
+ return static_cast<sockaddr_storage const*>(static_cast<void const*>(a));
+}
+inline sockaddr_storage* ink_inet_ss_cast(sockaddr_in* a) {
+ return static_cast<sockaddr_storage*>(static_cast<void*>(a));
+}
+inline sockaddr_storage const* ink_inet_ss_cast(sockaddr_in const* a) {
+ return static_cast<sockaddr_storage const*>(static_cast<void const*>(a));
+}
+inline sockaddr_storage* ink_inet_ss_cast(sockaddr_in6* a) {
+ return static_cast<sockaddr_storage*>(static_cast<void*>(a));
+}
+inline sockaddr_storage const* ink_inet_ss_cast(sockaddr_in6 const* a) {
+ return static_cast<sockaddr_storage const*>(static_cast<void const*>(a));
+}
+inline sockaddr_in* ink_inet_ip4_cast(sockaddr_storage* a) {
+ return static_cast<sockaddr_in*>(static_cast<void*>(a));
+}
+inline sockaddr_in const* ink_inet_ip4_cast(sockaddr_storage const* a) {
+ return static_cast<sockaddr_in const*>(static_cast<void const*>(a));
+}
+inline sockaddr_in& ink_inet_ip4_cast(sockaddr_storage& a) {
+ return *static_cast<sockaddr_in*>(static_cast<void*>(&a));
+}
+inline sockaddr_in const& ink_inet_ip4_cast(sockaddr_storage const& a) {
+ return *static_cast<sockaddr_in const*>(static_cast<void const*>(&a));
+}
+inline sockaddr_in6* ink_inet_ip6_cast(sockaddr_storage* a) {
+ return static_cast<sockaddr_in6*>(static_cast<void*>(a));
+}
+inline sockaddr_in6 const* ink_inet_ip6_cast(sockaddr_storage const* a) {
+ return static_cast<sockaddr_in6 const*>(static_cast<void const*>(a));
+}
+inline sockaddr_in6& ink_inet_ip6_cast(sockaddr_storage& a) {
+ return *static_cast<sockaddr_in6*>(static_cast<void*>(&a));
+}
+inline sockaddr_in6 const& ink_inet_ip6_cast(sockaddr_storage const& a) {
+ return *static_cast<sockaddr_in6 const*>(static_cast<void const*>(&a));
+}
+/** Get a reference to the port in an address.
+ @note Because this is direct access, the port value is in network order.
+ @see ink_inet_get_port for host order copy.
+ @return A reference to the port value in an IPv4 or IPv6 address.
+ @internal This is primarily for internal use but it might be handy for
+ clients so it is exposed.
+*/
+inline uint16_t& ink_inet_port_cast(sockaddr_storage* ss) {
+ static uint16_t dummy = 0;
+ return AF_INET == ss->ss_family
+ ? ink_inet_ip4_cast(ss)->sin_port
+ : AF_INET6 == ss->ss_family
+ ? ink_inet_ip6_cast(ss)->sin6_port
+ : (dummy = 0)
+ ;
+}
+/** Get a reference to the port in an address.
+ @note Convenience overload.
+ @see ink_inet_port_cast(sockaddr_storage* ss)
+*/
+inline uint16_t& ink_inet_port_cast(sockaddr_storage& ss) {
+ return ink_inet_port_cast(&ss);
+}
+
+/** Access the IPv4 address.
+
+ If this is not an IPv4 address a zero valued address is returned.
+ @note This is direct access to the address so it will be in
+ network order.
+
+ @return A reference to the IPv4 address in @a addr.
+*/
+inline uint32_t& ink_inet_ip4_addr_cast(sockaddr_storage* addr) {
+ static uint32_t dummy = 0;
+ return ink_inet_is_ip4(addr)
+ ? ink_inet_ip4_cast(addr)->sin_addr.s_addr
+ : (dummy = 0)
+ ;
+}
+/** Access the IPv4 address.
+
+ If this is not an IPv4 address a zero valued address is returned.
+ @note This is direct access to the address so it will be in
+ network order.
+
+ @return A reference to the IPv4 address in @a addr.
+*/
+inline uint32_t const& ink_inet_ip4_addr_cast(sockaddr_storage const* addr) {
+ static uint32_t dummy = 0;
+ return ink_inet_is_ip4(addr)
+ ? ink_inet_ip4_cast(addr)->sin_addr.s_addr
+ : static_cast<uint32_t const&>(dummy = 0)
+ ;
+}
+/** Access the IPv6 address.
+
+ If this is not an IPv6 address a zero valued address is returned.
+ @note This is direct access to the address so it will be in
+ network order.
+
+ @return A reference to the IPv6 address in @a addr.
+*/
+inline in6_addr& ink_inet_ip6_addr_cast(sockaddr_storage* addr) {
+ return ink_inet_ip6_cast(addr)->sin6_addr;
+}
+
+
+/// @name sockaddr_storage operators
+//@{
+
+/** Copy the address from @a src to @a dst if it's IP.
+ This attempts to do a minimal copy based on the type of @a src.
+ If @a src is not an IP address type it is @b not copied.
+ @return @c true if @a src was an IP address, @c false otherwise.
+*/
+inline bool ink_inet_copy(
+ sockaddr_storage* dst, ///< Destination object.
+ sockaddr_storage const* src ///< Source object.
+) {
+ size_t n = 0;
+ switch (src->ss_family) {
+ case AF_INET: n = sizeof(sockaddr_in); break;
+ case AF_INET6: n = sizeof(sockaddr_in6); break;
+ }
+ if (n) memcpy(dst, src, n);
+ else ink_inet_invalidate(dst);
+ return n != 0;
+}
+/** Copy the address from @a src to @a dst if it's IP.
+ This attempts to do a minimal copy based on the type of @a src.
+ If @a src is not an IP address type it is @b not copied.
+ @note Convenience overload.
+ @return @c true if @a src was an IP address, @c false otherwise.
+*/
+inline bool ink_inet_copy(
+ sockaddr_storage& dst, ///< Destination object.
+ sockaddr_storage const& src ///< Source object.
+) {
+ return ink_inet_copy(&dst, &src);
+}
+
+/** Compare two addresses.
+ This works only for IP addresses (IPv4, IPv6). A comparison bewteen
+ IPv4 and IPv6 will always return the IPv4 address as lesser.
+ @return
+ - -1 if @a lhs is less than @a rhs.
+ - 0 if @a lhs is identical to @a rhs.
+ - 1 if @a lhs is greater than @a rhs.
+ @internal This looks like a lot of code for an inline but I think it
+ should compile down quite a bit.
+*/
+inline int ink_inet_cmp(
+ sockaddr_storage const* lhs, ///< Left hand operand.
+ sockaddr_storage const* rhs ///< Right hand operand.
+) {
+ int zret = 0;
+ uint16_t rtype = rhs->ss_family;
+ uint16_t ltype = lhs->ss_family;
+
+ if (AF_INET == ltype) {
+ if (AF_INET == rtype) {
+ zret = memcmp(
+ &ink_inet_ip4_cast(lhs)->sin_addr,
+ &ink_inet_ip4_cast(rhs)->sin_addr,
+ sizeof(sockaddr_in::sin_addr)
+ );
+ } else if (AF_INET6 == rtype) {
+ zret = -1; // IPv4 addresses are before IPv6
+ } else {
+ ink_assert(false); // Comparing an IPv4 address to non-IP.
+ }
+ } else if (AF_INET6 == ltype) {
+ if (AF_INET == rtype) {
+ zret = 1; // IPv6 always greater than IPv4
+ } else if (AF_INET6 == rtype) {
+ zret = memcmp(
+ &ink_inet_ip6_cast(lhs)->sin6_addr,
+ &ink_inet_ip6_cast(rhs)->sin6_addr,
+ sizeof(sockaddr_in6::sin6_addr)
+ );
+ }
+ } else {
+ ink_assert(false); // Compare only works for IP presently.
+ }
+
+ return zret;
+}
+/** Compare two addresses.
+ This works only for IP addresses (IPv4, IPv6). A comparison bewteen
+ IPv4 and IPv6 will always return the IPv4 address as lesser.
+ @note Convenience overload.
+ @return
+ - -1 if @a lhs is less than @a rhs.
+ - 0 if @a lhs is identical to @a rhs.
+ - 1 if @a lhs is greater than @a rhs.
+ @internal This looks like a lot of code for an inline but I think it
+ should compile down quite a bit.
+*/
+inline int ink_inet_cmp(
+ sockaddr_storage const& lhs, ///< Left hand operand.
+ sockaddr_storage const& rhs ///< Right hand operand.
+) {
+ return ink_inet_cmp(&lhs, &rhs);
+}
+
+/// Equality.
+/// @return @c true if @a lhs and @a rhs are identical.
+inline bool operator == (
+ sockaddr_storage const& lhs, ///< Left operand.
+ sockaddr_storage const& rhs ///< Right operand.
+) {
+ return 0 == ink_inet_cmp(lhs, rhs);
+}
+/// Inequality.
+/// @return @c false if @a lhs and @a rhs are identical.
+inline bool operator != (
+ sockaddr_storage const& lhs, ///< Left operand.
+ sockaddr_storage const& rhs ///< Right operand.
+) {
+ return 0 != ink_inet_cmp(lhs, rhs);
+}
+/// Less than.
+/// @return @c true iff @a lhs < @a rhs.
+inline bool operator < (
+ sockaddr_storage const& lhs, ///< Left operand.
+ sockaddr_storage const& rhs ///< Right operand.
+) {
+ return -1 == ink_inet_cmp(lhs, rhs);
+}
+/// Less than or equal.
+/// @return @c true iff @a lhs < @a rhs.
+inline bool operator <= (
+ sockaddr_storage const& lhs, ///< Left operand.
+ sockaddr_storage const& rhs ///< Right operand.
+) {
+ return 1 != ink_inet_cmp(lhs, rhs);
+}
+//@}
+
+/// Get IP TCP/UDP port.
+/// @return The port in host order for an IPv4 or IPv6 address,
+/// or zero if neither.
+inline uint16_t ink_inet_get_port(
+ sockaddr_storage const* addr ///< Address with port.
+) {
+ // We can discard the const because this function returns
+ // by value.
+ return ntohs(ink_inet_port_cast(const_cast<sockaddr_storage&>(*addr)));
+}
+/// Get IP TCP/UDP port.
+/// @note Convenience overload.
+/// @return The port in host order for an IPv4 or IPv6 address,
+/// or zero if neither.
+inline uint16_t ink_inet_get_port(
+ sockaddr_storage const& addr ///< Address with port.
+) {
+ return ink_inet_get_port(&addr);
+}
+
+/** Extract the IPv4 address.
+ @return Host order IPv4 address.
+*/
+inline uint32_t ink_inet_get_ip4_addr(
+ sockaddr_storage const* addr ///< Address object.
+) {
+ return ntohl(ink_inet_ip4_addr_cast(const_cast<sockaddr_storage*>(addr)));
+}
+
+/// Write IPv4 data to a @c sockaddr_storage.
+inline void ink_inet_ip4_set(
+ sockaddr_storage* ss, ///< Destination storage.
+ uint32_t ip4, ///< address, IPv4 network order.
+ uint16_t port = 0 ///< port, network order.
+) {
+ sockaddr_in* sin = ink_inet_ip4_cast(ss);
+ memset(sin, 0, sizeof(*sin));
+ sin->sin_family = AF_INET;
+ memcpy(&(sin->sin_addr), &ip4, sizeof(ip4));
+ sin->sin_port = port;
+}
+/// Write IPv4 data to a @c sockaddr_storage.
+/// @note Convenience overload.
+inline void ink_inet_ip4_set(
+ sockaddr_storage& ss, ///< Destination storage.
+ uint32_t ip4, ///< address, IPv4 network order.
+ uint16_t port = 0 ///< port, network order.
+) {
+ ink_inet_ip4_set(&ss, ip4, port);
+}
+
+/** Just the address.
+ In some cases we want to store just the address and not the
+ ancillary information (such as port, or flow data) in
+ @c sockaddr_storage.
+ @note This is not easily used as an address for system calls.
+*/
+struct InkInetAddr {
+ typedef InkInetAddr self; ///< Self reference type.
+
+ /// Default construct (invalid address).
+ InkInetAddr() : _family(AF_UNSPEC) {}
+ /// Construct as IPv4 @a addr.
+ explicit InkInetAddr(
+ uint32_t addr ///< Address to assign.
+ ) : _family(AF_INET) {
+ _addr._ip4 = addr;
+ }
+ /// Construct from @c sockaddr_storage.
+ explicit InkInetAddr(sockaddr_storage const& addr) { this->assign(&addr); }
+ /// Construct from @c sockaddr_storage.
+ explicit InkInetAddr(sockaddr_storage const* addr) { this->assign(addr); }
+
+ /// Assign sockaddr storage.
+ self& assign(sockaddr_storage const* addr) {
+ _family = addr->ss_family;
+ if (ink_inet_is_ip4(addr)) {
+ _addr._ip4 = ink_inet_ip4_addr_cast(addr);
+ } else if (ink_inet_is_ip6(addr)) {
+ memcpy(&_addr._ip6, &ink_inet_ip6_cast(addr)->sin6_addr, INK_IP6_SIZE);
+ } else {
+ _family = AF_UNSPEC;
+ }
+ return *this;
+ }
+
+ /// Assign an IPv4 address.
+# if 0
+ self& operator=(uint32_t addr) {
+ _family = AF_INET;
+ _addr._ip4 = addr;
+ return *this;
+ }
+# endif
+
+ /// Equality.
+ bool operator==(self const& that) {
+ return _family == AF_INET
+ ? (that._family == AF_INET && _addr._ip4 == that._addr._ip4)
+ : _family == AF_INET6
+ ? (that._family == AF_INET6
+ && 0 == memcmp(_addr._ip6, that._addr._ip6, INK_IP6_SIZE)
+ )
+ : (_family = AF_UNSPEC && that._family == AF_UNSPEC)
+ ;
+ }
+
+ /// Inequality.
+ bool operator!=(self const& that) {
+ return ! (*this == that);
+ }
+
+ /// Test for validity.
+ bool isValid() const { return _family == AF_INET || _family == AF_INET6; }
+
+ uint8_t _family; ///< Protocol family.
+ uint8_t _pad[3]; ///< Pad it out.
+ /// Address data.
+ union {
+ uint32_t _ip4; ///< As IPv4 address.
+ uint8_t _ip6[INK_IP6_SIZE]; ///< As IPv6 address.
+ } _addr;
+};
#endif // _ink_inet.h
Modified: trafficserver/traffic/branches/ssc/lib/ts/ink_res_init.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/ink_res_init.cc?rev=1126862&r1=1126861&r2=1126862&view=diff
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/ink_res_init.cc (original)
+++ trafficserver/traffic/branches/ssc/lib/ts/ink_res_init.cc Tue May 24 04:11:36 2011
@@ -88,6 +88,7 @@
#include "ink_string.h"
#include "ink_resolver.h"
+#include "ink_inet.h"
#if !defined(linux)
int inet_aton(register const char *cp, struct in_addr *addr);
@@ -118,98 +119,32 @@ ink_res_nclose(ink_res_state statp) {
}
static void
-ink_res_ndestroy(ink_res_state statp) {
- ink_res_nclose(statp);
- if (statp->_u._ext.ext != NULL)
- free(statp->_u._ext.ext);
- statp->options &= ~INK_RES_INIT;
- statp->_u._ext.ext = NULL;
-}
-
-static void
-ink_res_setservers(ink_res_state statp, const union ink_res_sockaddr_union *set, int cnt) {
- int i, nserv;
- size_t size;
-
+ink_res_setservers(ink_res_state statp, const sockaddr_storage *set, int cnt) {
/* close open servers */
ink_res_nclose(statp);
/* cause rtt times to be forgotten */
- statp->_u._ext.nscount = 0;
-
- nserv = 0;
- for (i = 0; i < cnt && nserv < INK_MAXNS; i++) {
- switch (set->sin.sin_family) {
- case AF_INET:
- size = sizeof(set->sin);
- if (statp->_u._ext.ext)
- memcpy(&statp->_u._ext.ext->nsaddrs[nserv], &set->sin, size);
- if (size <= sizeof(statp->nsaddr_list[nserv].sin))
- memcpy(&statp->nsaddr_list[nserv].sin, &set->sin, size);
- else
- statp->nsaddr_list[nserv].sin.sin_family = 0;
- nserv++;
- break;
-
-#ifdef HAS_INET6_STRUCTS
- case AF_INET6:
- size = sizeof(set->sin6);
- if (statp->_u._ext.ext)
- memcpy(&statp->_u._ext.ext->nsaddrs[nserv], &set->sin6, size);
- if (size <= sizeof(statp->nsaddr_list[nserv].sin6))
- memcpy(&statp->nsaddr_list[nserv].sin6, &set->sin6, size);
- else
- statp->nsaddr_list[nserv].sin6.sin6_family = 0;
- nserv++;
- break;
-#endif
+ statp->nscount = 0;
- default:
- break;
- }
- set++;
+ int nserv = 0;
+ for ( sockaddr_storage const* limit = set + cnt ; nserv < INK_MAXNS && set < limit ; ++set ) {
+ if (ink_inet_copy(statp->nsaddr_list[nserv], *set)) ++nserv;
}
statp->nscount = nserv;
}
int
-ink_res_getservers(ink_res_state statp, union ink_res_sockaddr_union *set, int cnt) {
- int i;
- size_t size;
- u_int16_t family;
-
- for (i = 0; i < statp->nscount && i < cnt; i++) {
- if (statp->_u._ext.ext)
- family = statp->_u._ext.ext->nsaddrs[i].sin.sin_family;
- else
- family = statp->nsaddr_list[i].sin.sin_family;
-
- switch (family) {
- case AF_INET:
- size = sizeof(set->sin);
- if (statp->_u._ext.ext)
- memcpy(&set->sin, &statp->_u._ext.ext->nsaddrs[i], size);
- else
- memcpy(&set->sin, &statp->nsaddr_list[i].sin, size);
- break;
-
-#ifdef HAS_INET6_STRUCTS
- case AF_INET6:
- size = sizeof(set->sin6);
- if (statp->_u._ext.ext)
- memcpy(&set->sin6, &statp->_u._ext.ext->nsaddrs[i], size);
- else
- memcpy(&set->sin6, &statp->nsaddr_list[i].sin6, size);
- break;
-#endif
+ink_res_getservers(ink_res_state statp, sockaddr_storage *set, int cnt) {
+ int zret = 0; // return count.
+ sockaddr_storage const* src = statp->nsaddr_list;
- default:
- set->sin.sin_family = 0;
- break;
+ for (int i = 0; i < statp->nscount && i < cnt; ++i, ++src) {
+ if (ink_inet_copy(*set, *src)) {
+ ++set;
+ ++zret;
}
- set++;
}
- return (statp->nscount);
+ return zret;
}
static void
@@ -337,11 +272,17 @@ ink_res_randomid(void) {
* in the configuration file.
*
* Return 0 if completes successfully, -1 on error
+ *
+ * @internal This function has to be reachable by res_data.c but not publically.
*/
-/*% This function has to be reachable by res_data.c but not publically. */
int
-ink_res_init(ink_res_state statp, const unsigned int *pHostList, const int *pPort, const char *pDefDomain, const char *pSearchList,
- const char *pResolvConf) {
+ink_res_init(
+ ink_res_state statp, ///< State object to update.
+ sockaddr_storage const* pHostList, ///< Additional servers.
+ const char *pDefDomain, ///< Default domain (may be NULL).
+ const char *pSearchList, ///< Unknown
+ const char *pResolvConf ///< Path to configuration file.
+) {
register FILE *fp;
register char *cp, **pp;
register int n;
@@ -354,8 +295,6 @@ ink_res_init(ink_res_state statp, const
// INK_RES_SET_H_ERRNO(statp, 0);
statp->res_h_errno = 0;
- if (statp->_u._ext.ext != NULL)
- ink_res_ndestroy(statp);
statp->retrans = INK_RES_TIMEOUT;
statp->retry = INK_RES_DFLRETRY;
@@ -369,28 +308,6 @@ ink_res_init(ink_res_state statp, const
statp->_flags = 0;
statp->qhook = NULL;
statp->rhook = NULL;
- statp->_u._ext.nscount = 0;
- statp->_u._ext.ext = (struct __ink_res_state_ext*)malloc(sizeof(*statp->_u._ext.ext));
- if (statp->_u._ext.ext != NULL) {
- memset(statp->_u._ext.ext, 0, sizeof(*statp->_u._ext.ext));
- statp->_u._ext.ext->nsaddrs[0].sin = statp->nsaddr_list[0].sin;
- } else {
- /*
- * Historically res_init() rarely, if at all, failed.
- * Examples and applications exist which do not check
- * our return code. Furthermore several applications
- * simply call us to get the systems domainname. So
- * rather then immediately fail here we store the
- * failure, which is returned later, in h_errno. And
- * prevent the collection of 'nameserver' information
- * by setting maxns to 0. Thus applications that fail
- * to check our return code wont be able to make
- * queries anyhow.
- */
- // INK_RES_SET_H_ERRNO(statp, NETDB_INTERNAL);
- statp->res_h_errno = NETDB_INTERNAL;
- maxns = 0;
- }
#ifdef SOLARIS2
/*
@@ -494,12 +411,9 @@ ink_res_init(ink_res_state statp, const
/* -------------------------------------------
we must be provided with atleast a named!
------------------------------------------- */
- /* TODO we should figure out the IPV6 resolvers here. */
- while (pHostList && pHostList[nserv] != 0 && nserv < INK_MAXNS) {
- statp->nsaddr_list[nserv].sin.sin_addr.s_addr = pHostList[nserv];
- statp->nsaddr_list[nserv].sin.sin_family = AF_INET;
- statp->nsaddr_list[nserv].sin.sin_port = htons(pPort[nserv]);
- nserv++;
+ while (pHostList && ink_inet_is_ip(pHostList[nserv]) && nserv < INK_MAXNS) {
+ statp->nsaddr_list[nserv] = pHostList[nserv];
+ ++nserv;
}
#define MATCH(line, name) \
@@ -570,8 +484,6 @@ ink_res_init(ink_res_state statp, const
if (MATCH(buf, "nameserver") && nserv < maxns) {
struct addrinfo hints, *ai;
char sbuf[NI_MAXSERV];
- const size_t minsiz =
- sizeof(statp->_u._ext.ext->nsaddrs[0]);
cp = buf + sizeof("nameserver") - 1;
while (*cp == ' ' || *cp == '\t')
@@ -583,17 +495,13 @@ ink_res_init(ink_res_state statp, const
hints.ai_socktype = SOCK_DGRAM; /*dummy*/
hints.ai_flags = AI_NUMERICHOST;
sprintf(sbuf, "%d", NAMESERVER_PORT);
- if (getaddrinfo(cp, sbuf, &hints, &ai) == 0 &&
- ai->ai_addrlen <= minsiz) {
- if (statp->_u._ext.ext != NULL) {
- memcpy(&statp->_u._ext.ext->nsaddrs[nserv], ai->ai_addr, ai->ai_addrlen);
- }
- if (ai->ai_addrlen <= sizeof(statp->nsaddr_list[nserv].sin)) {
- memcpy(&statp->nsaddr_list[nserv].sin, ai->ai_addr, ai->ai_addrlen);
- } else
- statp->nsaddr_list[nserv].sin.sin_family = 0;
+ if (getaddrinfo(cp, sbuf, &hints, &ai) == 0) {
+ if (ink_inet_copy(
+ statp->nsaddr_list[nserv],
+ *ink_inet_ss_cast(ai->ai_addr)
+ ))
+ ++nserv;
freeaddrinfo(ai);
- nserv++;
}
}
continue;
Modified: trafficserver/traffic/branches/ssc/lib/ts/ink_resolver.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/branches/ssc/lib/ts/ink_resolver.h?rev=1126862&r1=1126861&r2=1126862&view=diff
==============================================================================
--- trafficserver/traffic/branches/ssc/lib/ts/ink_resolver.h (original)
+++ trafficserver/traffic/branches/ssc/lib/ts/ink_resolver.h Tue May 24 04:11:36 2011
@@ -180,19 +180,6 @@
} while (0)
#endif
-union ink_res_sockaddr_union {
- struct sockaddr_in sin;
-#ifdef IN6ADDR_ANY_INIT
- struct sockaddr_in6 sin6;
-#endif
-#ifdef ISC_ALIGN64
- int64_t __align64; /*%< 64bit alignment */
-#else
- int32_t __align32; /*%< 32bit alignment */
-#endif
- char __space[128]; /*%< max size */
-};
-
struct __ink_res_state {
int retrans; /*%< retransmission time interval */
int retry; /*%< number of times to retransmit */
@@ -202,8 +189,8 @@ struct __ink_res_state {
u_long options; /*%< option flags - see below. */
#endif
int nscount; /*%< number of name servers */
- union ink_res_sockaddr_union nsaddr_list[INK_MAXNS]; /*%< address of name server */
-#define nsaddr nsaddr_list[0] /*%< for backward compatibility */
+ sockaddr_storage nsaddr_list[INK_MAXNS]; /*%< address of name server */
+// #define nsaddr nsaddr_list[0] /*%< for backward compatibility */
u_short id; /*%< current message id */
char *dnsrch[MAXDNSRCH+1]; /*%< components of domain to search */
char defdname[256]; /*%< default domain (deprecated) */
@@ -221,24 +208,11 @@ struct __ink_res_state {
int _vcsock; /*%< PRIVATE: for res_send VC i/o */
u_int _flags; /*%< PRIVATE: see below */
u_int _pad; /*%< make _u 64 bit aligned */
- union {
- /* On an 32-bit arch this means 512b total. */
- char pad[72 - 4*sizeof (int) - 2*sizeof (void *)];
- struct {
- u_int16_t nscount;
- u_int16_t nstimes[INK_MAXNS]; /*%< ms. */
- struct __ink_res_state_ext *ext; /*%< extention for IPv6 */
- } _ext;
- } _u;
+ u_int16_t _nstimes[INK_MAXNS]; /*%< ms. */
};
typedef __ink_res_state *ink_res_state;
-struct __ink_res_state_ext {
- union ink_res_sockaddr_union nsaddrs[INK_MAXNS];
-};
-
-
-int ink_res_init(ink_res_state, const unsigned int *pHostList, const int *pPort = NULL, const char *pDefDomain = NULL,
+int ink_res_init(ink_res_state, sockaddr_storage const* pHostList, const int *pPort = NULL, const char *pDefDomain = NULL,
const char *pSearchList = NULL, const char *pResolvConf = NULL);
int ink_res_mkquery(ink_res_state, int, const char *, int, int,
const unsigned char *, int, const unsigned char *, unsigned char *, int);