4
IP address map support.
6
Provide the ability to create a range based mapping for the IP
7
address space. Addresses can be added and removed and each address
8
is associated with arbitrary client data.
10
@internal Don't bother to look at this code if you don't know how
11
a red/black tree works. There are so many good references on the
12
subject it's a waste to have some inferior version here. The
13
methods on @c Node follow the standard implementation except for
14
being parameterized by direction (so that, for instance, right
15
rotate and left rotate are both done by the @c rotate method with
16
a direction argument).
18
@section license License
20
Licensed to the Apache Software Foundation (ASF) under one
21
or more contributor license agreements. See the NOTICE file
22
distributed with this work for additional information
23
regarding copyright ownership. The ASF licenses this file
24
to you under the Apache License, Version 2.0 (the
25
"License"); you may not use this file except in compliance
26
with the License. You may obtain a copy of the License at
28
http://www.apache.org/licenses/LICENSE-2.0
30
Unless required by applicable law or agreed to in writing, software
31
distributed under the License is distributed on an "AS IS" BASIS,
32
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
33
See the License for the specific language governing permissions and
34
limitations under the License.
37
// Validation / printing disabled until I figure out how to generalize so
38
// as to not tie reporting into a particular project environment.
40
namespace ts { namespace detail {
44
inline int cmp(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
45
return memcmp(lhs.sin6_addr.s6_addr, rhs.sin6_addr.s6_addr, TS_IP6_SIZE);
49
inline bool operator<(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
50
return ts::detail::cmp(lhs, rhs) < 0;
52
inline bool operator<(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) {
53
return ts::detail::cmp(*lhs, rhs) < 0;
56
inline bool operator<(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
57
return ts::detail::cmp(lhs, *rhs) < 0;
60
inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
61
return ts::detail::cmp(lhs, *rhs) == 0;
64
inline bool operator==(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) {
65
return ts::detail::cmp(*lhs, rhs) == 0;
68
inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
69
return ts::detail::cmp(lhs, rhs) == 0;
71
/// Less than or equal.
72
inline bool operator<=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
73
return ts::detail::cmp(lhs, *rhs) <= 0;
75
/// Less than or equal.
76
inline bool operator<=(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
77
return ts::detail::cmp(lhs, rhs) <= 0;
79
/// Greater than or equal.
80
inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
81
return ts::detail::cmp(lhs, rhs) >= 0;
83
/// Greater than or equal.
84
inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
85
return ts::detail::cmp(lhs, *rhs) >= 0;
88
inline bool operator>(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
89
return ts::detail::cmp(lhs, *rhs) > 0;
93
/// @note If @a n is @c NULL it is treated as having the color @c BLACK.
94
/// @return @c true if @a c and the color of @a n are the same.
95
inline bool operator == ( RBNode* n, RBNode::Color c ) {
96
return c == ( n ? n->getColor() : RBNode::BLACK);
99
/// @note If @a n is @c NULL it is treated as having the color @c BLACK.
100
/// @return @c true if @a c and the color of @a n are the same.
101
inline bool operator == ( RBNode::Color c, RBNode* n ) {
106
RBNode::getChild(Direction d) const {
107
return d == RIGHT ? _right
114
RBNode::rotate(Direction d) {
115
self* parent = _parent; // Cache because it can change before we use it.
116
Direction child_dir = _parent ? _parent->getChildDirection(this) : NONE;
117
Direction other_dir = this->flip(d);
120
if (d != NONE && this->getChild(other_dir)) {
121
child = this->getChild(other_dir);
122
this->clearChild(other_dir);
123
this->setChild(child->getChild(d), other_dir);
124
child->clearChild(d);
125
child->setChild(this, d);
126
child->structureFixup();
127
this->structureFixup();
129
parent->clearChild(child_dir);
130
parent->setChild(child, child_dir);
139
RBNode::setChild(self* n, Direction d) {
140
if (n) n->_parent = this;
141
if (d == RIGHT) _right = n;
142
else if (d == LEFT) _left = n;
146
// Returns the root node
148
RBNode::rippleStructureFixup() {
149
self* root = this; // last node seen, root node at the end
160
RBNode::replaceWith(self* n) {
163
Direction d = _parent->getChildDirection(this);
164
_parent->setChild(0, d);
165
if (_parent != n) _parent->setChild(n, d);
169
n->_left = n->_right = 0;
170
if (_left && _left != n) n->setChild(_left, LEFT);
171
if (_right && _right != n) n->setChild(_right, RIGHT);
175
/* Rebalance the tree. This node is the unbalanced node. */
177
RBNode::rebalanceAfterInsert() {
178
self* x(this); // the node with the imbalance
180
while (x && x->_parent == RED) {
181
Direction child_dir = NONE;
183
if (x->_parent->_parent)
184
child_dir = x->_parent->_parent->getChildDirection(x->_parent);
187
Direction other_dir(flip(child_dir));
189
self* y = x->_parent->_parent->getChild(other_dir);
191
x->_parent->_color = BLACK;
193
x = x->_parent->_parent;
196
if (x->_parent->getChild(other_dir) == x) {
198
x->rotate(child_dir);
200
// Note setting the parent color to BLACK causes the loop to exit.
201
x->_parent->_color = BLACK;
202
x->_parent->_parent->_color = RED;
203
x->_parent->_parent->rotate(other_dir);
207
// every node above this one has a subtree structure change,
208
// so notify it. serendipitously, this makes it easy to return
209
// the new root node.
210
self* root = this->rippleStructureFixup();
211
root->_color = BLACK;
217
// Returns new root node
220
self* root = 0; // new root node, returned to caller
222
/* Handle two special cases first.
223
- This is the only node in the tree, return a new root of NIL
224
- This is the root node with only one child, return that child as new root
226
if (!_parent && !(_left && _right)) {
230
root->_color = BLACK;
234
root->_color = BLACK;
235
} // else that was the only node, so leave @a root @c NULL.
239
/* The node to be removed from the tree.
240
If @c this (the target node) has both children, we remove
241
its successor, which cannot have a left child and
242
put that node in place of the target node. Otherwise this
243
node has at most one child, so we can remove it.
244
Note that the successor of a node with a right child is always
245
a right descendant of the node. Therefore, remove_node
246
is an element of the tree rooted at this node.
247
Because of the initial special case checks, we know
248
that remove_node is @b not the root node.
250
self* remove_node(_left && _right ? _next : this);
252
// This is the color of the node physically removed from the tree.
253
// Normally this is the color of @a remove_node
254
Color remove_color = remove_node->_color;
255
// Need to remember the direction from @a remove_node to @a splice_node
258
// The child node that will be promoted to replace the removed node.
259
// The choice of left or right is irrelevant, as remove_node has at
260
// most one child (and splice_node may be NIL if remove_node has no
262
self* splice_node(remove_node->_left
264
: remove_node->_right
268
// @c replace_with copies color so in this case the actual color
269
// lost is that of the splice_node.
270
remove_color = splice_node->_color;
271
remove_node->replaceWith(splice_node);
273
// No children on remove node so we can just clip it off the tree
274
// We update splice_node to maintain the invariant that it is
275
// the node where the physical removal occurred.
276
splice_node = remove_node->_parent;
277
// Keep @a d up to date.
278
d = splice_node->getChildDirection(remove_node);
279
splice_node->setChild(0, d);
282
// If the node to pull out of the tree isn't this one,
283
// then replace this node in the tree with that removed
284
// node in liu of copying the data over.
285
if (remove_node != this) {
286
// Don't leave @a splice_node referring to a removed node
287
if (splice_node == this) splice_node = remove_node;
288
this->replaceWith(remove_node);
291
root = splice_node->rebalanceAfterRemove(remove_color, d);
292
root->_color = BLACK;
297
* Rebalance tree after a deletion
298
* Called on the spliced in node or its parent, whichever is not NIL.
299
* This modifies the tree structure only if @a c is @c BLACK.
302
RBNode::rebalanceAfterRemove(
303
Color c, //!< The color of the removed node
304
Direction d //!< Direction of removed node from its parent
308
if (BLACK == c) { // only rebalance if too much black
310
self* parent = n->_parent;
312
// If @a direction is set, then we need to start at a leaf psuedo-node.
313
// This is why we need @a parent, otherwise we could just use @a n.
319
while (parent) { // @a n is not the root
320
// If the current node is RED, we can just recolor and be done
325
// Parameterizing the rebalance logic on the directions. We
326
// write for the left child case and flip directions for the
328
Direction near(LEFT), far(RIGHT);
330
(NONE == d && parent->getChildDirection(n) == RIGHT)
337
self* w = parent->getChild(far); // sibling(n)
339
if (w->_color == RED) {
341
parent->_color = RED;
342
parent->rotate(near);
343
w = parent->getChild(far);
346
self* wfc = w->getChild(far);
347
if (w->getChild(near) == BLACK && wfc == BLACK) {
351
d = NONE; // Cancel any leaf node logic
353
if (wfc->_color == BLACK) {
354
w->getChild(near)->_color = BLACK;
357
w = parent->getChild(far);
358
wfc = w->getChild(far); // w changed, update far child cache.
360
w->_color = parent->_color;
361
parent->_color = BLACK;
363
parent->rotate(near);
369
root = this->rippleStructureFixup();
373
/** Ensure that the local information associated with each node is
374
correct globally This should only be called on debug builds as it
375
breaks any efficiencies we have gained from our tree structure.
381
int black_ht1, black_ht2;
384
black_ht1 = _left->validate();
389
if (black_ht1 > 0 && _right)
390
black_ht2 = _right->validate();
394
if (black_ht1 == black_ht2) {
395
black_ht = black_ht1;
396
if (this->_color == BLACK)
401
else if (_right == RED)
404
std::cout << "Red-red child\n";
407
std::cout << "Height mismatch " << black_ht1 << " " << black_ht2 << "\n";
409
if (black_ht > 0 && !this->structureValidate())
418
/** Base template class for IP maps.
419
This class is templated by the @a N type which must be a subclass
420
of @c RBNode. This class carries information about the addresses stored
421
in the map. This includes the type, the common argument type, and
422
some utility methods to operate on the address.
425
typename N ///< Node type.
427
friend class ::IpMap;
429
typedef IpMapBase self; ///< Self reference type.
430
typedef typename N::ArgType ArgType; ///< Import type.
431
typedef typename N::Metric Metric; ///< Import type.g482
433
IpMapBase() : _root(0) {}
434
~IpMapBase() { this->clear(); }
437
All addresses in the range [ @a min , @a max ] are marked with @a data.
441
ArgType min, ///< Minimum value in range.
442
ArgType max, ///< Maximum value in range.
443
void* data = 0 ///< Client data payload.
445
/** Unmark addresses.
447
All addresses in the range [ @a min , @a max ] are cleared
448
(removed from the map), no longer marked.
459
This background fills using the range. All addresses in the
460
range that are @b not present in the map are added. No
461
previously present address is changed.
463
@note This is useful for filling in first match tables.
473
/** Test for membership.
475
@return @c true if the address is in the map, @c false if not.
476
If the address is in the map and @a ptr is not @c NULL, @c *ptr
477
is set to the client data for the address.
480
ArgType target, ///< Search target value.
481
void **ptr = 0 ///< Client data return.
484
/** Remove all addresses in the map.
486
@note This is much faster than using @c unmark with a range of
493
/** Lower bound for @a target. @return The node whose minimum value
494
is the largest that is not greater than @a target, or @c NULL if
495
all minimum values are larger than @a target.
497
N* lowerBound(ArgType target);
499
/** Insert @a n after @a spot.
500
Caller is responsible for ensuring that @a spot is in this container
501
and the proper location for @a n.
504
N* spot, ///< Node in list.
505
N* n ///< Node to insert.
507
/** Insert @a n before @a spot.
508
Caller is responsible for ensuring that @a spot is in this container
509
and the proper location for @a n.
512
N* spot, ///< Node in list.
513
N* n ///< Node to insert.
515
/// Add node @a n as the first node.
519
/// Add node @a n as the last node.
525
N* n ///< Node to remove.
528
/** Validate internal data structures.
529
@note Intended for debugging, not general client use.
533
/// @return The number of distinct ranges.
534
size_t getCount() const;
537
/// @return This map.
541
N* prev(RBNode* n) const { return static_cast<N*>(n->_prev); }
542
N* next(RBNode* n) const { return static_cast<N*>(n->_next); }
543
N* parent(RBNode* n) const { return static_cast<N*>(n->_parent); }
544
N* left(RBNode* n) const { return static_cast<N*>(n->_left); }
545
N* right(RBNode* n) const { return static_cast<N*>(n->_right); }
546
N* getHead() { return static_cast<N*>(_list.getHead()); }
547
N* getTail() { return static_cast<N*>(_list.getTail()); }
549
N* _root; ///< Root node.
550
/// In order list of nodes.
551
/// For ugly compiler reasons, this is a list of base class pointers
552
/// even though we really store @a N instances on it.
553
typedef IntrusiveDList<RBNode, &RBNode::_next, &RBNode::_prev> NodeList;
554
/// This keeps track of all allocated nodes in order.
555
/// Iteration depends on this list being maintained.
559
template < typename N > N*
560
IpMapBase<N>::lowerBound(ArgType target) {
561
N* n = _root; // current node to test.
562
N* zret = 0; // best node so far.
564
if (target < n->_min) n = left(n);
566
zret = n; // this is a better candidate.
567
if (n->_max < target) n = right(n);
574
template < typename N > IpMapBase<N>&
575
IpMapBase<N>::clear() {
576
// Delete everything.
577
N* n = static_cast<N*>(_list.getHead());
588
template < typename N > IpMapBase<N>&
589
IpMapBase<N>::fill(ArgType rmin, ArgType rmax, void* payload) {
590
// Rightmost node of interest with n->_min <= min.
591
N* n = this->lowerBound(rmin);
592
N* x = 0; // New node (if any).
593
// Need copies because we will modify these.
594
Metric min = N::deref(rmin);
595
Metric max = N::deref(rmax);
597
// Handle cases involving a node of interest to the left of the
602
N::dec(min_1); // dec is OK because min isn't zero.
603
if (n->_max < min_1) { // no overlap or adj.
605
} else if (n->_max >= max) { // incoming range is covered, just discard.
607
} else if (n->_data != payload) { // different payload, clip range on left.
611
} else { // skew overlap with same payload, use node and continue.
620
// Work through the rest of the nodes of interest.
621
// Invariant: n->_min >= min
623
// Careful here -- because max_plus1 might wrap we need to use it only
624
// if we can certain it didn't. This is done by ordering the range
625
// tests so that when max_plus1 is used when we know there exists a
626
// larger value than max.
627
Metric max_plus1 = max;
630
- max (and thence max_plus1) never change during the loop.
631
- we must have either x != 0 or adjust min but not both.
634
if (n->_data == payload) {
636
if (n->_max <= max) {
637
// next range is covered, so we can remove and continue.
640
} else if (n->_min <= max_plus1) {
641
// Overlap or adjacent with larger max - absorb and finish.
646
// have the space to finish off the range.
650
} else { // not carrying a span.
651
if (n->_max <= max) { // next range is covered - use it.
655
} else if (n->_min <= max_plus1) {
658
} else { // no overlap, space to complete range.
659
this->insertBefore(n, new N(min, max, payload));
663
} else { // different payload
665
if (max < n->_min) { // range ends before n starts, done.
668
} else if (max <= n->_max) { // range ends before n, done.
669
x->setMaxMinusOne(n->_min);
671
} else { // n is contained in range, skip over it.
672
x->setMaxMinusOne(n->_min);
675
N::inc(min); // OK because n->_max maximal => next is null.
678
} else { // no carry node.
679
if (max < n->_min) { // entirely before next span.
680
this->insertBefore(n, new N(min, max, payload));
683
if (min < n->_min) { // leading section, need node.
684
N* y = new N(min, n->_min, payload);
686
this->insertBefore(n, y);
688
if (max <= n->_max) // nothing past node
697
// Invariant: min is larger than any existing range maximum.
701
this->append(new N(min, max, payload));
706
template < typename N > IpMapBase<N>&
707
IpMapBase<N>::mark(ArgType min, ArgType max, void* payload) {
708
N* n = this->lowerBound(min); // current node.
709
N* x = 0; // New node, gets set if we re-use an existing one.
710
N* y = 0; // Temporary for removing and advancing.
712
// Several places it is handy to have max+1. Must be careful
714
Metric max_plus = N::deref(max);
717
/* Some subtlety - for IPv6 we overload the compare operators to do
718
the right thing, but we can't overload pointer
719
comparisons. Therefore we carefully never compare pointers in
720
this logic. Only @a min and @a max can be pointers, everything
721
else is an instance or a reference. Since there's no good reason
722
to compare @a min and @a max this isn't particularly tricky, but
723
it's good to keep in mind. If we were somewhat more clever, we
724
would provide static less than and equal operators in the
725
template class @a N and convert all the comparisons to use only
726
those two via static function call.
729
/* We have lots of special cases here primarily to minimize memory
730
allocation by re-using an existing node as often as possible.
734
Metric min_1 = N::deref(min);
736
if (n->_min == min) {
737
// Could be another span further left which is adjacent.
738
// Coalesce if the data is the same. min_1 is OK because
739
// if there is a previous range, min is not zero.
741
if (p && p->_data == payload && p->_max == min_1) {
743
n = x; // need to back up n because frame of reference moved.
745
} else if (n->_max <= max) {
746
// Span will be subsumed by request span so it's available for use.
748
x->setMax(max).setData(payload);
749
} else if (n->_data == payload) {
750
return *this; // request is covered by existing span with the same data
752
// request span is covered by existing span.
753
x = new N(min, max, payload); //
754
n->setMin(max_plus); // clip existing.
755
this->insertBefore(n, x);
758
} else if (n->_data == payload && n->_max >= min_1) {
759
// min_1 is safe here because n->_min < min so min is not zero.
761
// If the existing span covers the requested span, we're done.
762
if (x->_max >= max) return *this;
764
} else if (n->_max <= max) {
765
// Can only have left skew overlap, otherwise disjoint.
767
if (n->_max >= min) n->setMax(min_1);
768
else if (next(n) && n->_max <= max) {
769
// request region covers next span so we can re-use that node.
771
x->setMin(min).setMax(max).setData(payload);
772
n = x; // this gets bumped again, which is correct.
775
// Existing span covers new span but with a different payload.
776
// We split it, put the new span in between and we're done.
777
// max_plus is valid because n->_max > max.
779
x = new N(min, max, payload);
780
r = new N(max_plus, n->_max, n->_data);
782
this->insertAfter(n, x);
783
this->insertAfter(x, r);
784
return *this; // done.
786
n = next(n); // lower bound span handled, move on.
788
x = new N(min, max, payload);
789
if (n) this->insertBefore(n, x);
790
else this->append(x); // note that since n == 0 we'll just return.
792
} else if (0 != (n = this->getHead()) && // at least one node in tree.
793
n->_data == payload && // payload matches
794
(n->_max <= max || n->_min <= max_plus) // overlap or adj.
796
// Same payload with overlap, re-use.
800
if (x->_max < max) x->setMax(max);
802
x = new N(min, max, payload);
806
// At this point, @a x has the node for this span and all existing spans of
807
// interest start at or past this span.
809
if (n->_max <= max) { // completely covered, drop span, continue
813
} else if (max_plus < n->_min) { // no overlap, done.
815
} else if (n->_data == payload) { // skew overlap or adj., same payload
820
} else if (n->_min <= max) { // skew overlap different payload
829
template <typename N> IpMapBase<N>&
830
IpMapBase<N>::unmark(ArgType min, ArgType max) {
831
N* n = this->lowerBound(min);
832
N* x; // temp for deletes.
834
// Need to handle special case where first span starts to the left.
835
if (n && n->_min < min) {
836
if (n->_max >= min) { // some overlap
838
// request span is covered by existing span - split existing span.
839
x = new N(max, N::argue(n->_max), n->_data);
841
n->setMaxMinusOne(N::deref(min));
842
this->insertAfter(n, x);
843
return *this; // done.
845
n->setMaxMinusOne(N::deref(min)); // just clip overlap.
847
} // else disjoint so just skip it.
850
// n and all subsequent spans start at >= min.
854
if (x->_max <= max) {
857
if (x->_min <= max) { // clip overlap
858
x->setMinPlusOne(N::deref(max));
866
template <typename N> void
867
IpMapBase<N>::insertAfter(N* spot, N* n) {
869
if (!c) spot->setChild(n, N::RIGHT);
870
else spot->_next->setChild(n, N::LEFT);
872
_list.insertAfter(spot, n);
873
_root = static_cast<N*>(n->rebalanceAfterInsert());
876
template <typename N> void
877
IpMapBase<N>::insertBefore(N* spot, N* n) {
879
if (!c) spot->setChild(n, N::LEFT);
880
else spot->_prev->setChild(n, N::RIGHT);
882
_list.insertBefore(spot, n);
883
_root = static_cast<N*>(n->rebalanceAfterInsert());
886
template <typename N> void
887
IpMapBase<N>::prepend(N* n) {
888
if (!_root) _root = n;
889
else _root = static_cast<N*>(_list.getHead()->setChild(n, N::LEFT)->rebalanceAfterInsert());
893
template <typename N> void
894
IpMapBase<N>::append(N* n) {
895
if (!_root) _root = n;
896
else _root = static_cast<N*>(_list.getTail()->setChild(n, N::RIGHT)->rebalanceAfterInsert());
900
template <typename N> void
901
IpMapBase<N>::remove(N* n) {
902
_root = static_cast<N*>(n->remove());
907
template <typename N> bool
908
IpMapBase<N>::contains(ArgType x, void** ptr) const {
910
N* n = _root; // current node to test.
912
if (x < n->_min) n = left(n);
913
else if (n->_max < x) n = right(n);
915
if (ptr) *ptr = n->_data;
923
template < typename N > size_t IpMapBase<N>::getCount() const { return _list.getCount(); }
924
//----------------------------------------------------------------------------
925
template <typename N> void
926
IpMapBase<N>::validate() {
928
if (_root) _root->validate();
929
for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
931
if (0 != (x = n->_next)) {
933
std::cout << "Broken list" << std::endl;
934
if (n->_max >= x->_min)
935
std::cout << "Out of order - " << n->_max << " > " << x->_min << std::endl;
936
if (n->_parent == n || n->_left == n || n->_right == n)
937
std::cout << "Looped node" << std::endl;
943
template <typename N> IpMapBase<N>&
944
IpMapBase<N>::print() {
946
for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
948
<< n << ": " << n->_min << '-' << n->_max << " [" << n->_data << "] "
949
<< (n->_color == Node::BLACK ? "Black " : "Red ") << "P=" << n->_parent << " L=" << n->_left << " R=" << n->_right
956
//----------------------------------------------------------------------------
957
typedef Interval<in_addr_t, in_addr_t> Ip4Span;
959
/** Node for IPv4 map.
960
We store the address in host order in the @a _min and @a _max
961
members for performance. We store copies in the @a _sa member
962
for API compliance (which requires @c sockaddr* access).
964
class Ip4Node : public IpMap::Node, protected Ip4Span {
965
friend struct IpMapBase<Ip4Node>;
967
typedef Ip4Node self; ///< Self reference type.
969
/// Construct with values.
971
ArgType min, ///< Minimum address (host order).
972
ArgType max, ///< Maximum address (host order).
973
void* data ///< Client data.
974
) : Node(data), Ip4Span(min, max) {
975
ats_ip4_set(ats_ip_sa_cast(&_sa._min), htonl(min));
976
ats_ip4_set(ats_ip_sa_cast(&_sa._max), htonl(max));
978
/// @return The minimum value of the interval.
979
virtual sockaddr const* min() const {
980
return ats_ip_sa_cast(&_sa._min);
982
/// @return The maximum value of the interval.
983
virtual sockaddr const* max() const {
984
return ats_ip_sa_cast(&_sa._max);
986
/// Set the client data.
988
void* data ///< Client data.
995
/// Set the minimum value of the interval.
996
/// @return This interval.
998
ArgType min ///< Minimum value (host order).
1001
_sa._min.sin_addr.s_addr = htonl(min);
1005
/// Set the maximum value of the interval.
1006
/// @return This interval.
1008
ArgType max ///< Maximum value (host order).
1011
_sa._max.sin_addr.s_addr = htonl(max);
1015
/** Set the maximum value to one less than @a max.
1016
@return This object.
1018
self& setMaxMinusOne(
1019
ArgType max ///< One more than maximum value.
1021
return this->setMax(max-1);
1023
/** Set the minimum value to one more than @a min.
1024
@return This object.
1026
self& setMinPlusOne(
1027
ArgType min ///< One less than minimum value.
1029
return this->setMin(min+1);
1031
/** Decremement the maximum value in place.
1032
@return This object.
1034
self& decrementMax() {
1035
this->setMax(_max-1);
1038
/** Increment the minimum value in place.
1039
@return This object.
1041
self& incrementMin() {
1042
this->setMin(_min+1);
1046
/// Increment a metric.
1048
Metric& m ///< Incremented in place.
1053
/// Decrement a metric.
1055
Metric& m ///< Decremented in place.
1060
/// @return Dereferenced @a addr.
1061
static Metric deref(
1062
ArgType addr ///< Argument to dereference.
1067
/// @return The argument type for the @a metric.
1068
static ArgType argue(
1069
Metric const& metric
1077
} _sa; ///< Addresses in API compliant form.
1081
class Ip4Map : public IpMapBase<Ip4Node> {
1082
friend class ::IpMap;
1085
//----------------------------------------------------------------------------
1086
typedef Interval<sockaddr_in6> Ip6Span;
1088
/** Node for IPv6 map.
1090
class Ip6Node : public IpMap::Node, protected Ip6Span {
1091
friend struct IpMapBase<Ip6Node>;
1093
typedef Ip6Node self; ///< Self reference type.
1094
/// Override @c ArgType from @c Interval because the convention
1095
/// is to use a pointer, not a reference.
1096
typedef Metric const* ArgType;
1098
/// Construct from pointers.
1100
ArgType min, ///< Minimum address (network order).
1101
ArgType max, ///< Maximum address (network order).
1102
void* data ///< Client data.
1103
) : Node(data), Ip6Span(*min, *max) {
1105
/// Construct with values.
1107
Metric const& min, ///< Minimum address (network order).
1108
Metric const& max, ///< Maximum address (network order).
1109
void* data ///< Client data.
1110
) : Node(data), Ip6Span(min, max) {
1112
/// @return The minimum value of the interval.
1113
virtual sockaddr const* min() const {
1114
return ats_ip_sa_cast(&_min);
1116
/// @return The maximum value of the interval.
1117
virtual sockaddr const* max() const {
1118
return ats_ip_sa_cast(&_max);
1120
/// Set the client data.
1122
void* data ///< Client data.
1129
/// Set the minimum value of the interval.
1130
/// @return This interval.
1132
ArgType min ///< Minimum value (host order).
1134
ats_ip_copy(ats_ip_sa_cast(&_min), ats_ip_sa_cast(min));
1138
/// Set the minimum value of the interval.
1139
/// @note Convenience overload.
1140
/// @return This interval.
1142
Metric const& min ///< Minimum value (host order).
1144
return this->setMin(&min);
1147
/// Set the maximum value of the interval.
1148
/// @return This interval.
1150
ArgType max ///< Maximum value (host order).
1152
ats_ip_copy(ats_ip_sa_cast(&_max), ats_ip_sa_cast(max));
1155
/// Set the maximum value of the interval.
1156
/// @note Convenience overload.
1157
/// @return This interval.
1159
Metric const& max ///< Maximum value (host order).
1161
return this->setMax(&max);
1163
/** Set the maximum value to one less than @a max.
1164
@return This object.
1166
self& setMaxMinusOne(
1167
Metric const& max ///< One more than maximum value.
1173
/** Set the minimum value to one more than @a min.
1174
@return This object.
1176
self& setMinPlusOne(
1177
Metric const& min ///< One less than minimum value.
1183
/** Decremement the maximum value in place.
1184
@return This object.
1186
self& decrementMax() { dec(_max); return *this; }
1187
/** Increment the mininimum value in place.
1188
@return This object.
1190
self& incrementMin() { inc(_min); return *this; }
1192
/// Increment a metric.
1194
Metric& m ///< Incremented in place.
1196
uint8_t* addr = m.sin6_addr.s6_addr;
1197
uint8_t* b = addr + TS_IP6_SIZE;
1198
// Ripple carry. Walk up the address incrementing until we don't
1202
} while (b > addr && 0 == *b);
1205
/// Decrement a metric.
1207
Metric& m ///< Decremented in place.
1209
uint8_t* addr = m.sin6_addr.s6_addr;
1210
uint8_t* b = addr + TS_IP6_SIZE;
1211
// Ripple borrow. Walk up the address decrementing until we don't
1215
} while (b > addr && static_cast<uint8_t>(0xFF) == *b);
1217
/// @return Dereferenced @a addr.
1218
static Metric const& deref(
1219
ArgType addr ///< Argument to dereference.
1224
/// @return The argument type for the @a metric.
1225
static ArgType argue(
1226
Metric const& metric
1233
// We declare this after the helper operators and inside this namespace
1234
// so that the template uses these for comparisons.
1236
class Ip6Map : public IpMapBase<Ip6Node> {
1237
friend class ::IpMap;
1240
}} // end ts::detail
1241
//----------------------------------------------------------------------------
1247
inline ts::detail::Ip4Map*
1249
if (!_m4) _m4 = new ts::detail::Ip4Map;
1253
inline ts::detail::Ip6Map*
1255
if (!_m6) _m6 = new ts::detail::Ip6Map;
1260
IpMap::contains(sockaddr const* target, void** ptr) const {
1262
if (AF_INET == target->sa_family) {
1263
zret = _m4 && _m4->contains(ntohl(ats_ip4_addr_cast(target)), ptr);
1264
} else if (AF_INET6 == target->sa_family) {
1265
zret = _m6 && _m6->contains(ats_ip6_cast(target), ptr);
1271
IpMap::contains(in_addr_t target, void** ptr) const {
1272
return _m4 && _m4->contains(ntohl(target), ptr);
1277
sockaddr const* min,
1278
sockaddr const* max,
1281
ink_assert(min->sa_family == max->sa_family);
1282
if (AF_INET == min->sa_family) {
1283
this->force4()->mark(
1284
ntohl(ats_ip4_addr_cast(min)),
1285
ntohl(ats_ip4_addr_cast(max)),
1288
} else if (AF_INET6 == min->sa_family) {
1289
this->force6()->mark(ats_ip6_cast(min), ats_ip6_cast(max), data);
1295
IpMap::mark(in_addr_t min, in_addr_t max, void* data) {
1296
this->force4()->mark(ntohl(min), ntohl(max), data);
1302
sockaddr const* min,
1305
ink_assert(min->sa_family == max->sa_family);
1306
if (AF_INET == min->sa_family) {
1309
ntohl(ats_ip4_addr_cast(min)),
1310
ntohl(ats_ip4_addr_cast(max))
1312
} else if (AF_INET6 == min->sa_family) {
1313
if (_m6) _m6->unmark(ats_ip6_cast(min), ats_ip6_cast(max));
1319
IpMap::unmark(in_addr_t min, in_addr_t max) {
1320
if (_m4) _m4->unmark(ntohl(min), ntohl(max));
1326
sockaddr const* min,
1327
sockaddr const* max,
1330
ink_assert(min->sa_family == max->sa_family);
1331
if (AF_INET == min->sa_family) {
1332
this->force4()->fill(
1333
ntohl(ats_ip4_addr_cast(min)),
1334
ntohl(ats_ip4_addr_cast(max)),
1337
} else if (AF_INET6 == min->sa_family) {
1338
this->force6()->fill(ats_ip6_cast(min), ats_ip6_cast(max), data);
1344
IpMap::fill(in_addr_t min, in_addr_t max, void* data) {
1345
this->force4()->fill(ntohl(min), ntohl(max), data);
1350
IpMap::getCount() const {
1352
if (_m4) zret += _m4->getCount();
1353
if (_m6) zret += _m6->getCount();
1359
if (_m4) _m4->clear();
1360
if (_m6) _m6->clear();
1367
if (_m4) x = _m4->getHead();
1368
if (!x && _m6) x = _m6->getHead();
1369
return iterator(this, x);
1373
IpMap::iterator::operator ++ () {
1375
// If we go past the end of the list see if it was the v4 list
1376
// and if so, move to the v6 list (if it's there).
1377
Node* x = static_cast<Node*>(_node->_next);
1378
if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m4->getTail())
1379
x = _tree->_m6->getHead();
1385
inline IpMap::iterator&
1386
IpMap::iterator::operator--() {
1388
// At a node, try to back up. Handle the case where we back over the
1389
// start of the v6 addresses and switch to the v4, if there are any.
1390
Node* x = static_cast<Node*>(_node->_prev);
1391
if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m6->getHead())
1392
x = _tree->_m4->getTail();
1395
// We were at the end. Back up to v6 if possible, v4 if not.
1396
if (_tree->_m6) _node = _tree->_m6->getTail();
1397
if (!_node && _tree->_m4) _node = _tree->_m4->getTail();
1403
//----------------------------------------------------------------------------
1404
//----------------------------------------------------------------------------
added
removed
lib/ts/IpMap.cc
