1
# if ! defined(TS_IP_MAP_HEADER)
2
# define TS_IP_MAP_HEADER
4
# include "ink_platform.h"
6
# include <ts/ink_inet.h>
7
# include <ts/IntrusiveDList.h>
8
# include <ts/ink_assert.h>
12
Map of IP addresses to client data.
14
@section license License
16
Licensed to the Apache Software Foundation (ASF) under one
17
or more contributor license agreements. See the NOTICE file
18
distributed with this work for additional information
19
regarding copyright ownership. The ASF licenses this file
20
to you under the Apache License, Version 2.0 (the
21
"License"); you may not use this file except in compliance
22
with the License. You may obtain a copy of the License at
24
http://www.apache.org/licenses/LICENSE-2.0
26
Unless required by applicable law or agreed to in writing, software
27
distributed under the License is distributed on an "AS IS" BASIS,
28
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
29
See the License for the specific language governing permissions and
30
limitations under the License.
33
namespace ts { namespace detail {
36
This holds an interval based on a metric @a T along with
40
typename T, ///< Metric for span.
41
typename A = T const& ///< Argument type.
43
typedef T Metric; ///< Metric (storage) type.
44
typedef A ArgType; ///< Type used to pass instances of @c Metric.
46
Interval() {} ///< Default constructor.
47
/// Construct with values.
49
ArgType min, ///< Minimum value in span.
50
ArgType max ///< Maximum value in span.
51
) : _min(min), _max(max) {}
52
Metric _min; ///< Minimum value in span.
53
Metric _max; ///< Maximum value in span.
56
class Ip4Map; // Forward declare.
57
class Ip6Map; // Forward declare.
59
/** A node in a red/black tree.
61
This class provides only the basic tree operations. The client
62
must provide the search and decision logic. This enables this
63
class to be a base class for templated nodes with much less code
67
typedef RBNode self; ///< self reference type
70
typedef enum { RED, BLACK } Color;
72
/// Directional constants
73
typedef enum { NONE, LEFT, RIGHT } Direction;
75
/// Get a child by direction.
76
/// @return The child in the direction @a d if it exists,
79
Direction d //!< The direction of the desired child
82
/** Determine which child a node is
83
@return @c LEFT if @a n is the left child,
84
@c RIGHT if @a n is the right child,
85
@c NONE if @a n is not a child
87
Direction getChildDirection(
88
self* const& n //!< The presumed child node
90
return (n == _left) ? LEFT : (n == _right) ? RIGHT : NONE;
93
/** Get the parent node.
94
@return A Node* to the parent node or a @c nil Node* if no parent.
96
self* getParent() const { return const_cast<self*>(_parent); }
98
/// @return The color of the node.
99
Color getColor() const { return _color; }
101
/** Reverse a direction
102
@return @c LEFT if @a d is @c RIGHT, @c RIGHT if @a d is @c LEFT,
105
Direction flip(Direction d) {
106
return LEFT == d ? RIGHT : RIGHT == d ? LEFT : NONE;
109
/** Perform internal validation checks.
110
@return 0 on failure, black height of the tree on success.
114
/// Default constructor.
124
/// Destructor (force virtual).
125
virtual ~RBNode() { }
127
/** Rotate the subtree rooted at this node.
128
The node is rotated in to the position of one of its children.
129
Which child is determined by the direction parameter @a d. The
130
child in the other direction becomes the new root of the subtree.
132
If the parent pointer is set, then the child pointer of the original
133
parent is updated so that the tree is left in a consistent state.
135
@note If there is no child in the other direction, the rotation
136
fails and the original node is returned. It is @b not required
137
that a child exist in the direction specified by @a d.
139
@return The new root node for the subtree.
142
Direction d //!< The direction to rotate
145
/** Set the child node in direction @a d to @a n.
146
The @a d child is set to the node @a n. The pointers in this
147
node and @a n are set correctly. This can only be called if
148
there is no child node already present.
153
self* n, //!< The node to set as the child
154
Direction d //!< The direction of the child
157
/** Remove this node from the tree.
158
The tree is rebalanced after removal.
159
@return The new root node.
163
void clearChild(Direction dir) {
164
if (LEFT == dir) _left = 0;
165
else if (RIGHT == dir) _right = 0;
168
/** @name Subclass hook methods */
170
/** Structural change notification.
171
This method is called if the structure of the subtree rooted at
172
this node was changed.
174
This is intended a hook. The base method is empty so that subclasses
175
are not required to override.
177
virtual void structureFixup() {}
179
/** Called from @c validate to perform any additional validation checks.
180
Clients should chain this if they wish to perform additional checks.
181
@return @c true if the validation is successful, @c false otherwise.
182
@note The base method simply returns @c true.
184
virtual bool structureValidate() { return true; }
187
/** Replace this node with another node.
188
This is presumed to be non-order modifying so the next reference
192
self* n //!< Node to put in place of this node.
195
//! Rebalance the tree starting at this node
196
/** The tree is rebalanced so that all of the invariants are
197
true. The (potentially new) root of the tree is returned.
199
@return The root node of the tree after the rebalance.
201
self* rebalanceAfterInsert();
203
/** Rebalance the tree after a deletion.
204
Called on the lowest modified node.
205
@return The new root of the tree.
207
self* rebalanceAfterRemove(
208
Color c, //!< The color of the removed node.
209
Direction d //!< Direction of removed node from parent
212
//! Invoke @c structure_fixup() on this node and all of its ancestors.
213
self* rippleStructureFixup();
215
Color _color; ///< node color
216
self* _parent; ///< parent node (needed for rotations)
217
self* _left; ///< left child
218
self* _right; ///< right child
219
self* _next; ///< Next node.
220
self* _prev; ///< Previous node.
223
}} // namespace ts::detail
225
/** Map from IP addresses to client data.
227
Conceptually this class maps the entire space of IP addresses to
228
client data. Client data is stored as a @c (void*). Memory
229
management of the data is left to the client. The interface
230
supports marking ranges of addresses with a specific client
231
data. Marking takes a painter's algorithm approach -- any marking
232
overwrites any previous marking on an address. Details of marking
233
calls are discarded and only the final results are kept. That is,
234
a client cannot unmark expliticly any previous marking. Only a
235
specific range of addresses can be unmarked.
237
Both IPv4 and IPv6 are supported in the same map. Mixed ranges are
238
not supported (any particular range of addresses must be a single
239
protocol but ranges of both types can be in the map).
241
Use @c mark to mark / set / add addresses to the map.
242
Use @c unmark to unset addresses (setting the client data to 0 does
243
@b not remove the address -- this is for the convenience of clients
244
that do not need data, only membership). @c contains tests for
245
membership and retrieves the client data.
247
Ranges can be marked and unmarked arbitrarily. The internal
248
representation keeps a minimal set of ranges to describe the
249
current addresses. Search time is O(log n) where n is the number
250
of disjoint ranges. Marking and unmarking can take O(log n) and
251
may require memory allocation / deallocation although this is
258
typedef IpMap self; ///< Self reference type.
260
class iterator; // forward declare.
262
/** Public API for intervals in the map.
264
class Node : protected ts::detail::RBNode {
265
friend class iterator;
268
typedef Node self; ///< Self reference type.
269
/// Default constructor.
271
/// Construct with @a data.
272
Node(void* data) : _data(data) {}
273
/// @return Client data for the node.
274
virtual void* data() { return _data; }
276
virtual self& setData(
277
void* data ///< Client data pointer to store.
282
/// @return Minimum value of the interval.
283
virtual sockaddr const* min() const = 0;
284
/// @return Maximum value of the interval.
285
virtual sockaddr const* max() const = 0;
287
void* _data; ///< Client data.
290
/** Iterator over nodes / intervals.
292
The iteration is over all nodes, regardless of which node is
293
used to create the iterator. The node passed to the constructor
294
just sets the current location.
299
typedef iterator self; ///< Self reference type.
300
typedef Node value_type; ///< Referenced type for iterator.
301
typedef int difference_type; ///< Distance type.
302
typedef Node* pointer; ///< Pointer to referent.
303
typedef Node& reference; ///< Reference to referent.
304
typedef std::bidirectional_iterator_tag iterator_category;
305
/// Default constructor.
306
iterator() : _tree(0), _node(0) {}
308
reference operator* (); //!< value operator
309
pointer operator -> (); //!< dereference operator
310
self& operator++(); //!< next node (prefix)
311
self operator++(int); //!< next node (postfix)
312
self& operator--(); ///< previous node (prefix)
313
self operator--(int); ///< next node (postfix)
316
@return @c true if the iterators refer to the same node.
318
bool operator==(self const& that) const;
320
@return @c true if the iterators refer to different nodes.
322
bool operator!=(self const& that) const { return ! (*this == that); }
324
/// Construct a valid iterator.
325
iterator(IpMap* tree, Node* node) : _tree(tree), _node(node) {}
326
IpMap* _tree; ///< Container.
327
Node* _node; //!< Current node.
330
IpMap(); ///< Default constructor.
331
~IpMap(); ///< Destructor.
334
All addresses in the range [ @a min , @a max ] are marked with @a data.
338
sockaddr const* min, ///< Minimum value in range.
339
sockaddr const* max, ///< Maximum value in range.
340
void* data = 0 ///< Client data payload.
344
All addresses in the range [ @a min , @a max ] are marked with @a data.
345
@note Convenience overload for IPv4 addresses.
349
in_addr_t min, ///< Minimum address (network order).
350
in_addr_t max, ///< Maximum address (network order).
351
void* data = 0 ///< Client data.
354
/** Mark an IPv4 address @a addr with @a data.
355
This is equivalent to calling @c mark(addr, addr, data).
356
@note Convenience overload for IPv4 addresses.
360
in_addr_t addr, ///< Address (network order).
361
void* data = 0 ///< Client data.
365
All addresses in the range [ @a min , @a max ] are marked with @a data.
366
@note Convenience overload.
370
IpEndpoint const* min, ///< Minimum address (network order).
371
IpEndpoint const* max, ///< Maximum address (network order).
372
void* data = 0 ///< Client data.
375
/** Mark an IPv6 address @a addr with @a data.
376
This is equivalent to calling @c mark(addr, addr, data).
377
@note Convenience overload.
381
IpEndpoint const* addr, ///< Address (network order).
382
void* data = 0 ///< Client data.
385
/** Unmark addresses.
387
All addresses in the range [ @a min , @a max ] are cleared
388
(removed from the map), no longer marked.
393
sockaddr const* min, ///< Minimum value.
394
sockaddr const* max ///< Maximum value.
396
/// Unmark addresses (overload).
398
IpEndpoint const* min,
399
IpEndpoint const* max
403
in_addr_t min, ///< Minimum of range to unmark.
404
in_addr_t max ///< Maximum of range to unmark.
409
This background fills using the range. All addresses in the
410
range that are @b not present in the map are added. No
411
previously present address is changed.
413
@note This is useful for filling in first match tables.
422
/// Fill addresses (overload).
424
IpEndpoint const* min,
425
IpEndpoint const* max,
428
/// Fill addresses (overload).
435
/** Test for membership.
437
@return @c true if the address is in the map, @c false if not.
438
If the address is in the map and @a ptr is not @c NULL, @c *ptr
439
is set to the client data for the address.
442
sockaddr const* target, ///< Search target (network order).
443
void **ptr = 0 ///< Client data return.
446
/** Test for membership.
448
@note Covenience overload for IPv4.
450
@return @c true if the address is in the map, @c false if not.
451
If the address is in the map and @a ptr is not @c NULL, @c *ptr
452
is set to the client data for the address.
455
in_addr_t target, ///< Search target (network order).
456
void **ptr = 0 ///< Client data return.
460
IpEndpoint const* target, ///< Search target (network order).
461
void **ptr = 0 ///< Client data return.
464
/** Remove all addresses from the map.
466
@note This is much faster than @c unmark.
471
/// Iterator for first element.
473
/// Iterator past last element.
475
/// @return Number of distinct ranges in the map.
476
size_t getCount() const;
478
/** Validate internal data structures.
479
@note Intended for debugging, not general client use.
484
/// @return This map.
488
/// Force the IPv4 map to exist.
489
/// @return The IPv4 map.
490
ts::detail::Ip4Map* force4();
491
/// Force the IPv6 map to exist.
492
/// @return The IPv6 map.
493
ts::detail::Ip6Map* force6();
495
ts::detail::Ip4Map* _m4; ///< Map of IPv4 addresses.
496
ts::detail::Ip6Map* _m6; ///< Map of IPv6 addresses.
500
inline IpMap& IpMap::mark(in_addr_t addr, void* data) {
501
return this->mark(addr, addr, data);
504
inline IpMap& IpMap::mark(IpEndpoint const* addr, void* data) {
505
return this->mark(&addr->sa, &addr->sa, data);
508
inline IpMap& IpMap::mark(IpEndpoint const* min, IpEndpoint const* max, void* data) {
509
return this->mark(&min->sa, &max->sa, data);
512
inline IpMap& IpMap::unmark(IpEndpoint const* min, IpEndpoint const* max) {
513
return this->unmark(&min->sa, &max->sa);
516
inline IpMap& IpMap::fill(IpEndpoint const* min, IpEndpoint const* max, void* data) {
517
return this->fill(&min->sa, &max->sa, data);
520
inline bool IpMap::contains(IpEndpoint const* target, void** ptr) const {
521
return this->contains(&target->sa, ptr);
524
inline IpMap::iterator
526
return iterator(this, 0);
529
inline IpMap::iterator
530
IpMap::iterator::operator ++ (int) {
536
inline IpMap::iterator
537
IpMap::iterator::operator--(int) {
544
IpMap::iterator::operator == (iterator const& that) const {
545
return _tree == that._tree && _node == that._node;
548
inline IpMap::iterator::reference
549
IpMap::iterator::operator * () {
553
inline IpMap::iterator::pointer
554
IpMap::iterator::operator -> () {
558
inline IpMap::IpMap() : _m4(0), _m6(0) {}
560
# endif // TS_IP_MAP_HEADER
added
removed
lib/ts/IpMap.h
