You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by zw...@apache.org on 2015/03/23 21:32:48 UTC
[15/52] [partial] trafficserver git commit: TS-3419 Fix some enum's
such that clang-format can handle it the way we want. Basically this means
having a trailing ,
on short enum's. TS-3419 Run clang-format over most of the source
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