http://git-wip-us.apache.org/repos/asf/trafficserver/blob/65477944/lib/ts/IntrusiveDList.h ---------------------------------------------------------------------- diff --git a/lib/ts/IntrusiveDList.h b/lib/ts/IntrusiveDList.h index b79ab10..4f38feb 100644 --- a/lib/ts/IntrusiveDList.h +++ b/lib/ts/IntrusiveDList.h @@ -1,5 +1,5 @@ -# if ! defined(TS_INTRUSIVE_DOUBLE_LIST_HEADER) -# define TS_INTRUSIVE_DOUBLE_LIST_HEADER +#if !defined(TS_INTRUSIVE_DOUBLE_LIST_HEADER) +#define TS_INTRUSIVE_DOUBLE_LIST_HEADER /** @file @@ -43,7 +43,7 @@ */ /// FreeBSD doesn't like just declaring the tag struct we need so we have to include the file. -# include <iterator> +#include <iterator> /** Intrusive doubly linked list container. @@ -94,53 +94,61 @@ which seems very wrong to me. */ -template < - typename T, ///< Type of list element. - T* (T::*N), ///< Member to use for pointer to next element. - T* (T::*P) ///< Member to use for pointer to previous element. -> class IntrusiveDList { +template <typename T, ///< Type of list element. + T *(T::*N), ///< Member to use for pointer to next element. + T *(T::*P) ///< Member to use for pointer to previous element. + > +class IntrusiveDList +{ friend class iterator; + public: typedef IntrusiveDList self; ///< Self reference type. - typedef T element_type; ///< Type of list element. - /** STL style iterator for access to elements. - */ - class iterator { + typedef T element_type; ///< Type of list element. + /** STL style iterator for access to elements. + */ + class iterator + { friend class IntrusiveDList; + public: - typedef iterator self; ///< Self reference type. - typedef T value_type; ///< Referenced type for iterator. + typedef iterator self; ///< Self reference type. + typedef T value_type; ///< Referenced type for iterator. typedef int difference_type; ///< Distance type. - typedef T* pointer; ///< Pointer to referent. - typedef T& reference; ///< Reference to referent. + typedef T *pointer; ///< Pointer to referent. + typedef T &reference; ///< Reference to referent. typedef std::bidirectional_iterator_tag iterator_category; /// Default constructor. iterator() : _list(0), _elt(0) {} /// Equality test. /// @return @c true if @c this and @a that refer to the same object. - bool operator==(self const& that) const { - return _list == that._list && _elt == that._elt; - } + bool operator==(self const &that) const { return _list == that._list && _elt == that._elt; } /// Pre-increment. /// Move to the next element in the list. /// @return The iterator. - self& operator++() { - if (_elt) _elt = _elt->*N; + self &operator++() + { + if (_elt) + _elt = _elt->*N; return *this; } /// Pre-decrement. /// Move to the previous element in the list. /// @return The iterator. - self& operator--() { - if (_elt) _elt = _elt->*P; - else if (_list) _elt = _list->_tail; + self &operator--() + { + if (_elt) + _elt = _elt->*P; + else if (_list) + _elt = _list->_tail; return *this; } /// Post-increment. /// Move to the next element in the list. /// @return The iterator value before the increment. - self operator++(int) { + self operator++(int) + { self tmp(*this); ++*this; return tmp; @@ -148,71 +156,88 @@ public: /// Post-decrement. /// Move to the previous element in the list. /// @return The iterator value before the decrement. - self operator--(int) { + self operator--(int) + { self tmp(*this); ++*this; return tmp; } /// Inequality test. /// @return @c true if @c this and @a do not refer to the same object. - bool operator!=(self const& that) const { return !(*this == that); } + bool operator!=(self const &that) const { return !(*this == that); } /// Dereference. /// @return A reference to the referent. reference operator*() { return *_elt; } /// Dereference. /// @return A pointer to the referent. pointer operator->() { return _elt; } + protected: - IntrusiveDList* _list; ///< List for this iterator. - T* _elt; ///< Referenced element. + IntrusiveDList *_list; ///< List for this iterator. + T *_elt; ///< Referenced element. /// Internal constructor for containers. - iterator( - IntrusiveDList* container, ///< Container for iteration. - T* elt ///< Initial referent - ) : _list(container), _elt(elt) { + iterator(IntrusiveDList *container, ///< Container for iteration. + T *elt ///< Initial referent + ) + : _list(container), _elt(elt) + { } }; /// Default constructor (empty list). - IntrusiveDList() : _head(0), _tail(0), _count(0) { } + IntrusiveDList() : _head(0), _tail(0), _count(0) {} /// Empty check. /// @return @c true if the list is empty. - bool isEmpty() const { return 0 == _head; } + bool + isEmpty() const + { + return 0 == _head; + } /// Add @a elt as the first element in the list. /// @return This container. - self& prepend( - T* elt ///< Element to add. - ) { + self & + prepend(T *elt ///< Element to add. + ) + { elt->*N = _head; elt->*P = 0; - if (_head) _head->*P = elt; + if (_head) + _head->*P = elt; _head = elt; - if (! _tail) _tail = _head; // empty to non-empty transition + if (!_tail) + _tail = _head; // empty to non-empty transition ++_count; return *this; } /// Add @elt as the last element in the list. /// @return This container. - self& append( - T* elt ///< Element to add. - ) { + self & + append(T *elt ///< Element to add. + ) + { elt->*N = 0; elt->*P = _tail; - if (_tail) _tail->*N = elt; + if (_tail) + _tail->*N = elt; _tail = elt; - if (! _head) _head = _tail; // empty to non-empty transition + if (!_head) + _head = _tail; // empty to non-empty transition ++_count; return *this; } /// Remove the first element of the list. /// @return A poiner to the removed item, or @c NULL if the list was empty. - T* takeHead() { - T* zret = 0; + T * + takeHead() + { + T *zret = 0; if (_head) { zret = _head; _head = _head->*N; - if (_head) _head->*P = 0; - else _tail = 0; // non-empty to empty transition. + if (_head) + _head->*P = 0; + else + _tail = 0; // non-empty to empty transition. zret->*N = 0; // erase traces of list. zret->*P = 0; --_count; @@ -221,13 +246,17 @@ public: } /// Remove the last element of the list. /// @return A poiner to the removed item, or @c NULL if the list was empty. - T* takeTail() { - T* zret = 0; + T * + takeTail() + { + T *zret = 0; if (_tail) { zret = _tail; _tail = _tail->*P = 0; - if (_tail) _tail->*N = 0; - else _head = 0; // non-empty to empty transition. + if (_tail) + _tail->*N = 0; + else + _head = 0; // non-empty to empty transition. zret->*N = 0; // erase traces of list. zret->*P = 0; --_count; @@ -238,16 +267,19 @@ public: /// The caller is responsible for ensuring @a target is in this list /// and @a elt is not in a list. /// @return This list. - self& insertAfter( - T* target, ///< Target element in list. - T* elt ///< Element to insert. - ) { + self & + insertAfter(T *target, ///< Target element in list. + T *elt ///< Element to insert. + ) + { // Should assert that !(elt->*N || elt->*P) elt->*N = target->*N; elt->*P = target; target->*N = elt; - if (elt->*N) elt->*N->*P = elt; - if (target == _tail) _tail = elt; + if (elt->*N) + elt->*N->*P = elt; + if (target == _tail) + _tail = elt; ++_count; return *this; } @@ -255,28 +287,36 @@ public: /// The caller is responsible for ensuring @a target is in this list /// and @a elt is not in a list. /// @return This list. - self& insertBefore( - T* target, ///< Target element in list. - T* elt ///< Element to insert. - ) { + self & + insertBefore(T *target, ///< Target element in list. + T *elt ///< Element to insert. + ) + { // Should assert that !(elt->*N || elt->*P) elt->*P = target->*P; elt->*N = target; target->*P = elt; - if (elt->*P) elt->*P->*N = elt; - if (target == _head) _head = elt; + if (elt->*P) + elt->*P->*N = elt; + if (target == _head) + _head = elt; ++_count; return *this; } /// Take @a elt out of this list. /// @return This list. - self& take( - T* elt ///< Element to remove. - ) { - if (elt->*P) elt->*P->*N = elt->*N; - if (elt->*N) elt->*N->*P = elt->*P; - if (elt == _head) _head = elt->*N; - if (elt == _tail) _tail = elt->*P; + self & + take(T *elt ///< Element to remove. + ) + { + if (elt->*P) + elt->*P->*N = elt->*N; + if (elt->*N) + elt->*N->*P = elt->*P; + if (elt == _head) + _head = elt->*N; + if (elt == _tail) + _tail = elt->*P; elt->*P = elt->*N = 0; --_count; return *this; @@ -284,23 +324,49 @@ public: /// Remove all elements. /// @note @b No memory management is done! /// @return This container. - self& clear() { _head = _tail = 0; _count = 0; return *this; } + self & + clear() + { + _head = _tail = 0; + _count = 0; + return *this; + } /// @return Number of elements in the list. - size_t getCount() const { return _count; } + size_t + getCount() const + { + return _count; + } /// Get an iterator to the first element. - iterator begin() { return iterator(this, _head); } + iterator + begin() + { + return iterator(this, _head); + } /// Get an iterator to past the last element. - iterator end() { return iterator(this, 0); } + iterator + end() + { + return iterator(this, 0); + } /// Get the first element. - T* getHead() { return _head; } + T * + getHead() + { + return _head; + } /// Get the last element. - T* getTail() { return _tail; } + T * + getTail() + { + return _tail; + } + protected: - T* _head; ///< First element in list. - T* _tail; ///< Last element in list. + T *_head; ///< First element in list. + T *_tail; ///< Last element in list. size_t _count; ///< # of elements in list. }; -# endif // TS_INTRUSIVE_DOUBLE_LIST_HEADER - +#endif // TS_INTRUSIVE_DOUBLE_LIST_HEADER
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/65477944/lib/ts/IntrusivePtrTest.cc ---------------------------------------------------------------------- diff --git a/lib/ts/IntrusivePtrTest.cc b/lib/ts/IntrusivePtrTest.cc index d58db69..212e8d0 100644 --- a/lib/ts/IntrusivePtrTest.cc +++ b/lib/ts/IntrusivePtrTest.cc @@ -21,32 +21,39 @@ limitations under the License. */ -# include <ts/IntrusivePtr.h> -# include <ts/IntrusiveDList.h> -# include <ts/TestBox.h> +#include <ts/IntrusivePtr.h> +#include <ts/IntrusiveDList.h> +#include <ts/TestBox.h> -namespace { // Hide our local defintions +namespace +{ // Hide our local defintions // Test class for pointers and lists. -class A : public IntrusivePtrCounter { +class A : public IntrusivePtrCounter +{ public: A() : _data(0) {} - static A*& nextPtr(A* a) { return a->_next; } - static A*& prevPtr(A* a) { return a->_prev; } + static A *& + nextPtr(A *a) + { + return a->_next; + } + static A *& + prevPtr(A *a) + { + return a->_prev; + } int _data; - A* _next; - A* _prev; + A *_next; + A *_prev; }; // Definitions to test compilation. -typedef IntrusivePtrQueue< - A, - IntrusivePtrLinkFunction<A, &A::nextPtr, &A::prevPtr> -> AList; - +typedef IntrusivePtrQueue<A, IntrusivePtrLinkFunction<A, &A::nextPtr, &A::prevPtr> > AList; } -REGRESSION_TEST(IntrusivePtr_Test_Basic)(RegressionTest* t, int atype, int* pstatus) { +REGRESSION_TEST(IntrusivePtr_Test_Basic)(RegressionTest *t, int atype, int *pstatus) +{ IntrusivePtr<A> ptr1; IntrusivePtr<A> ptr2(new A); @@ -66,10 +73,8 @@ REGRESSION_TEST(IntrusivePtr_Test_Basic)(RegressionTest* t, int atype, int* psta tb.check(ptr2->useCount() == 1, "Bad use count: expected 1 got %d", ptr2->useCount()); alist1.prepend(ptr2); tb.check(ptr2->useCount() == 2, "Bad use count: expected 2 got %d", ptr2->useCount()); - for ( AList::iterator spot = alist1.begin(), limit = alist1.end() - ; spot != limit - ; ++spot - ) { - if (spot->_data) break; + for (AList::iterator spot = alist1.begin(), limit = alist1.end(); spot != limit; ++spot) { + if (spot->_data) + break; } } http://git-wip-us.apache.org/repos/asf/trafficserver/blob/65477944/lib/ts/IpMap.cc ---------------------------------------------------------------------- diff --git a/lib/ts/IpMap.cc b/lib/ts/IpMap.cc index ce44118..67cba39 100644 --- a/lib/ts/IpMap.cc +++ b/lib/ts/IpMap.cc @@ -1,4 +1,4 @@ -# include "IpMap.h" +#include "IpMap.h" /** @file IP address map support. @@ -45,568 +45,610 @@ before we had IpAddr as a type. */ -namespace ts { namespace detail { +namespace ts +{ +namespace detail +{ + // Helper functions -// Helper functions - -inline int cmp(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) { - return memcmp(lhs.sin6_addr.s6_addr, rhs.sin6_addr.s6_addr, TS_IP6_SIZE); -} - -/// Less than. -inline bool operator<(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) { - return ts::detail::cmp(lhs, rhs) < 0; -} -inline bool operator<(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) { - return ts::detail::cmp(*lhs, rhs) < 0; -} -/// Less than. -inline bool operator<(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) { - return ts::detail::cmp(lhs, *rhs) < 0; -} -/// Equality. -inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) { - return ts::detail::cmp(lhs, *rhs) == 0; -} -/// Equality. -inline bool operator==(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) { - return ts::detail::cmp(*lhs, rhs) == 0; -} -/// Equality. -inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) { - return ts::detail::cmp(lhs, rhs) == 0; -} -/// Less than or equal. -inline bool operator<=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) { - return ts::detail::cmp(lhs, *rhs) <= 0; -} -/// Less than or equal. -inline bool operator<=(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) { - return ts::detail::cmp(lhs, rhs) <= 0; -} -/// Greater than or equal. -inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) { - return ts::detail::cmp(lhs, rhs) >= 0; -} -/// Greater than or equal. -inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) { - return ts::detail::cmp(lhs, *rhs) >= 0; -} -/// Greater than. -inline bool operator>(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) { - return ts::detail::cmp(lhs, *rhs) > 0; -} - -/** 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->clear(); } - - /** 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 - ); - - /** Fill addresses. - - This background fills using the range. All addresses in the - range that are @b not present in the map are added. No - previously present address is changed. - - @note This is useful for filling in first match tables. - - @return This object. - */ - self& fill( - ArgType min, - ArgType max, - void* data = 0 - ); - - /** 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. - ) const; - - /** Remove all addresses in the map. - - @note This is much faster than using @c unmark with a range of - all addresses. - - @return This object. - */ - self& clear(); - - /** 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); + inline int + cmp(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) + { + return memcmp(lhs.sin6_addr.s6_addr, rhs.sin6_addr.s6_addr, TS_IP6_SIZE); + } - /** 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. + /// Less than. + inline bool operator<(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) { return ts::detail::cmp(lhs, rhs) < 0; } + inline bool operator<(sockaddr_in6 const *lhs, sockaddr_in6 const &rhs) { return ts::detail::cmp(*lhs, rhs) < 0; } + /// Less than. + inline bool operator<(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) { return ts::detail::cmp(lhs, *rhs) < 0; } + /// Equality. + inline bool operator==(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) { return ts::detail::cmp(lhs, *rhs) == 0; } + /// Equality. + inline bool operator==(sockaddr_in6 const *lhs, sockaddr_in6 const &rhs) { return ts::detail::cmp(*lhs, rhs) == 0; } + /// Equality. + inline bool operator==(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) { return ts::detail::cmp(lhs, rhs) == 0; } + /// Less than or equal. + inline bool operator<=(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) { return ts::detail::cmp(lhs, *rhs) <= 0; } + /// Less than or equal. + inline bool operator<=(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) { return ts::detail::cmp(lhs, rhs) <= 0; } + /// Greater than or equal. + inline bool operator>=(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) { return ts::detail::cmp(lhs, rhs) >= 0; } + /// Greater than or equal. + inline bool operator>=(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) { return ts::detail::cmp(lhs, *rhs) >= 0; } + /// Greater than. + inline bool operator>(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) { return ts::detail::cmp(lhs, *rhs) > 0; } + + /** 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. */ - void validate(); - - /// @return The number of distinct ranges. - size_t getCount() const; - - /// Print all spans. - /// @return This map. - self& print(); - - // Helper methods. - N* prev(RBNode* n) const { return static_cast<N*>(n->_prev); } - N* next(RBNode* n) const { return static_cast<N*>(n->_next); } - N* parent(RBNode* n) const { return static_cast<N*>(n->_parent); } - N* left(RBNode* n) const { return static_cast<N*>(n->_left); } - N* right(RBNode* n) const { 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; + 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->clear(); } + + /** 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); + + /** Fill addresses. + + This background fills using the range. All addresses in the + range that are @b not present in the map are added. No + previously present address is changed. + + @note This is useful for filling in first match tables. + + @return This object. + */ + self &fill(ArgType min, ArgType max, void *data = 0); + + /** 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. + ) const; + + /** Remove all addresses in the map. + + @note This is much faster than using @c unmark with a range of + all addresses. + + @return This object. + */ + self &clear(); + + /** 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(); + + /// @return The number of distinct ranges. + size_t getCount() const; + + /// Print all spans. + /// @return This map. + self &print(); + + // Helper methods. + N * + prev(RBNode *n) const + { + return static_cast<N *>(n->_prev); + } + N * + next(RBNode *n) const + { + return static_cast<N *>(n->_next); + } + N * + parent(RBNode *n) const + { + return static_cast<N *>(n->_parent); + } + N * + left(RBNode *n) const + { + return static_cast<N *>(n->_left); + } + N * + right(RBNode *n) const + { + return static_cast<N *>(n->_right); + } + N * + getHead() + { + return static_cast<N *>(_list.getHead()); + } + N * + getTail() + { + return static_cast<N *>(_list.getTail()); } - } - return zret; -} -template < typename N > IpMapBase<N>& -IpMapBase<N>::clear() { - // Delete everything. - N* n = static_cast<N*>(_list.getHead()); - while (n) { - N* x = n; - n = next(n); - delete x; + 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; } - _list.clear(); - _root = 0; - return *this; -} -template < typename N > IpMapBase<N>& -IpMapBase<N>::fill(ArgType rmin, ArgType rmax, void* payload) { - // Rightmost node of interest with n->_min <= min. - N* n = this->lowerBound(rmin); - N* x = 0; // New node (if any). - // Need copies because we will modify these. - Metric min = N::deref(rmin); - Metric max = N::deref(rmax); - - // Handle cases involving a node of interest to the left of the - // range. - if (n) { - if (n->_min < min) { - Metric min_1 = min; - N::dec(min_1); // dec is OK because min isn't zero. - if (n->_max < min_1) { // no overlap or adj. - n = next(n); - } else if (n->_max >= max) { // incoming range is covered, just discard. - return *this; - } else if (n->_data != payload) { // different payload, clip range on left. - min = n->_max; - N::inc(min); - n = next(n); - } else { // skew overlap with same payload, use node and continue. - x = n; - n = next(n); - } + template <typename N> + IpMapBase<N> & + IpMapBase<N>::clear() + { + // Delete everything. + N *n = static_cast<N *>(_list.getHead()); + while (n) { + N *x = n; + n = next(n); + delete x; } - } else { - n = this->getHead(); + _list.clear(); + _root = 0; + return *this; } - // Work through the rest of the nodes of interest. - // Invariant: n->_min >= min - - // Careful here -- because max_plus1 might wrap we need to use it only - // if we can certain it didn't. This is done by ordering the range - // tests so that when max_plus1 is used when we know there exists a - // larger value than max. - Metric max_plus1 = max; - N::inc(max_plus1); - /* Notes: - - max (and thence max_plus1) never change during the loop. - - we must have either x != 0 or adjust min but not both. - */ - while (n) { - if (n->_data == payload) { - if (x) { - if (n->_max <= max) { - // next range is covered, so we can remove and continue. - this->remove(n); - n = next(x); - } else if (n->_min <= max_plus1) { - // Overlap or adjacent with larger max - absorb and finish. - x->setMax(n->_max); - this->remove(n); - return *this; - } else { - // have the space to finish off the range. - x->setMax(max); + template <typename N> + IpMapBase<N> & + IpMapBase<N>::fill(ArgType rmin, ArgType rmax, void *payload) + { + // Rightmost node of interest with n->_min <= min. + N *n = this->lowerBound(rmin); + N *x = 0; // New node (if any). + // Need copies because we will modify these. + Metric min = N::deref(rmin); + Metric max = N::deref(rmax); + + // Handle cases involving a node of interest to the left of the + // range. + if (n) { + if (n->_min < min) { + Metric min_1 = min; + N::dec(min_1); // dec is OK because min isn't zero. + if (n->_max < min_1) { // no overlap or adj. + n = next(n); + } else if (n->_max >= max) { // incoming range is covered, just discard. return *this; - } - } else { // not carrying a span. - if (n->_max <= max) { // next range is covered - use it. + } else if (n->_data != payload) { // different payload, clip range on left. + min = n->_max; + N::inc(min); + n = next(n); + } else { // skew overlap with same payload, use node and continue. x = n; - x->setMin(min); n = next(n); - } else if (n->_min <= max_plus1) { - n->setMin(min); - return *this; - } else { // no overlap, space to complete range. - this->insertBefore(n, new N(min, max, payload)); - return *this; } } - } else { // different payload - if (x) { - if (max < n->_min) { // range ends before n starts, done. - x->setMax(max); - return *this; - } else if (max <= n->_max) { // range ends before n, done. - x->setMaxMinusOne(n->_min); - return *this; - } else { // n is contained in range, skip over it. - x->setMaxMinusOne(n->_min); - x = 0; - min = n->_max; - N::inc(min); // OK because n->_max maximal => next is null. - n = next(n); + } else { + n = this->getHead(); + } + + // Work through the rest of the nodes of interest. + // Invariant: n->_min >= min + + // Careful here -- because max_plus1 might wrap we need to use it only + // if we can certain it didn't. This is done by ordering the range + // tests so that when max_plus1 is used when we know there exists a + // larger value than max. + Metric max_plus1 = max; + N::inc(max_plus1); + /* Notes: + - max (and thence max_plus1) never change during the loop. + - we must have either x != 0 or adjust min but not both. + */ + while (n) { + if (n->_data == payload) { + if (x) { + if (n->_max <= max) { + // next range is covered, so we can remove and continue. + this->remove(n); + n = next(x); + } else if (n->_min <= max_plus1) { + // Overlap or adjacent with larger max - absorb and finish. + x->setMax(n->_max); + this->remove(n); + return *this; + } else { + // have the space to finish off the range. + x->setMax(max); + return *this; + } + } else { // not carrying a span. + if (n->_max <= max) { // next range is covered - use it. + x = n; + x->setMin(min); + n = next(n); + } else if (n->_min <= max_plus1) { + n->setMin(min); + return *this; + } else { // no overlap, space to complete range. + this->insertBefore(n, new N(min, max, payload)); + return *this; + } } - } else { // no carry node. - if (max < n->_min) { // entirely before next span. - this->insertBefore(n, new N(min, max, payload)); - return *this; - } else { - if (min < n->_min) { // leading section, need node. - N* y = new N(min, n->_min, payload); - y->decrementMax(); - this->insertBefore(n, y); + } else { // different payload + if (x) { + if (max < n->_min) { // range ends before n starts, done. + x->setMax(max); + return *this; + } else if (max <= n->_max) { // range ends before n, done. + x->setMaxMinusOne(n->_min); + return *this; + } else { // n is contained in range, skip over it. + x->setMaxMinusOne(n->_min); + x = 0; + min = n->_max; + N::inc(min); // OK because n->_max maximal => next is null. + n = next(n); } - if (max <= n->_max) // nothing past node + } else { // no carry node. + if (max < n->_min) { // entirely before next span. + this->insertBefore(n, new N(min, max, payload)); return *this; - min = n->_max; - N::inc(min); - n = next(n); + } else { + if (min < n->_min) { // leading section, need node. + N *y = new N(min, n->_min, payload); + y->decrementMax(); + this->insertBefore(n, y); + } + if (max <= n->_max) // nothing past node + return *this; + min = n->_max; + N::inc(min); + n = next(n); + } } } } + // Invariant: min is larger than any existing range maximum. + if (x) { + x->setMax(max); + } else { + this->append(new N(min, max, payload)); + } + return *this; } - // Invariant: min is larger than any existing range maximum. - if (x) { - x->setMax(max); - } else { - this->append(new N(min, max, payload)); - } - 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. - N* y = 0; // Temporary for removing and advancing. - - // Several places it is handy to have max+1. Must be careful - // about wrapping. - Metric max_plus = N::deref(max); - N::inc(max_plus); - - /* Some subtlety - for IPv6 we overload the compare operators to do - the right thing, but we can't overload pointer - comparisons. Therefore we carefully never compare pointers in - this logic. Only @a min and @a max can be pointers, everything - else is an instance or a reference. Since there's no good reason - to compare @a min and @a max this isn't particularly tricky, but - it's good to keep in mind. If we were somewhat more clever, we - would provide static less than and equal operators in the - template class @a N and convert all the comparisons to use only - those two via static function call. - */ - /* We have lots of special cases here primarily to minimize memory - allocation by re-using an existing node as often as possible. - */ - if (n) { - // Watch for wrap. - 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. min_1 is OK because - // if there is a previous range, min is not zero. - N* p = prev(n); - if (p && p->_data == payload && p->_max == min_1) { - x = p; - n = x; // need to back up n because frame of reference moved. + 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. + N *y = 0; // Temporary for removing and advancing. + + // Several places it is handy to have max+1. Must be careful + // about wrapping. + Metric max_plus = N::deref(max); + N::inc(max_plus); + + /* Some subtlety - for IPv6 we overload the compare operators to do + the right thing, but we can't overload pointer + comparisons. Therefore we carefully never compare pointers in + this logic. Only @a min and @a max can be pointers, everything + else is an instance or a reference. Since there's no good reason + to compare @a min and @a max this isn't particularly tricky, but + it's good to keep in mind. If we were somewhat more clever, we + would provide static less than and equal operators in the + template class @a N and convert all the comparisons to use only + those two via static function call. + */ + + /* We have lots of special cases here primarily to minimize memory + allocation by re-using an existing node as often as possible. + */ + if (n) { + // Watch for wrap. + 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. min_1 is OK because + // if there is a previous range, min is not zero. + N *p = prev(n); + if (p && p->_data == payload && p->_max == min_1) { + x = p; + n = x; // need to back up n because frame of reference moved. + 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 { + // 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) { + // min_1 is safe here because n->_min < min so min is not zero. + 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) { - // 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 + // 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 { - // 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; + // Existing span covers new span but with a different payload. + // We split it, put the new span in between and we're done. + // max_plus is valid because n->_max > max. + N *r; + 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. } - } else if (n->_data == payload && n->_max >= min_1) { - // min_1 is safe here because n->_min < min so min is not zero. - 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. + 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 if (0 != (n = this->getHead()) && // at least one node in tree. + n->_data == payload && // payload matches + (n->_max <= max || n->_min <= max_plus) // overlap or adj. + ) { + // Same payload with overlap, re-use. + x = n; + n = next(n); + x->setMin(min); + if (x->_max < max) + x->setMax(max); } else { - // Existing span covers new span but with a different payload. - // We split it, put the new span in between and we're done. - // max_plus is valid because n->_max > max. - N* r; 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. + this->prepend(x); } - 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. + + // 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) { // completely covered, drop span, continue + y = n; + n = next(n); + this->remove(y); + } else if (max_plus < n->_min) { // no overlap, done. + break; + } else if (n->_data == payload) { // skew overlap or adj., same payload + x->setMax(n->_max); + y = n; + n = next(n); + this->remove(y); + } else if (n->_min <= max) { // skew overlap different payload + n->setMin(max_plus); + break; + } } - } else if (0 != (n = this->getHead()) && // at least one node in tree. - n->_data == payload && // payload matches - (n->_max <= max || n->_min <= max_plus) // overlap or adj. - ) { - // Same payload with overlap, re-use. - x = n; - n = next(n); - x->setMin(min); - if (x->_max < max) x->setMax(max); - } else { - x = new N(min, max, payload); - this->prepend(x); + + return *this; } - // 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) { // completely covered, drop span, continue - y = n; - n = next(n); - this->remove(y); - } else if (max_plus < n->_min) { // no overlap, done. - break; - } else if (n->_data == payload) { // skew overlap or adj., same payload - x->setMax(n->_max); - y = n; + 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 + if (n->_max > max) { + // request span is covered by existing span - split existing span. + x = new N(max, N::argue(n->_max), n->_data); + x->incrementMin(); + n->setMaxMinusOne(N::deref(min)); + this->insertAfter(n, x); + return *this; // done. + } else { + n->setMaxMinusOne(N::deref(min)); // just clip overlap. + } + } // else disjoint so just skip it. n = next(n); - this->remove(y); - } else if (n->_min <= max) { // skew overlap different payload - 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 - if (n->_max > max) { - // request span is covered by existing span - split existing span. - x = new N(max, N::argue(n->_max), n->_data); - x->incrementMin(); - n->setMaxMinusOne(N::deref(min)); - this->insertAfter(n, x); - return *this; // done. + // n and all subsequent spans start at >= min. + while (n) { + x = n; + n = next(n); + if (x->_max <= max) { + this->remove(x); } else { - n->setMaxMinusOne(N::deref(min)); // just clip overlap. - } - } // 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 - x->setMinPlusOne(N::deref(max)); + if (x->_min <= max) { // clip overlap + x->setMinPlusOne(N::deref(max)); + } + break; } - break; } + return *this; } - 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); + 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()); + } - _list.insertBefore(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>::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>::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> + 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) const { - 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; + template <typename N> + bool + IpMapBase<N>::contains(ArgType x, void **ptr) const + { + 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; } - return zret; -} -template < typename N > size_t IpMapBase<N>::getCount() const { return _list.getCount(); } -//---------------------------------------------------------------------------- -template <typename N> void -IpMapBase<N>::validate() { -# if 0 + template <typename N> + size_t + IpMapBase<N>::getCount() const + { + return _list.getCount(); + } + //---------------------------------------------------------------------------- + template <typename N> + void + IpMapBase<N>::validate() + { +#if 0 if (_root) _root->validate(); for ( Node* n = _list.getHead() ; n ; n = n->_next ) { Node* x; @@ -619,327 +661,382 @@ IpMapBase<N>::validate() { std::cout << "Looped node" << std::endl; } } -# endif -} +#endif + } -template <typename N> IpMapBase<N>& -IpMapBase<N>::print() { -# if 0 + 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<in_addr_t, in_addr_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* access). -*/ -class Ip4Node : public IpMap::Node, protected Ip4Span { - friend struct IpMapBase<Ip4Node>; -public: - typedef Ip4Node self; ///< Self reference type. - - /// Construct with values. - Ip4Node( - ArgType min, ///< Minimum address (host order). - ArgType max, ///< Maximum address (host order). - void* data ///< Client data. - ) : Node(data), Ip4Span(min, max) { - ats_ip4_set(ats_ip_sa_cast(&_sa._min), htonl(min)); - ats_ip4_set(ats_ip_sa_cast(&_sa._max), htonl(max)); - } - /// @return The minimum value of the interval. - virtual sockaddr const* min() const { - return ats_ip_sa_cast(&_sa._min); - } - /// @return The maximum value of the interval. - virtual sockaddr const* max() const { - return ats_ip_sa_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); +#endif 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; - } + //---------------------------------------------------------------------------- + typedef Interval<in_addr_t, in_addr_t> Ip4Span; - /** Set the maximum value to one less than @a max. - @return This object. - */ - self& setMaxMinusOne( - ArgType max ///< One more than maximum value. - ) { - return this->setMax(max-1); - } - /** Set the minimum value to one more than @a min. - @return This object. - */ - self& setMinPlusOne( - ArgType min ///< One less than minimum value. - ) { - return this->setMin(min+1); - } - /** Decremement the maximum value in place. - @return This object. + /** 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* access). */ - self& decrementMax() { - this->setMax(_max-1); - return *this; - } - /** Increment the minimum value in place. - @return This object. - */ - self& incrementMin() { - this->setMin(_min+1); - return *this; - } + class Ip4Node : public IpMap::Node, protected Ip4Span + { + friend struct IpMapBase<Ip4Node>; + + public: + typedef Ip4Node self; ///< Self reference type. + + /// Construct with values. + Ip4Node(ArgType min, ///< Minimum address (host order). + ArgType max, ///< Maximum address (host order). + void *data ///< Client data. + ) + : Node(data), Ip4Span(min, max) + { + ats_ip4_set(ats_ip_sa_cast(&_sa._min), htonl(min)); + ats_ip4_set(ats_ip_sa_cast(&_sa._max), htonl(max)); + } + /// @return The minimum value of the interval. + virtual sockaddr const * + min() const + { + return ats_ip_sa_cast(&_sa._min); + } + /// @return The maximum value of the interval. + virtual sockaddr const * + max() const + { + return ats_ip_sa_cast(&_sa._max); + } + /// Set the client data. + self & + setData(void *data ///< Client data. + ) + { + _data = data; + return *this; + } - /// Increment a metric. - static void inc( - Metric& m ///< Incremented in place. - ) { - ++m; - } + 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; + } - /// Decrement a metric. - static void dec( - Metric& m ///< Decremented in place. - ) { - --m; - } + /// 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; + } - /// @return Dereferenced @a addr. - static Metric deref( - ArgType addr ///< Argument to dereference. - ) { - return addr; - } + /** Set the maximum value to one less than @a max. + @return This object. + */ + self & + setMaxMinusOne(ArgType max ///< One more than maximum value. + ) + { + return this->setMax(max - 1); + } + /** Set the minimum value to one more than @a min. + @return This object. + */ + self & + setMinPlusOne(ArgType min ///< One less than minimum value. + ) + { + return this->setMin(min + 1); + } + /** Decremement the maximum value in place. + @return This object. + */ + self & + decrementMax() + { + this->setMax(_max - 1); + return *this; + } + /** Increment the minimum value in place. + @return This object. + */ + self & + incrementMin() + { + this->setMin(_min + 1); + return *this; + } - /// @return The argument type for the @a metric. - static ArgType argue( - Metric const& metric - ) { - return metric; - } + /// Increment a metric. + static void + inc(Metric &m ///< Incremented in place. + ) + { + ++m; + } - struct { - sockaddr_in _min; - sockaddr_in _max; - } _sa; ///< Addresses in API compliant form. + /// 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; + } -class Ip4Map : public IpMapBase<Ip4Node> { - friend class ::IpMap; -}; + /// @return The argument type for the @a metric. + static ArgType + argue(Metric const &metric) + { + return metric; + } -//---------------------------------------------------------------------------- -typedef Interval<sockaddr_in6> Ip6Span; + struct { + sockaddr_in _min; + sockaddr_in _max; + } _sa; ///< Addresses in API compliant form. + }; -/** Node for IPv6 map. -*/ -class Ip6Node : public IpMap::Node, protected Ip6Span { - friend struct IpMapBase<Ip6Node>; -public: - typedef Ip6Node self; ///< Self reference type. - /// Override @c ArgType from @c Interval because the convention - /// is to use a pointer, not a reference. - typedef Metric const* ArgType; - - /// Construct from pointers. - 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 const* min() const { - return ats_ip_sa_cast(&_min); - } - /// @return The maximum value of the interval. - virtual sockaddr const* max() const { - return ats_ip_sa_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). - ) { - ats_ip_copy(ats_ip_sa_cast(&_min), ats_ip_sa_cast(min)); - return *this; - } + class Ip4Map : public IpMapBase<Ip4Node> + { + friend class ::IpMap; + }; - /// Set the minimum value of the interval. - /// @note Convenience overload. - /// @return This interval. - self& setMin( - Metric const& min ///< Minimum value (host order). - ) { - return this->setMin(&min); - } + //---------------------------------------------------------------------------- + typedef Interval<sockaddr_in6> Ip6Span; - /// Set the maximum value of the interval. - /// @return This interval. - self& setMax( - ArgType max ///< Maximum value (host order). - ) { - ats_ip_copy(ats_ip_sa_cast(&_max), ats_ip_sa_cast(max)); - return *this; - } - /// Set the maximum value of the interval. - /// @note Convenience overload. - /// @return This interval. - self& setMax( - Metric const& max ///< Maximum value (host order). - ) { - return this->setMax(&max); - } - /** Set the maximum value to one less than @a max. - @return This object. - */ - self& setMaxMinusOne( - Metric const& max ///< One more than maximum value. - ) { - this->setMax(max); - dec(_max); - return *this; - } - /** Set the minimum value to one more than @a min. - @return This object. - */ - self& setMinPlusOne( - Metric const& min ///< One less than minimum value. - ) { - this->setMin(min); - inc(_min); - return *this; - } - /** Decremement the maximum value in place. - @return This object. - */ - self& decrementMax() { dec(_max); return *this; } - /** Increment the mininimum value in place. - @return This object. + /** Node for IPv6 map. */ - self& incrementMin() { inc(_min); return *this; } - - /// Increment a metric. - static void inc( - Metric& m ///< Incremented in place. - ) { - uint8_t* addr = m.sin6_addr.s6_addr; - uint8_t* b = addr + TS_IP6_SIZE; - // Ripple carry. Walk up the address incrementing until we don't - // have a carry. - do { - ++*--b; - } while (b > addr && 0 == *b); - } + class Ip6Node : public IpMap::Node, protected Ip6Span + { + friend struct IpMapBase<Ip6Node>; + + public: + typedef Ip6Node self; ///< Self reference type. + /// Override @c ArgType from @c Interval because the convention + /// is to use a pointer, not a reference. + typedef Metric const *ArgType; + + /// Construct from pointers. + 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 const * + min() const + { + return ats_ip_sa_cast(&_min); + } + /// @return The maximum value of the interval. + virtual sockaddr const * + max() const + { + return ats_ip_sa_cast(&_max); + } + /// Set the client data. + self & + setData(void *data ///< Client data. + ) + { + _data = data; + return *this; + } - /// Decrement a metric. - static void dec( - Metric& m ///< Decremented in place. - ) { - uint8_t* addr = m.sin6_addr.s6_addr; - uint8_t* b = addr + TS_IP6_SIZE; - // Ripple borrow. Walk up the address decrementing until we don't - // have a borrow. - 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; - } + protected: + /// Set the minimum value of the interval. + /// @return This interval. + self & + setMin(ArgType min ///< Minimum value (host order). + ) + { + ats_ip_copy(ats_ip_sa_cast(&_min), ats_ip_sa_cast(min)); + return *this; + } - /// @return The argument type for the @a metric. - static ArgType argue( - Metric const& metric - ) { - return &metric; - } + /// Set the minimum value of the interval. + /// @note Convenience overload. + /// @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). + ) + { + ats_ip_copy(ats_ip_sa_cast(&_max), ats_ip_sa_cast(max)); + return *this; + } + /// Set the maximum value of the interval. + /// @note Convenience overload. + /// @return This interval. + self & + setMax(Metric const &max ///< Maximum value (host order). + ) + { + return this->setMax(&max); + } + /** Set the maximum value to one less than @a max. + @return This object. + */ + self & + setMaxMinusOne(Metric const &max ///< One more than maximum value. + ) + { + this->setMax(max); + dec(_max); + return *this; + } + /** Set the minimum value to one more than @a min. + @return This object. + */ + self & + setMinPlusOne(Metric const &min ///< One less than minimum value. + ) + { + this->setMin(min); + inc(_min); + return *this; + } + /** Decremement the maximum value in place. + @return This object. + */ + self & + decrementMax() + { + dec(_max); + return *this; + } + /** Increment the mininimum value in place. + @return This object. + */ + self & + incrementMin() + { + inc(_min); + return *this; + } -// We declare this after the helper operators and inside this namespace -// so that the template uses these for comparisons. + /// Increment a metric. + static void + inc(Metric &m ///< Incremented in place. + ) + { + uint8_t *addr = m.sin6_addr.s6_addr; + uint8_t *b = addr + TS_IP6_SIZE; + // Ripple carry. Walk up the address incrementing until we don't + // have a carry. + do { + ++*--b; + } while (b > addr && 0 == *b); + } -class Ip6Map : public IpMapBase<Ip6Node> { - friend class ::IpMap; -}; + /// Decrement a metric. + static void + dec(Metric &m ///< Decremented in place. + ) + { + uint8_t *addr = m.sin6_addr.s6_addr; + uint8_t *b = addr + TS_IP6_SIZE; + // Ripple borrow. Walk up the address decrementing until we don't + // have a borrow. + 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; + } + + /// @return The argument type for the @a metric. + static ArgType + argue(Metric const &metric) + { + return &metric; + } + }; -}} // end ts::detail + // We declare this after the helper operators and inside this namespace + // so that the template uses these for comparisons. + + class Ip6Map : public IpMapBase<Ip6Node> + { + friend class ::IpMap; + }; +} +} // end ts::detail //---------------------------------------------------------------------------- -IpMap::~IpMap() { +IpMap::~IpMap() +{ delete _m4; delete _m6; } -inline ts::detail::Ip4Map* -IpMap::force4() { - if (!_m4) _m4 = new ts::detail::Ip4Map; +inline ts::detail::Ip4Map * +IpMap::force4() +{ + if (!_m4) + _m4 = new ts::detail::Ip4Map; return _m4; } -inline ts::detail::Ip6Map* -IpMap::force6() { - if (!_m6) _m6 = new ts::detail::Ip6Map; +inline ts::detail::Ip6Map * +IpMap::force6() +{ + if (!_m6) + _m6 = new ts::detail::Ip6Map; return _m6; } bool -IpMap::contains(sockaddr const* target, void** ptr) const { +IpMap::contains(sockaddr const *target, void **ptr) const +{ bool zret = false; if (AF_INET == target->sa_family) { zret = _m4 && _m4->contains(ntohl(ats_ip4_addr_cast(target)), ptr); @@ -950,113 +1047,109 @@ IpMap::contains(sockaddr const* target, void** ptr) const { } bool -IpMap::contains(in_addr_t target, void** ptr) const { +IpMap::contains(in_addr_t target, void **ptr) const +{ return _m4 && _m4->contains(ntohl(target), ptr); } -IpMap& -IpMap::mark( - sockaddr const* min, - sockaddr const* max, - void* data -) { +IpMap & +IpMap::mark(sockaddr const *min, sockaddr const *max, void *data) +{ ink_assert(min->sa_family == max->sa_family); if (AF_INET == min->sa_family) { - this->force4()->mark( - ntohl(ats_ip4_addr_cast(min)), - ntohl(ats_ip4_addr_cast(max)), - data - ); + this->force4()->mark(ntohl(ats_ip4_addr_cast(min)), ntohl(ats_ip4_addr_cast(max)), data); } else if (AF_INET6 == min->sa_family) { this->force6()->mark(ats_ip6_cast(min), ats_ip6_cast(max), data); } return *this; } -IpMap& -IpMap::mark(in_addr_t min, in_addr_t max, void* data) { +IpMap & +IpMap::mark(in_addr_t min, in_addr_t max, void *data) +{ this->force4()->mark(ntohl(min), ntohl(max), data); return *this; } -IpMap& -IpMap::unmark( - sockaddr const* min, - sockaddr const* max -) { +IpMap & +IpMap::unmark(sockaddr const *min, sockaddr const *max) +{ ink_assert(min->sa_family == max->sa_family); if (AF_INET == min->sa_family) { if (_m4) - _m4->unmark( - ntohl(ats_ip4_addr_cast(min)), - ntohl(ats_ip4_addr_cast(max)) - ); + _m4->unmark(ntohl(ats_ip4_addr_cast(min)), ntohl(ats_ip4_addr_cast(max))); } else if (AF_INET6 == min->sa_family) { - if (_m6) _m6->unmark(ats_ip6_cast(min), ats_ip6_cast(max)); + if (_m6) + _m6->unmark(ats_ip6_cast(min), ats_ip6_cast(max)); } return *this; } -IpMap& -IpMap::unmark(in_addr_t min, in_addr_t max) { - if (_m4) _m4->unmark(ntohl(min), ntohl(max)); +IpMap & +IpMap::unmark(in_addr_t min, in_addr_t max) +{ + if (_m4) + _m4->unmark(ntohl(min), ntohl(max)); return *this; } -IpMap& -IpMap::fill( - sockaddr const* min, - sockaddr const* max, - void* data -) { +IpMap & +IpMap::fill(sockaddr const *min, sockaddr const *max, void *data) +{ ink_assert(min->sa_family == max->sa_family); if (AF_INET == min->sa_family) { - this->force4()->fill( - ntohl(ats_ip4_addr_cast(min)), - ntohl(ats_ip4_addr_cast(max)), - data - ); + this->force4()->fill(ntohl(ats_ip4_addr_cast(min)), ntohl(ats_ip4_addr_cast(max)), data); } else if (AF_INET6 == min->sa_family) { this->force6()->fill(ats_ip6_cast(min), ats_ip6_cast(max), data); } return *this; } -IpMap& -IpMap::fill(in_addr_t min, in_addr_t max, void* data) { +IpMap & +IpMap::fill(in_addr_t min, in_addr_t max, void *data) +{ this->force4()->fill(ntohl(min), ntohl(max), data); return *this; } size_t -IpMap::getCount() const { +IpMap::getCount() const +{ size_t zret = 0; - if (_m4) zret += _m4->getCount(); - if (_m6) zret += _m6->getCount(); + if (_m4) + zret += _m4->getCount(); + if (_m6) + zret += _m6->getCount(); return zret; } -IpMap& -IpMap::clear() { - if (_m4) _m4->clear(); - if (_m6) _m6->clear(); +IpMap & +IpMap::clear() +{ + if (_m4) + _m4->clear(); + if (_m6) + _m6->clear(); return *this; } IpMap::iterator -IpMap::begin() const { - Node* x = 0; - if (_m4) x = _m4->getHead(); - if (!x && _m6) x = _m6->getHead(); +IpMap::begin() const +{ + Node *x = 0; + if (_m4) + x = _m4->getHead(); + if (!x && _m6) + x = _m6->getHead(); return iterator(this, x); } -IpMap::iterator& -IpMap::iterator::operator ++ () { +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); + Node *x = static_cast<Node *>(_node->_next); if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m4->getTail()) x = _tree->_m6->getHead(); _node = x; @@ -1064,19 +1157,21 @@ IpMap::iterator::operator ++ () { return *this; } -inline IpMap::iterator& -IpMap::iterator::operator--() { +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); + 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(); + if (_tree->_m6) + _node = _tree->_m6->getTail(); + if (!_node && _tree->_m4) + _node = _tree->_m4->getTail(); } return *this; } @@ -1084,4 +1179,3 @@ IpMap::iterator::operator--() { //---------------------------------------------------------------------------- //---------------------------------------------------------------------------- - http://git-wip-us.apache.org/repos/asf/trafficserver/blob/65477944/lib/ts/IpMap.h ---------------------------------------------------------------------- diff --git a/lib/ts/IpMap.h b/lib/ts/IpMap.h index 77bef62..5e15325 100644 --- a/lib/ts/IpMap.h +++ b/lib/ts/IpMap.h @@ -1,12 +1,12 @@ -# if ! defined(TS_IP_MAP_HEADER) -# define TS_IP_MAP_HEADER +#if !defined(TS_IP_MAP_HEADER) +#define TS_IP_MAP_HEADER -# 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> +#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> /** @file @@ -31,33 +31,37 @@ limitations under the License. */ -namespace ts { namespace detail { - +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 (storage) type. + template <typename T, ///< Metric for span. + typename A = T const & ///< Argument type. + > + struct Interval { + typedef T Metric; ///< Metric (storage) type. typedef A ArgType; ///< Type used to pass instances of @c Metric. Interval() {} ///< Default constructor. /// Construct with values. - Interval( - ArgType min, ///< Minimum value in span. - ArgType max ///< Maximum value in span. - ) : _min(min), _max(max) {} + 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. - -}} // namespace ts::detail +} +} // namespace ts::detail /** Map from IP addresses to client data. @@ -89,7 +93,8 @@ namespace ts { namespace detail { minimized. */ -class IpMap { +class IpMap +{ public: typedef IpMap self; ///< Self reference type. @@ -97,30 +102,38 @@ public: /** Public API for intervals in the map. */ - class Node : protected ts::detail::RBNode { + 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) {} + Node(void *data) : _data(data) {} /// @return Client data for the node. - virtual void* data() { return _data; } + virtual void * + data() + { + return _data; + } /// Set client data. - virtual self& setData( - void* data ///< Client data pointer to store. - ) { + virtual self & + setData(void *data ///< Client data pointer to store. + ) + { _data = data; return *this; } /// @return Minimum value of the interval. - virtual sockaddr const* min() const = 0; + virtual sockaddr const *min() const = 0; /// @return Maximum value of the interval. - virtual sockaddr const* max() const = 0; + virtual sockaddr const *max() const = 0; + protected: - void* _data; ///< Client data. + void *_data; ///< Client data. }; /** Iterator over nodes / intervals. @@ -129,105 +142,102 @@ public: used to create the iterator. The node passed to the constructor just sets the current location. */ - class iterator { + class iterator + { friend class IpMap; + public: - typedef iterator self; ///< Self reference type. - typedef Node value_type; ///< Referenced type for iterator. + 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 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* () const; //!< value operator - pointer operator -> () const; //!< dereference operator - self& operator++(); //!< next node (prefix) - self operator++(int); //!< next node (postfix) - self& operator--(); ///< previous node (prefix) - self operator--(int); ///< next node (postfix) + reference operator*() const; //!< value operator + pointer operator->() const; //!< 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; + 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); } + bool operator!=(self const &that) const { return !(*this == that); } + private: /// Construct a valid iterator. - iterator(IpMap const* tree, Node* node) : _tree(tree), _node(node) {} - IpMap const* _tree; ///< Container. - Node* _node; //!< Current node. - }; + iterator(IpMap const *tree, Node *node) : _tree(tree), _node(node) {} + IpMap const *_tree; ///< Container. + Node *_node; //!< Current node. + }; - IpMap(); ///< Default constructor. + 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 const* min, ///< Minimum value in range. - sockaddr const* max, ///< Maximum value in range. - void* data = 0 ///< Client data payload. - ); + self &mark(sockaddr const *min, ///< Minimum value in range. + sockaddr 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( - in_addr_t min, ///< Minimum address (network order). - in_addr_t max, ///< Maximum address (network order). - void* data = 0 ///< Client data. - ); + self &mark(in_addr_t min, ///< Minimum address (network order). + in_addr_t max, ///< Maximum address (network order). + void *data = 0 ///< Client data. + ); /** 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( - IpAddr const& min, ///< Minimum address (network order). - IpAddr const& max, ///< Maximum address (network order). - void* data = 0 ///< Client data. - ); + self &mark(IpAddr const &min, ///< Minimum address (network order). + IpAddr const &max, ///< Maximum address (network order). + void *data = 0 ///< Client data. + ); /** Mark an IPv4 address @a addr with @a data. This is equivalent to calling @c mark(addr, addr, data). @note Convenience overload for IPv4 addresses. @return This object. */ - self& mark( - in_addr_t addr, ///< Address (network order). - void* data = 0 ///< Client data. - ); + self &mark(in_addr_t addr, ///< Address (network order). + void *data = 0 ///< Client data. + ); /** Mark a range. All addresses in the range [ @a min , @a max ] are marked with @a data. @note Convenience overload. @return This object. */ - self& mark( - IpEndpoint const* min, ///< Minimum address (network order). - IpEndpoint const* max, ///< Maximum address (network order). - void* data = 0 ///< Client data. - ); + self &mark(IpEndpoint const *min, ///< Minimum address (network order). + IpEndpoint const *max, ///< Maximum address (network order). + void *data = 0 ///< Client data. + ); /** Mark an address @a addr with @a data. This is equivalent to calling @c mark(addr, addr, data). @note Convenience overload. @return This object. */ - self& mark( - IpEndpoint const* addr, ///< Address (network order). - void* data = 0 ///< Client data. - ); + self &mark(IpEndpoint const *addr, ///< Address (network order). + void *data = 0 ///< Client data. + ); /** Unmark addresses. @@ -236,20 +246,15 @@ public: @return This object. */ - self& unmark( - sockaddr const* min, ///< Minimum value. - sockaddr const* max ///< Maximum value. - ); + self &unmark(sockaddr const *min, ///< Minimum value. + sockaddr const *max ///< Maximum value. + ); /// Unmark addresses (overload). - self& unmark( - IpEndpoint const* min, - IpEndpoint const* max - ); + self &unmark(IpEndpoint const *min, IpEndpoint const *max); /// Unmark overload. - self& unmark( - in_addr_t min, ///< Minimum of range to unmark. - in_addr_t max ///< Maximum of range to unmark. - ); + self &unmark(in_addr_t min, ///< Minimum of range to unmark. + in_addr_t max ///< Maximum of range to unmark. + ); /** Fill addresses. @@ -262,23 +267,11 @@ public: @return This object. */ - self& fill( - sockaddr const* min, - sockaddr const* max, - void* data = 0 - ); + self &fill(sockaddr const *min, sockaddr const *max, void *data = 0); /// Fill addresses (overload). - self& fill( - IpEndpoint const* min, - IpEndpoint const* max, - void* data = 0 - ); + self &fill(IpEndpoint const *min, IpEndpoint const *max, void *data = 0); /// Fill addresses (overload). - self& fill( - in_addr_t min, - in_addr_t max, - void* data = 0 - ); + self &fill(in_addr_t min, in_addr_t max, void *data = 0); /** Test for membership. @@ -286,10 +279,9 @@ public: 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 const* target, ///< Search target (network order). - void **ptr = 0 ///< Client data return. - ) const; + bool contains(sockaddr const *target, ///< Search target (network order). + void **ptr = 0 ///< Client data return. + ) const; /** Test for membership. @@ -299,10 +291,9 @@ public: 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( - in_addr_t target, ///< Search target (network order). - void **ptr = 0 ///< Client data return. - ) const; + bool contains(in_addr_t target, ///< Search target (network order). + void **ptr = 0 ///< Client data return. + ) const; /** Test for membership. @@ -312,10 +303,9 @@ public: 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( - IpEndpoint const* target, ///< Search target (network order). - void **ptr = 0 ///< Client data return. - ) const; + bool contains(IpEndpoint const *target, ///< Search target (network order). + void **ptr = 0 ///< Client data return. + ) const; /** Test for membership. @@ -325,17 +315,16 @@ public: 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( - IpAddr const& target, ///< Search target (network order). - void **ptr = 0 ///< Client data return. - ) const; + bool contains(IpAddr const &target, ///< Search target (network order). + void **ptr = 0 ///< Client data return. + ) const; /** Remove all addresses from the map. @note This is much faster than @c unmark. @return This object. */ - self& clear(); + self &clear(); /// Iterator for first element. iterator begin() const; @@ -356,88 +345,105 @@ public: protected: /// Force the IPv4 map to exist. /// @return The IPv4 map. - ts::detail::Ip4Map* force4(); + ts::detail::Ip4Map *force4(); /// Force the IPv6 map to exist. /// @return The IPv6 map. - ts::detail::Ip6Map* force6(); - - ts::detail::Ip4Map* _m4; ///< Map of IPv4 addresses. - ts::detail::Ip6Map* _m6; ///< Map of IPv6 addresses. + ts::detail::Ip6Map *force6(); + ts::detail::Ip4Map *_m4; ///< Map of IPv4 addresses. + ts::detail::Ip6Map *_m6; ///< Map of IPv6 addresses. }; -inline IpMap& IpMap::mark(in_addr_t addr, void* data) { +inline IpMap & +IpMap::mark(in_addr_t addr, void *data) +{ return this->mark(addr, addr, data); } -inline IpMap& IpMap::mark(IpAddr const& min, IpAddr const& max, void* data) { - IpEndpoint x,y; +inline IpMap & +IpMap::mark(IpAddr const &min, IpAddr const &max, void *data) +{ + IpEndpoint x, y; x.assign(min); y.assign(max); return this->mark(&x.sa, &y.sa, data); } -inline IpMap& IpMap::mark(IpEndpoint const* addr, void* data) { +inline IpMap & +IpMap::mark(IpEndpoint const *addr, void *data) +{ return this->mark(&addr->sa, &addr->sa, data); } -inline IpMap& IpMap::mark(IpEndpoint const* min, IpEndpoint const* max, void* data) { +inline IpMap & +IpMap::mark(IpEndpoint const *min, IpEndpoint const *max, void *data) +{ return this->mark(&min->sa, &max->sa, data); } -inline IpMap& IpMap::unmark(IpEndpoint const* min, IpEndpoint const* max) { +inline IpMap & +IpMap::unmark(IpEndpoint const *min, IpEndpoint const *max) +{ return this->unmark(&min->sa, &max->sa); } -inline IpMap& IpMap::fill(IpEndpoint const* min, IpEndpoint const* max, void* data) { +inline IpMap & +IpMap::fill(IpEndpoint const *min, IpEndpoint const *max, void *data) +{ return this->fill(&min->sa, &max->sa, data); } -inline bool IpMap::contains(IpEndpoint const* target, void** ptr) const { +inline bool +IpMap::contains(IpEndpoint const *target, void **ptr) const +{ return this->contains(&target->sa, ptr); } inline bool -IpMap::contains(IpAddr const& addr, void** ptr) const { +IpMap::contains(IpAddr const &addr, void **ptr) const +{ IpEndpoint ip; ip.assign(addr); return this->contains(&ip.sa, ptr); } inline IpMap::iterator -IpMap::end() const { +IpMap::end() const +{ return iterator(this, 0); } -inline IpMap::iterator -IpMap::iterator::operator ++ (int) { +inline IpMap::iterator IpMap::iterator::operator++(int) +{ iterator old(*this); ++*this; return old; } -inline IpMap::iterator -IpMap::iterator::operator--(int) { +inline IpMap::iterator IpMap::iterator::operator--(int) +{ self tmp(*this); --*this; return tmp; } -inline bool -IpMap::iterator::operator == (iterator const& that) const { +inline bool IpMap::iterator::operator==(iterator const &that) const +{ return _tree == that._tree && _node == that._node; } -inline IpMap::iterator::reference -IpMap::iterator::operator * () const { +inline IpMap::iterator::reference IpMap::iterator::operator*() const +{ return *_node; } -inline IpMap::iterator::pointer -IpMap::iterator::operator -> () const { +inline IpMap::iterator::pointer IpMap::iterator::operator->() const +{ return _node; } -inline IpMap::IpMap() : _m4(0), _m6(0) {} +inline IpMap::IpMap() : _m4(0), _m6(0) +{ +} -# endif // TS_IP_MAP_HEADER +#endif // TS_IP_MAP_HEADER
