You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2023/03/22 15:01:51 UTC
[trafficserver] branch master updated: libswoc: Final elimination of obsolete IpMap. (#9548)
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new 9082b9219 libswoc: Final elimination of obsolete IpMap. (#9548)
9082b9219 is described below
commit 9082b92190ef37862b56ef8c549e1e32f104dc75
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Wed Mar 22 10:01:42 2023 -0500
libswoc: Final elimination of obsolete IpMap. (#9548)
---
include/tscore/IpMap.h | 504 -------------
src/tscore/CMakeLists.txt | 1 -
src/tscore/IpMap.cc | 1342 -----------------------------------
src/tscore/Makefile.am | 2 -
src/tscore/unit_tests/test_IpMap.cc | 633 -----------------
5 files changed, 2482 deletions(-)
diff --git a/include/tscore/IpMap.h b/include/tscore/IpMap.h
deleted file mode 100644
index 72c54482e..000000000
--- a/include/tscore/IpMap.h
+++ /dev/null
@@ -1,504 +0,0 @@
-/** @file
-
- Map of IP addresses to client data.
-
- @section license License
-
- Licensed to the Apache Software Foundation (ASF) under one
- or more contributor license agreements. See the NOTICE file
- distributed with this work for additional information
- regarding copyright ownership. The ASF licenses this file
- to you under the Apache License, Version 2.0 (the
- "License"); you may not use this file except in compliance
- with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
-*/
-
-#pragma once
-
-#include <algorithm>
-#include <utility>
-
-#include "tscore/ink_platform.h"
-#include "tscore/ink_defs.h"
-#include "tscore/RbTree.h"
-#include "tscore/ink_inet.h"
-#include "tscpp/util/IntrusiveDList.h"
-#include "tscore/ink_assert.h"
-#include "tscore/BufferWriterForward.h"
-
-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 {
- using Metric = T; ///< Metric (storage) type.
- using ArgType = A; ///< 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)
- {
- }
- Metric _min; ///< Minimum value in span.
- Metric _max; ///< Maximum value in span.
- };
-
- class Ip4Map; // Forward declare.
- class Ip6Map; // Forward declare.
-} // namespace detail
-} // namespace ts
-
-/** Map from IP addresses to client data.
-
- Conceptually this class maps the entire space of IP addresses to
- client data. Client data is stored as a @c (void*). Memory
- management of the data is left to the client. The interface
- supports marking ranges of addresses with a specific client
- data. Marking takes a painter's algorithm approach -- any marking
- overwrites any previous marking on an address. Details of marking
- calls are discarded and only the final results are kept. That is,
- a client cannot unmark explicitly any previous marking. Only a
- specific range of addresses can be unmarked.
-
- Both IPv4 and IPv6 are supported in the same map. Mixed ranges are
- not supported (any particular range of addresses must be a single
- protocol but ranges of both types can be in the map).
-
- Use @c mark to mark / set / add addresses to the map.
- Use @c unmark to unset addresses (setting the client data to 0 does
- @b not remove the address -- this is for the convenience of clients
- that do not need data, only membership). @c contains tests for
- membership and retrieves the client data.
-
- Ranges can be marked and unmarked arbitrarily. The internal
- representation keeps a minimal set of ranges to describe the
- current addresses. Search time is O(log n) where n is the number
- of disjoint ranges. Marking and unmarking can take O(log n) and
- may require memory allocation / deallocation although this is
- minimized.
-*/
-
-class IpMap
-{
-public:
- using self_type = IpMap; ///< Self reference type.
-
- class iterator; // forward declare.
-
- static constexpr in_addr_t RAW_IP4_MIN_ADDR = 0;
- static constexpr IpAddr IP4_MIN_ADDR{RAW_IP4_MIN_ADDR};
- static constexpr in_addr_t RAW_IP4_MAX_ADDR = ~0;
- static constexpr IpAddr IP4_MAX_ADDR{RAW_IP4_MAX_ADDR};
-
- static constexpr in6_addr RAW_IP6_MIN_ADDR = {{{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}};
- static constexpr IpAddr IP6_MIN_ADDR{RAW_IP6_MIN_ADDR};
- static constexpr in6_addr RAW_IP6_MAX_ADDR = {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}}};
- static constexpr IpAddr IP6_MAX_ADDR{RAW_IP6_MAX_ADDR};
-
- /** Public API for intervals in the map.
- */
- class Node : protected ts::detail::RBNode
- {
- friend class iterator;
- friend class IpMap;
-
- public:
- using self_type = Node; ///< Self reference type.
- /// Default constructor.
- Node() {}
- /// Construct with @a data.
- Node(void *data) : _data(data) {}
- /// @return Client data for the node.
- virtual void *
- data()
- {
- return _data;
- }
- /// Set client data.
- virtual self_type &
- setData(void *data ///< Client data pointer to store.
- )
- {
- _data = data;
- return *this;
- }
- /// @return Minimum value of the interval.
- virtual sockaddr const *min() const = 0;
- /// @return Maximum value of the interval.
- virtual sockaddr const *max() const = 0;
-
- protected:
- void *_data = nullptr; ///< Client data.
- };
-
- /** Iterator over nodes / intervals.
-
- The iteration is over all nodes, regardless of which node is
- used to create the iterator. The node passed to the constructor
- just sets the current location.
- */
- class iterator
- {
- friend class IpMap;
-
- public:
- using self_type = iterator; ///< Self reference type.
- using value_type = Node; ///< Referenced type for iterator.
- using difference_type = int; ///< Distance type.
- using pointer = Node *; ///< Pointer to referent.
- using reference = Node &; ///< Reference to referent.
- using iterator_category = std::bidirectional_iterator_tag;
- /// Default constructor.
- iterator() = default;
- reference operator*() const; //!< value operator
- pointer operator->() const; //!< dereference operator
- self_type &operator++(); //!< next node (prefix)
- self_type operator++(int); //!< next node (postfix)
- self_type &operator--(); ///< previous node (prefix)
- self_type operator--(int); ///< next node (postfix)
-
- /** Equality.
- @return @c true if the iterators refer to the same node.
- */
- bool operator==(self_type const &that) const;
- /** Inequality.
- @return @c true if the iterators refer to different nodes.
- */
- bool
- operator!=(self_type const &that) const
- {
- return !(*this == that);
- }
-
- private:
- /// Construct a valid iterator.
- iterator(IpMap const *tree, Node *node) : _tree(tree), _node(node) {}
- IpMap const *_tree = nullptr; ///< Container.
- Node *_node = nullptr; //!< Current node.
- };
-
- IpMap() = default; ///< Default constructor.
- IpMap(self_type const &that) = delete;
- IpMap(self_type &&that) noexcept;
- ~IpMap(); ///< Destructor.
-
- self_type &operator=(self_type const &that) = delete;
- self_type &operator=(self_type &&that);
-
- /** Mark a range.
- All addresses in the range [ @a min , @a max ] are marked with @a data.
- @return This object.
- */
- self_type &mark(sockaddr const *min, ///< Minimum value in range.
- sockaddr const *max, ///< Maximum value in range.
- void *data = nullptr ///< 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_type &mark(in_addr_t min, ///< Minimum address (network order).
- in_addr_t max, ///< Maximum address (network order).
- void *data = nullptr ///< 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_type &mark(IpAddr const &min, ///< Minimum address (network order).
- IpAddr const &max, ///< Maximum address (network order).
- void *data = nullptr ///< 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_type &mark(in_addr_t addr, ///< Address (network order).
- void *data = nullptr ///< 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_type &mark(IpEndpoint const *min, ///< Minimum address (network order).
- IpEndpoint const *max, ///< Maximum address (network order).
- void *data = nullptr ///< 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_type &mark(IpEndpoint const *addr, ///< Address (network order).
- void *data = nullptr ///< Client data.
- );
-
- /** Unmark addresses.
-
- All addresses in the range [ @a min , @a max ] are cleared
- (removed from the map), no longer marked.
-
- @return This object.
- */
- self_type &unmark(sockaddr const *min, ///< Minimum value.
- sockaddr const *max ///< Maximum value.
- );
- /// Unmark addresses (overload).
- self_type &unmark(IpAddr const &min, IpAddr const &max);
- /// Unmark addresses (overload).
- self_type &unmark(IpEndpoint const *min, IpEndpoint const *max);
- /// Unmark overload.
- self_type &unmark(in_addr_t min, ///< Minimum of range to unmark.
- in_addr_t max ///< Maximum of range to unmark.
- );
-
- /** 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 because @a data for already present
- addresses is not changed.
-
- @return This object.
- */
- self_type &fill(sockaddr const *min, sockaddr const *max, void *data = nullptr);
- /// Fill addresses (overload).
- self_type &fill(IpEndpoint const *min, IpEndpoint const *max, void *data = nullptr);
- /// Fill addresses (overload).
- self_type &fill(IpAddr const &min, IpAddr const &max, void *data = nullptr);
- /// Fill addresses (overload).
- self_type &fill(in_addr_t min, in_addr_t max, void *data = nullptr);
-
- /** 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 nullptr, @c *ptr
- is set to the client data for the address.
- */
- bool contains(sockaddr const *target, ///< Search target (network order).
- void **ptr = nullptr ///< Client data return.
- ) const;
-
- /** Test for membership.
-
- @note Convenience overload for IPv4.
-
- @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 nullptr, @c *ptr
- is set to the client data for the address.
- */
- bool contains(in_addr_t target, ///< Search target (network order).
- void **ptr = nullptr ///< Client data return.
- ) const;
-
- /** Test for membership.
-
- @note Convenience overload for @c IpEndpoint.
-
- @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 nullptr, @c *ptr
- is set to the client data for the address.
- */
- bool contains(IpEndpoint const *target, ///< Search target (network order).
- void **ptr = nullptr ///< Client data return.
- ) const;
-
- /** Test for membership.
-
- @note Convenience overload for @c IpAddr.
-
- @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 nullptr, @c *ptr
- is set to the client data for the address.
- */
- bool contains(IpAddr const &target, ///< Search target (network order).
- void **ptr = nullptr ///< Client data return.
- ) const;
-
- /** Remove all addresses from the map.
-
- @note This is much faster than @c unmark.
- @return This object.
- */
- self_type &clear();
-
- /// Iterator for first element.
- iterator begin() const;
- /// Iterator past last element.
- iterator end() const;
- /// @return Number of distinct ranges in the map.
- size_t count() const;
-
- /** Validate internal data structures.
- @note Intended for debugging, not general client use.
- */
- void validate();
-
- /** Generate formatted output.
- *
- * @param w Destination of formatted output.
- * @param spec Formatting specification.
- * @return @a w
- */
- ts::BufferWriter &describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const;
-
-protected:
- /// Force the IPv4 map to exist.
- /// @return The IPv4 map.
- ts::detail::Ip4Map *force4();
- /// Force the IPv6 map to exist.
- /// @return The IPv6 map.
- ts::detail::Ip6Map *force6();
-
- ts::detail::Ip4Map *_m4 = nullptr; ///< Map of IPv4 addresses.
- ts::detail::Ip6Map *_m6 = nullptr; ///< Map of IPv6 addresses.
-};
-
-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;
- x.assign(min);
- y.assign(max);
- return this->mark(&x.sa, &y.sa, 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)
-{
- return this->mark(&min->sa, &max->sa, data);
-}
-
-inline IpMap &
-IpMap::unmark(IpEndpoint const *min, IpEndpoint const *max)
-{
- return this->unmark(&min->sa, &max->sa);
-}
-
-inline IpMap &
-IpMap::unmark(IpAddr const &min, IpAddr const &max)
-{
- IpEndpoint x, y;
- x.assign(min);
- y.assign(max);
- return this->unmark(&x.sa, &y.sa);
-}
-
-inline IpMap &
-IpMap::fill(IpEndpoint const *min, IpEndpoint const *max, void *data)
-{
- return this->fill(&min->sa, &max->sa, data);
-}
-
-inline IpMap &
-IpMap::fill(IpAddr const &min, IpAddr const &max, void *data)
-{
- IpEndpoint x, y;
- x.assign(min);
- y.assign(max);
- return this->fill(&x.sa, &y.sa, data);
-}
-
-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
-{
- IpEndpoint ip;
- ip.assign(addr);
- return this->contains(&ip.sa, ptr);
-}
-
-inline IpMap::iterator
-IpMap::end() const
-{
- return iterator(this, nullptr);
-}
-
-inline IpMap::iterator
-IpMap::iterator::operator++(int)
-{
- iterator old(*this);
- ++*this;
- return old;
-}
-
-inline IpMap::iterator
-IpMap::iterator::operator--(int)
-{
- self_type tmp(*this);
- --*this;
- return tmp;
-}
-
-inline bool
-IpMap::iterator::operator==(iterator const &that) const
-{
- return _tree == that._tree && _node == that._node;
-}
-
-inline IpMap::iterator::reference
-IpMap::iterator::operator*() const
-{
- return *_node;
-}
-
-inline IpMap::iterator::pointer
-IpMap::iterator::operator->() const
-{
- return _node;
-}
-
-namespace ts
-{
-inline BufferWriter &
-bwformat(BufferWriter &w, BWFSpec const &spec, IpMap const &map)
-{
- return map.describe(w, spec);
-}
-} // namespace ts
diff --git a/src/tscore/CMakeLists.txt b/src/tscore/CMakeLists.txt
index ff7acdfbe..e16a8c237 100644
--- a/src/tscore/CMakeLists.txt
+++ b/src/tscore/CMakeLists.txt
@@ -123,7 +123,6 @@ add_executable(test_tscore
unit_tests/test_History.cc
unit_tests/test_IntrusiveHashMap.cc
unit_tests/test_IntrusivePtr.cc
- unit_tests/test_IpMap.cc
unit_tests/test_List.cc
unit_tests/test_MMH.cc
unit_tests/test_MT_hashtable.cc
diff --git a/src/tscore/IpMap.cc b/src/tscore/IpMap.cc
deleted file mode 100644
index 5200e1c19..000000000
--- a/src/tscore/IpMap.cc
+++ /dev/null
@@ -1,1342 +0,0 @@
-/** @file
- IP address map support.
-
- Provide the ability to create a range based mapping for the IP
- address space. Addresses can be added and removed and each address
- is associated with arbitrary client data.
-
- @internal Don't bother to look at this code if you don't know how
- a red/black tree works. There are so many good references on the
- subject it's a waste to have some inferior version here. The
- methods on @c Node follow the standard implementation except for
- being parameterized by direction (so that, for instance, right
- rotate and left rotate are both done by the @c rotate method with
- a direction argument).
-
- @section license License
-
- Licensed to the Apache Software Foundation (ASF) under one
- or more contributor license agreements. See the NOTICE file
- distributed with this work for additional information
- regarding copyright ownership. The ASF licenses this file
- to you under the Apache License, Version 2.0 (the
- "License"); you may not use this file except in compliance
- with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
- */
-
-// Validation / printing disabled until I figure out how to generalize so
-// as to not tie reporting into a particular project environment.
-
-/* @internal It is a bit ugly to store a @c sockaddr equivalent in the table
- as all that is actually needed is the raw address. Unfortunately some clients
- require a @c sockaddr* return via the iterator and that's expensive to
- compute all the time. I should, at some point, re-examine this and see if we
- can do better and have a more compact internal format. I suspect I did this
- before we had IpAddr as a type.
-*/
-
-#include "tscore/IpMap.h"
-#include "tscore/ink_inet.h"
-#include "tscore/BufferWriter.h"
-
-namespace ts
-{
-namespace detail
-{
- // 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;
-
- using self_type = IpMapBase<N>; ///< Self reference type.
- using ArgType = typename N::ArgType; ///< Import type.
- using Metric = typename N::Metric; ///< Import type.g482
-
- IpMapBase() = default;
- IpMapBase(self_type &&that) : _root(that._root), _list(std::move(that._list)) { that._root = nullptr; }
- ~IpMapBase();
- /** Mark a range.
- All addresses in the range [ @a min , @a max ] are marked with @a data.
- @return This object.
- */
- self_type &mark(ArgType min, ///< Minimum value in range.
- ArgType max, ///< Maximum value in range.
- void *data = nullptr ///< 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_type &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_type &fill(ArgType min, ArgType max, void *data = nullptr);
-
- /** 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 nullptr, @c *ptr
- is set to the client data for the address.
- */
- bool contains(ArgType target, ///< Search target value.
- void **ptr = nullptr ///< 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_type &clear();
-
- /** Lower bound for @a target. @return The node whose minimum value
- is the largest that is not greater than @a target, or @c nullptr 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 insert_after(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 insert_before(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 count() const;
-
- /** Generate formatted output.
- *
- * @param w Destination of the output.
- * @param spec Format specification.
- * @return @a w.
- */
- ts::BufferWriter &describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const;
-
- // 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 *
- head()
- {
- return static_cast<N *>(_list.head());
- }
- N *
- tail()
- {
- return static_cast<N *>(_list.tail());
- }
-
- N *_root = nullptr; ///< 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.
- struct NodeLinkage {
- static RBNode *&
- next_ptr(RBNode *n)
- {
- return n->_next;
- }
- static RBNode *&
- prev_ptr(RBNode *n)
- {
- return n->_prev;
- }
- };
- using NodeList = ts::IntrusiveDList<NodeLinkage>;
- /// 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 = nullptr; // best node so far.
- while (n) {
- if (target < n->_min) {
- n = left(n);
- } else {
- zret = n; // this is a better candidate.
- if (n->_max < target) {
- n = right(n);
- } else {
- break;
- }
- }
- }
- return zret;
- }
-
- template <typename N>
- IpMapBase<N> &
- IpMapBase<N>::clear()
- {
- // Delete everything.
- N *n = static_cast<N *>(_list.head());
- while (n) {
- N *x = n;
- n = next(n);
- delete x;
- }
- _list.clear();
- _root = nullptr;
- 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 = nullptr; // New node (if any).
- // Need copies because we will modify these.
- Metric localmin = N::deref(rmin);
- Metric localmax = N::deref(rmax);
-
- // Handle cases involving a node of interest to the left of the
- // range.
- if (n) {
- if (n->_min < localmin) {
- Metric min_1 = localmin;
- 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 >= localmax) { // incoming range is covered, just discard.
- return *this;
- } else if (n->_data != payload) { // different payload, clip range on left.
- localmin = n->_max;
- N::inc(localmin);
- n = next(n);
- } else { // skew overlap with same payload, use node and continue.
- x = n;
- n = next(n);
- }
- }
- } else {
- n = this->head();
- }
-
- // 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 be 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 = localmax;
- N::inc(max_plus1);
-
- /* Notes:
- - max (and thence also max_plus1) never change during the loop.
- - we must have either x != 0 or adjust min but not both for each loop iteration.
- */
- while (n) {
- if (n->_data == payload) {
- if (x) {
- if (n->_max <= localmax) { // next range is covered, so we can remove and continue.
-#if defined(__clang_analyzer__)
- x->_next = n->_next; // done in @c remove, but CA doesn't realize that.
- // It's insufficient to assert(x->_next != n) after the remove.
-#endif
- 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(localmax);
- return *this;
- }
- } else { // not carrying a span.
- if (n->_max <= localmax) { // next range is covered - use it.
- x = n;
- x->setMin(localmin);
- n = next(n);
- } else if (n->_min <= max_plus1) {
- n->setMin(localmin);
- return *this;
- } else { // no overlap, space to complete range.
- this->insert_before(n, new N(localmin, localmax, payload));
- return *this;
- }
- }
- } else { // different payload
- if (x) {
- if (localmax < n->_min) { // range ends before n starts, done.
- x->setMax(localmax);
- return *this;
- } else if (localmax <= 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 = nullptr;
- localmin = n->_max;
- N::inc(localmin); // OK because n->_max maximal => next is null.
- n = next(n);
- }
- } else { // no carry node.
- if (localmax < n->_min) { // entirely before next span.
- this->insert_before(n, new N(localmin, localmax, payload));
- return *this;
- } else {
- if (localmin < n->_min) { // leading section, need node.
- N *y = new N(localmin, n->_min, payload);
- y->decrementMax();
- this->insert_before(n, y);
- }
- if (localmax <= n->_max) { // nothing past node
- return *this;
- }
- localmin = n->_max;
- N::inc(localmin);
- n = next(n);
- }
- }
- }
- }
- // Invariant: min is larger than any existing range maximum.
- if (x) {
- x->setMax(localmax);
- } else {
- this->append(new N(localmin, localmax, 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 = nullptr; // New node, gets set if we re-use an existing one.
- N *y = nullptr; // 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->insert_before(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) {
- // Can only have left skew overlap, otherwise disjoint.
- // Clip if overlap.
- if (n->_max >= min) {
- n->setMax(min_1);
- } else if (nullptr != (y = next(n)) && y->_max <= max) {
- // because @a n was selected as the minimum it must be the case that
- // y->min >= min (or y would have been selected). Therefore in this
- // case the request covers the next node therefore it can be reused.
- x = y;
- x->setMin(min).setMax(max).setData(payload);
- n = x; // this gets bumped again, which is correct.
- }
- } else {
- // Existing span covers new span but with a different payload.
- // We split it, put the new span in between and we're done.
- // 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->insert_after(n, x);
- this->insert_after(x, r);
- return *this; // done.
- }
- n = next(n); // lower bound span handled, move on.
- if (!x) {
- x = new N(min, max, payload);
- if (n) {
- this->insert_before(n, x);
- } else {
- this->append(x); // note that since n == 0 we'll just return.
- }
- }
- } else if (nullptr != (n = this->head()) && // 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);
- }
-
- // 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;
- }
- }
-
- 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->insert_after(n, x);
- return *this; // done.
- } 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));
- }
- break;
- }
- }
- return *this;
- }
-
- template <typename N>
- void
- IpMapBase<N>::insert_after(N *spot, N *n)
- {
- N *c = right(spot);
- if (!c) {
- spot->setChild(n, N::RIGHT);
- } else {
- spot->_next->setChild(n, N::LEFT);
- }
-
- _list.insert_after(spot, n);
- _root = static_cast<N *>(n->rebalanceAfterInsert());
- }
-
- template <typename N>
- void
- IpMapBase<N>::insert_before(N *spot, N *n)
- {
- if (left(spot) == nullptr) {
- spot->setChild(n, N::LEFT);
- } else {
-// If there's a left child, there's a previous node, therefore spot->_prev is valid.
-// Clang analyzer doesn't realize this so it generates a false positive.
-#if defined(__clang_analyzer__)
- ink_assert(spot->_prev != nullptr);
-#endif
- spot->_prev->setChild(n, N::RIGHT);
- }
-
- _list.insert_before(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.head()->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.tail()->setChild(n, N::RIGHT)->rebalanceAfterInsert());
- }
- _list.append(n);
- }
-
- template <typename N>
- void
- IpMapBase<N>::remove(N *n)
- {
- _root = static_cast<N *>(n->remove());
- _list.erase(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;
- }
- }
- return zret;
- }
-
- template <typename N>
- size_t
- IpMapBase<N>::count() const
- {
- return _list.count();
- }
- //----------------------------------------------------------------------------
- template <typename N>
- void
- IpMapBase<N>::validate()
- {
-#if 0
- if (_root) _root->validate();
- for ( Node* n = _list.head() ; n ; n = n->_next ) {
- Node* x;
- if (0 != (x = n->_next)) {
- if (x->_prev != n)
- std::cout << "Broken list" << std::endl;
- if (n->_max >= x->_min)
- std::cout << "Out of order - " << n->_max << " > " << x->_min << std::endl;
- if (n->_parent == n || n->_left == n || n->_right == n)
- std::cout << "Looped node" << std::endl;
- }
- }
-#endif
- }
-
- template <typename N>
- ts::BufferWriter &
- IpMapBase<N>::describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const
- {
- auto pos = w.extent();
- for (auto const &rb_node : _list) {
- N const &n{static_cast<N const &>(rb_node)};
- if (w.extent() > pos) {
- w.write(',');
- }
- w.print("{::a}-{::a}={}", n.min(), n.max(), n._data);
- if (std::string_view::npos != spec._ext.find('x')) {
- w.print("[{};^{};<{};>{}]", n._color == N::BLACK ? "Black" : "Red", n._parent, n._left, n._right);
- }
- }
- return w;
- }
-
- template <typename N> IpMapBase<N>::~IpMapBase()
- {
- this->clear();
- }
-
- //----------------------------------------------------------------------------
- using Ip4Span = Interval<in_addr_t, in_addr_t>;
-
- /** 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:
- using self_type = ts::detail::Ip4Node; ///< 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), _sa()
- {
- 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.
- sockaddr const *
- min() const override
- {
- return ats_ip_sa_cast(&_sa._min);
- }
- /// @return The maximum value of the interval.
- sockaddr const *
- max() const override
- {
- return ats_ip_sa_cast(&_sa._max);
- }
- /// Set the client data.
- self_type &
- setData(void *data ///< Client data.
- ) override
- {
- _data = data;
- return *this;
- }
-
- protected:
- /// Set the minimum value of the interval.
- /// @return This interval.
- self_type &
- setMin(ArgType min ///< Minimum value (host order).
- )
- {
- _min = min;
- _sa._min.sin_addr.s_addr = htonl(min);
- return *this;
- }
-
- /// Set the maximum value of the interval.
- /// @return This interval.
- self_type &
- setMax(ArgType max ///< Maximum value (host order).
- )
- {
- _max = max;
- _sa._max.sin_addr.s_addr = htonl(max);
- return *this;
- }
-
- /** Set the maximum value to one less than @a max.
- @return This object.
- */
- self_type &
- 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_type &
- setMinPlusOne(ArgType min ///< One less than minimum value.
- )
- {
- return this->setMin(min + 1);
- }
- /** decrement the maximum value in place.
- @return This object.
- */
- self_type &
- decrementMax()
- {
- this->setMax(_max - 1);
- return *this;
- }
- /** Increment the minimum value in place.
- @return This object.
- */
- self_type &
- incrementMin()
- {
- this->setMin(_min + 1);
- return *this;
- }
-
- /// Increment a metric.
- static void
- inc(Metric &m ///< Incremented in place.
- )
- {
- ++m;
- }
-
- /// Decrement a metric.
- static void
- dec(Metric &m ///< Decremented in place.
- )
- {
- --m;
- }
-
- /// @return Dereferenced @a addr.
- static Metric
- deref(ArgType addr ///< Argument to dereference.
- )
- {
- return addr;
- }
-
- /// @return The argument type for the @a metric.
- static ArgType
- argue(Metric const &metric)
- {
- return metric;
- }
-
- struct {
- sockaddr_in _min;
- sockaddr_in _max;
- } _sa; ///< Addresses in API compliant form.
- };
-
- class Ip4Map : public IpMapBase<Ip4Node>
- {
- friend class ::IpMap;
- };
-
- //----------------------------------------------------------------------------
- using Ip6Span = Interval<sockaddr_in6>;
-
- /** Node for IPv6 map.
- */
- class Ip6Node : public IpMap::Node, protected Ip6Span
- {
- friend struct IpMapBase<Ip6Node>;
-
- public:
- using self_type = ts::detail::Ip6Node; ///< Self reference type.
- /// Override @c ArgType from @c Interval because the convention
- /// is to use a pointer, not a reference.
- using ArgType = const ts::detail::Interval<sockaddr_in6, const sockaddr_in6 &>::Metric *;
-
- /** Construct from the argument type.
- *
- * @param min Minimum value in the range.
- * @param max Maximum value in the range (inclusive).
- * @param data Data to attach to the range.
- */
-
- Ip6Node(ArgType min, ///< Minimum address (network order).
- ArgType max, ///< Maximum address (network order).
- void *data ///< Client data.
- )
- : Node(data), Ip6Span(*min, *max)
- {
- }
-
- /** Construct from the underlying @c Metric type @a min to @a max
- *
- * @param min Minimum value in the range.
- * @param max Maximum value in the range (inclusive).
- * @param data Data to attach to the range.
- */
- Ip6Node(Metric const &min, Metric const &max, void *data) : Node(data), Ip6Span(min, max) {}
-
- /// @return The minimum value of the interval.
- sockaddr const *
- min() const override
- {
- return ats_ip_sa_cast(&_min);
- }
-
- /// @return The maximum value of the interval.
- sockaddr const *
- max() const override
- {
- return ats_ip_sa_cast(&_max);
- }
-
- /** Set the client @a data.
- *
- * @param data Client data.
- * @return @a this
- */
- self_type &
- setData(void *data) override
- {
- _data = data;
- return *this;
- }
-
- protected:
- /// Set the minimum value of the interval.
- /// @return This interval.
- self_type &
- setMin(ArgType min ///< Minimum value (host order).
- )
- {
- ats_ip_copy(ats_ip_sa_cast(&_min), ats_ip_sa_cast(min));
- return *this;
- }
-
- /// Set the minimum value of the interval.
- /// @note Convenience overload.
- /// @return This interval.
- self_type &
- setMin(Metric const &min ///< Minimum value (host order).
- )
- {
- return this->setMin(&min);
- }
-
- /// Set the maximum value of the interval.
- /// @return This interval.
- self_type &
- 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_type &
- 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_type &
- 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_type &
- setMinPlusOne(Metric const &min ///< One less than minimum value.
- )
- {
- this->setMin(min);
- inc(_min);
- return *this;
- }
- /** Decrement the maximum value in place.
- @return This object.
- */
- self_type &
- decrementMax()
- {
- dec(_max);
- return *this;
- }
- /** Increment the minimum value in place.
- @return This object.
- */
- self_type &
- 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);
- }
-
- /// 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;
- }
- };
-
- // 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;
- };
-} // namespace detail
-
-template <typename N>
-inline BufferWriter &
-bwformat(BufferWriter &w, BWFSpec const &spec, detail::IpMapBase<N> const &map)
-{
- return map.describe(w, spec);
-}
-
-} // namespace ts
-//----------------------------------------------------------------------------
-IpMap::IpMap(IpMap::self_type &&that) noexcept : _m4(that._m4), _m6(that._m6)
-{
- that._m4 = nullptr;
- that._m6 = nullptr;
-}
-
-IpMap::self_type &
-IpMap::operator=(IpMap::self_type &&that)
-{
- if (&that != this) {
- this->clear();
- std::swap(_m4, that._m4);
- std::swap(_m6, that._m6);
- }
- return *this;
-}
-
-IpMap::~IpMap()
-{
- delete _m4;
- delete _m6;
-}
-
-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;
- }
- return _m6;
-}
-
-bool
-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);
- } else if (AF_INET6 == target->sa_family) {
- zret = _m6 && _m6->contains(ats_ip6_cast(target), ptr);
- }
- return zret;
-}
-
-bool
-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)
-{
- 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);
- } 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)
-{
- this->force4()->mark(ntohl(min), ntohl(max), data);
- return *this;
-}
-
-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)));
- }
- } else if (AF_INET6 == min->sa_family) {
- 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));
- }
- return *this;
-}
-
-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);
- } 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)
-{
- this->force4()->fill(ntohl(min), ntohl(max), data);
- return *this;
-}
-
-size_t
-IpMap::count() const
-{
- size_t zret = 0;
- if (_m4) {
- zret += _m4->count();
- }
- if (_m6) {
- zret += _m6->count();
- }
- return zret;
-}
-
-IpMap &
-IpMap::clear()
-{
- if (_m4) {
- _m4->clear();
- }
- if (_m6) {
- _m6->clear();
- }
- return *this;
-}
-
-IpMap::iterator
-IpMap::begin() const
-{
- Node *x = nullptr;
- if (_m4) {
- x = _m4->head();
- }
- if (!x && _m6) {
- x = _m6->head();
- }
- return iterator(this, x);
-}
-
-IpMap::iterator &
-IpMap::iterator::operator++()
-{
- if (_node) {
- // If we go past the end of the list see if it was the v4 list
- // and if so, move to the v6 list (if it's there).
- Node *x = static_cast<Node *>(_node->_next);
- if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m4->tail()) {
- x = _tree->_m6->head();
- }
- _node = x;
- }
- return *this;
-}
-
-inline IpMap::iterator &
-IpMap::iterator::operator--()
-{
- if (_node) {
- // At a node, try to back up. Handle the case where we back over the
- // start of the v6 addresses and switch to the v4, if there are any.
- Node *x = static_cast<Node *>(_node->_prev);
- if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m6->head()) {
- x = _tree->_m4->tail();
- }
- _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->tail();
- }
- if (!_node && _tree->_m4) {
- _node = _tree->_m4->tail();
- }
- }
- return *this;
-}
-
-ts::BufferWriter &
-IpMap::describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const
-{
- w.write("IPv4 ");
- if (_m4) {
- bwformat(w, spec, *_m4);
- } else {
- w.write("N/A");
- }
- w.write("\n");
-
- w.write("IPv6 ");
- if (_m6) {
- bwformat(w, spec, *_m6);
- } else {
- w.write("N/A");
- }
- w.write("\n");
-
- return w;
-}
-
-//----------------------------------------------------------------------------
-//----------------------------------------------------------------------------
diff --git a/src/tscore/Makefile.am b/src/tscore/Makefile.am
index 4cd1fa6d2..cabd04301 100644
--- a/src/tscore/Makefile.am
+++ b/src/tscore/Makefile.am
@@ -104,7 +104,6 @@ libtscore_la_SOURCES = \
ink_thread.cc \
ink_time.cc \
ink_uuid.cc \
- IpMap.cc \
JeMiAllocator.cc \
Layout.cc \
llqueue.cc \
@@ -183,7 +182,6 @@ test_tscore_SOURCES = \
unit_tests/test_ink_memory.cc \
unit_tests/test_IntrusiveHashMap.cc \
unit_tests/test_IntrusivePtr.cc \
- unit_tests/test_IpMap.cc \
unit_tests/test_layout.cc \
unit_tests/test_List.cc \
unit_tests/test_MemArena.cc \
diff --git a/src/tscore/unit_tests/test_IpMap.cc b/src/tscore/unit_tests/test_IpMap.cc
deleted file mode 100644
index 07debf88b..000000000
--- a/src/tscore/unit_tests/test_IpMap.cc
+++ /dev/null
@@ -1,633 +0,0 @@
-/** @file
-
- IpMap unit tests.
-
- @section license License
-
- Licensed to the Apache Software Foundation (ASF) under one
- or more contributor license agreements. See the NOTICE file
- distributed with this work for additional information
- regarding copyright ownership. The ASF licenses this file
- to you under the Apache License, Version 2.0 (the
- "License"); you may not use this file except in compliance
- with the License. You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
-*/
-
-#include "tscore/IpMap.h"
-#include <sstream>
-#include <catch.hpp>
-#include <tscore/BufferWriter.h>
-
-std::ostream &
-operator<<(std::ostream &s, IpEndpoint const &addr)
-{
- ip_text_buffer b;
- ats_ip_ntop(addr, b, sizeof(b));
- s << b;
- return s;
-}
-
-void
-IpMapTestPrint(IpMap &map)
-{
- printf("IpMap Dump\n");
- for (auto &spot : map) {
- ip_text_buffer ipb1, ipb2;
-
- printf("%s - %s : %p\n", ats_ip_ntop(spot.min(), ipb1, sizeof ipb1), ats_ip_ntop(spot.max(), ipb2, sizeof(ipb2)), spot.data());
- }
- printf("\n");
-}
-
-// --- Test helper classes ---
-class MapMarkedAt : public Catch::MatcherBase<IpMap>
-{
- IpEndpoint const &_addr;
-
-public:
- MapMarkedAt(IpEndpoint const &addr) : _addr(addr) {}
-
- bool
- match(IpMap const &map) const override
- {
- return map.contains(&_addr);
- }
-
- std::string
- describe() const override
- {
- std::ostringstream ss;
- ss << _addr << " is marked";
- return ss.str();
- }
-};
-
-// The builder function
-inline MapMarkedAt
-IsMarkedAt(IpEndpoint const &_addr)
-{
- return {_addr};
-}
-
-class MapMarkedWith : public Catch::MatcherBase<IpMap>
-{
- IpEndpoint const &_addr;
- void *_mark;
- mutable bool _found_p = false;
-
-public:
- MapMarkedWith(IpEndpoint const &addr, void *mark) : _addr(addr), _mark(mark) {}
-
- bool
- match(IpMap const &map) const override
- {
- void *mark = nullptr;
- return (_found_p = map.contains(&_addr, &mark)) && mark == _mark;
- }
-
- std::string
- describe() const override
- {
- std::ostringstream ss;
- if (_found_p) {
- ss << "is marked at " << _addr << " with " << std::hex << reinterpret_cast<intptr_t>(_mark);
- } else {
- ss << "is not marked at " << _addr;
- }
- return ss.str();
- }
-};
-
-inline MapMarkedWith
-IsMarkedWith(IpEndpoint const &addr, void *mark)
-{
- return {addr, mark};
-}
-
-// -------------
-// --- TESTS ---
-// -------------
-TEST_CASE("IpMap Basic", "[libts][ipmap]")
-{
- IpMap map;
- void *const markA = reinterpret_cast<void *>(1);
- void *const markB = reinterpret_cast<void *>(2);
- void *const markC = reinterpret_cast<void *>(3);
- void *mark; // for retrieval
-
- in_addr_t ip5 = htonl(5), ip9 = htonl(9);
- in_addr_t ip10 = htonl(10), ip15 = htonl(15), ip20 = htonl(20);
- in_addr_t ip50 = htonl(50), ip60 = htonl(60);
- in_addr_t ip100 = htonl(100), ip120 = htonl(120), ip140 = htonl(140);
- in_addr_t ip150 = htonl(150), ip160 = htonl(160);
- in_addr_t ip200 = htonl(200);
- in_addr_t ip0 = 0;
- in_addr_t ipmax = ~static_cast<in_addr_t>(0);
-
- map.mark(ip10, ip20, markA);
- map.mark(ip5, ip9, markA);
- {
- INFO("Coalesce failed");
- CHECK(map.count() == 1);
- }
- {
- INFO("Range max not found.");
- CHECK(map.contains(ip9));
- }
- {
- INFO("Span min not found");
- CHECK(map.contains(ip10, &mark));
- }
- {
- INFO("Mark not preserved.");
- CHECK(mark == markA);
- }
-
- map.fill(ip15, ip100, markB);
- {
- INFO("Fill failed.");
- CHECK(map.count() == 2);
- }
- {
- INFO("fill interior missing");
- CHECK(map.contains(ip50, &mark));
- }
- {
- INFO("Fill mark not preserved.");
- CHECK(mark == markB);
- }
- {
- INFO("Span min not found.");
- CHECK(!map.contains(ip200));
- }
- {
- INFO("Old span interior not found");
- CHECK(map.contains(ip15, &mark));
- }
- {
- INFO("Fill overwrote mark.");
- CHECK(mark == markA);
- }
-
- map.clear();
- {
- INFO("Clear failed.");
- CHECK(map.count() == 0);
- }
-
- map.mark(ip20, ip50, markA);
- map.mark(ip100, ip150, markB);
- map.fill(ip10, ip200, markC);
- CHECK(map.count() == 5);
- {
- INFO("Left span missing");
- CHECK(map.contains(ip15, &mark));
- }
- {
- INFO("Middle span missing");
- CHECK(map.contains(ip60, &mark));
- }
- {
- INFO("fill mark wrong.");
- CHECK(mark == markC);
- }
- {
- INFO("right span missing.");
- CHECK(map.contains(ip160));
- }
- {
- INFO("right span missing");
- CHECK(map.contains(ip120, &mark));
- }
- {
- INFO("wrong data on right mark span.");
- CHECK(mark == markB);
- }
-
- map.unmark(ip140, ip160);
- {
- INFO("unmark failed");
- CHECK(map.count() == 5);
- }
- {
- INFO("unmark left edge still there.");
- CHECK(!map.contains(ip140));
- }
- {
- INFO("unmark middle still there.");
- CHECK(!map.contains(ip150));
- }
- {
- INFO("unmark right edge still there.");
- CHECK(!map.contains(ip160));
- }
-
- map.clear();
- map.mark(ip20, ip20, markA);
- {
- INFO("Map failed on singleton insert");
- CHECK(map.contains(ip20));
- }
- map.mark(ip10, ip200, markB);
- mark = 0;
- map.contains(ip20, &mark);
- {
- INFO("Map held singleton against range.");
- CHECK(mark == markB);
- }
- map.mark(ip100, ip120, markA);
- map.mark(ip150, ip160, markB);
- map.mark(ip0, ipmax, markC);
- {
- INFO("IpMap: Full range fill left extra ranges.");
- CHECK(map.count() == 1);
- }
-}
-
-TEST_CASE("IpMap Unmark", "[libts][ipmap]")
-{
- IpMap map;
- // ip_text_buffer ipb1, ipb2;
- void *const markA = reinterpret_cast<void *>(1);
-
- IpEndpoint a_0, a_0_0_0_16, a_0_0_0_17, a_max;
- IpEndpoint a_10_28_56_0, a_10_28_56_4, a_10_28_56_255;
- IpEndpoint a_10_28_55_255, a_10_28_57_0;
- IpEndpoint a_63_128_1_12;
- IpEndpoint a_loopback, a_loopback2;
- IpEndpoint a6_0, a6_max, a6_fe80_9d90, a6_fe80_9d9d, a6_fe80_9d95;
-
- ats_ip_pton("0.0.0.0", &a_0);
- ats_ip_pton("0.0.0.16", &a_0_0_0_16);
- ats_ip_pton("0.0.0.17", &a_0_0_0_17);
- ats_ip_pton("255.255.255.255", &a_max);
- ats_ip_pton("10.28.55.255", &a_10_28_55_255);
- ats_ip_pton("10.28.56.0", &a_10_28_56_0);
- ats_ip_pton("10.28.56.4", &a_10_28_56_4);
- ats_ip_pton("10.28.56.255", &a_10_28_56_255);
- ats_ip_pton("10.28.57.0", &a_10_28_57_0);
- ats_ip_pton("63.128.1.12", &a_63_128_1_12);
- ats_ip_pton("::", &a6_0);
- ats_ip_pton("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff", &a6_max);
- ats_ip_pton("fe80::221:9bff:fe10:9d90", &a6_fe80_9d90);
- ats_ip_pton("fe80::221:9bff:fe10:9d9d", &a6_fe80_9d9d);
- ats_ip_pton("fe80::221:9bff:fe10:9d95", &a6_fe80_9d95);
- ats_ip_pton("127.0.0.1", &a_loopback);
- ats_ip_pton("127.0.0.255", &a_loopback2);
-
- map.mark(&a_0, &a_max, markA);
- {
- INFO("IpMap Unmark: Full range not single.");
- CHECK(map.count() == 1);
- }
- map.unmark(&a_10_28_56_0, &a_10_28_56_255);
- {
- INFO("IpMap Unmark: Range unmark failed.");
- CHECK(map.count() == 2);
- }
- // Generic range check.
- {
- INFO("IpMap Unmark: Range unmark min address not removed.");
- CHECK(!map.contains(&a_10_28_56_0));
- }
- {
- INFO("IpMap Unmark: Range unmark max address not removed.");
- CHECK(!map.contains(&a_10_28_56_255));
- }
- {
- INFO("IpMap Unmark: Range unmark min-1 address removed.");
- CHECK(map.contains(&a_10_28_55_255));
- }
- {
- INFO("IpMap Unmark: Range unmark max+1 address removed.");
- CHECK(map.contains(&a_10_28_57_0));
- }
- // Test min bounded range.
- map.unmark(&a_0, &a_0_0_0_16);
- {
- INFO("IpMap Unmark: Range unmark zero address not removed.");
- CHECK(!map.contains(&a_0));
- }
- {
- INFO("IpMap Unmark: Range unmark zero bounded range max not removed.");
- CHECK(!map.contains(&a_0_0_0_16));
- }
- {
- INFO("IpMap Unmark: Range unmark zero bounded range max+1 removed.");
- CHECK(map.contains(&a_0_0_0_17));
- }
-}
-
-TEST_CASE("IpMap Fill", "[libts][ipmap]")
-{
- IpMap map;
- void *const allow = reinterpret_cast<void *>(0);
- void *const deny = reinterpret_cast<void *>(~0);
- void *const markA = reinterpret_cast<void *>(1);
- void *const markB = reinterpret_cast<void *>(2);
- void *const markC = reinterpret_cast<void *>(3);
-
- IpEndpoint a0, a_10_28_56_0, a_10_28_56_4, a_10_28_56_255, a3, a4;
- IpEndpoint a_9_255_255_255, a_10_0_0_0, a_10_0_0_19, a_10_0_0_255, a_10_0_1_0;
- IpEndpoint a_max, a_loopback, a_loopback2;
- IpEndpoint a_10_28_55_255, a_10_28_57_0;
- IpEndpoint a_63_128_1_12;
- IpEndpoint a_0000_0000, a_0000_0001, a_ffff_ffff;
- IpEndpoint a_fe80_9d8f, a_fe80_9d90, a_fe80_9d95, a_fe80_9d9d, a_fe80_9d9e;
-
- ats_ip_pton("0.0.0.0", &a0);
- ats_ip_pton("255.255.255.255", &a_max);
-
- ats_ip_pton("9.255.255.255", &a_9_255_255_255);
- ats_ip_pton("10.0.0.0", &a_10_0_0_0);
- ats_ip_pton("10.0.0.19", &a_10_0_0_19);
- ats_ip_pton("10.0.0.255", &a_10_0_0_255);
- ats_ip_pton("10.0.1.0", &a_10_0_1_0);
-
- ats_ip_pton("10.28.55.255", &a_10_28_55_255);
- ats_ip_pton("10.28.56.0", &a_10_28_56_0);
- ats_ip_pton("10.28.56.4", &a_10_28_56_4);
- ats_ip_pton("10.28.56.255", &a_10_28_56_255);
- ats_ip_pton("10.28.57.0", &a_10_28_57_0);
-
- ats_ip_pton("192.168.1.0", &a3);
- ats_ip_pton("192.168.1.255", &a4);
-
- ats_ip_pton("::", &a_0000_0000);
- ats_ip_pton("::1", &a_0000_0001);
- ats_ip_pton("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff", &a_ffff_ffff);
- ats_ip_pton("fe80::221:9bff:fe10:9d8f", &a_fe80_9d8f);
- ats_ip_pton("fe80::221:9bff:fe10:9d90", &a_fe80_9d90);
- ats_ip_pton("fe80::221:9bff:fe10:9d95", &a_fe80_9d95);
- ats_ip_pton("fe80::221:9bff:fe10:9d9d", &a_fe80_9d9d);
- ats_ip_pton("fe80::221:9bff:fe10:9d9e", &a_fe80_9d9e);
-
- ats_ip_pton("127.0.0.0", &a_loopback);
- ats_ip_pton("127.0.0.255", &a_loopback2);
- ats_ip_pton("63.128.1.12", &a_63_128_1_12);
-
- SECTION("subnet overfill")
- {
- map.fill(&a_10_28_56_0, &a_10_28_56_255, deny);
- map.fill(&a0, &a_max, allow);
- CHECK_THAT(map, IsMarkedWith(a_10_28_56_4, deny));
- }
-
- SECTION("singleton overfill")
- {
- map.fill(&a_loopback, &a_loopback, allow);
- {
- INFO("singleton not marked.");
- CHECK_THAT(map, IsMarkedAt(a_loopback));
- }
- map.fill(&a0, &a_max, deny);
- THEN("singleton mark")
- {
- CHECK_THAT(map, IsMarkedWith(a_loopback, allow));
- THEN("not empty")
- {
- REQUIRE(map.begin() != map.end());
- IpMap::iterator spot = map.begin();
- ++spot;
- THEN("more than one range")
- {
- REQUIRE(spot != map.end());
- THEN("ranges disjoint")
- {
- INFO(" " << map.begin()->max() << " < " << spot->min());
- REQUIRE(-1 == ats_ip_addr_cmp(map.begin()->max(), spot->min()));
- }
- }
- }
- }
- }
-
- SECTION("3")
- {
- map.fill(&a_loopback, &a_loopback2, markA);
- map.fill(&a_10_28_56_0, &a_10_28_56_255, markB);
- {
- INFO("over extended range");
- CHECK_THAT(map, !IsMarkedWith(a_63_128_1_12, markC));
- }
- map.fill(&a0, &a_max, markC);
- {
- INFO("IpMap[2]: Fill failed.");
- CHECK(map.count() == 5);
- }
- {
- INFO("invalid mark in range gap");
- CHECK_THAT(map, IsMarkedWith(a_63_128_1_12, markC));
- }
- }
-
- SECTION("4")
- {
- map.fill(&a_10_0_0_0, &a_10_0_0_255, allow);
- map.fill(&a_loopback, &a_loopback2, allow);
- {
- INFO("invalid mark between ranges");
- CHECK_THAT(map, !IsMarkedAt(a_63_128_1_12));
- }
- {
- INFO("invalid mark in lower range");
- CHECK_THAT(map, IsMarkedWith(a_10_0_0_19, allow));
- }
- map.fill(&a0, &a_max, deny);
- {
- INFO("range count incorrect");
- CHECK(map.count() == 5);
- }
- {
- INFO("mark between ranges");
- CHECK_THAT(map, IsMarkedWith(a_63_128_1_12, deny));
- }
-
- map.fill(&a_fe80_9d90, &a_fe80_9d9d, markA);
- map.fill(&a_0000_0001, &a_0000_0001, markA);
- map.fill(&a_0000_0000, &a_ffff_ffff, markB);
-
- {
- INFO("IpMap Fill[v6]: Zero address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_0000_0000, markB));
- }
- {
- INFO("IpMap Fill[v6]: Max address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_ffff_ffff, markB));
- }
- {
- INFO("IpMap Fill[v6]: 9d90 address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d90, markA));
- }
- {
- INFO("IpMap Fill[v6]: 9d8f address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d8f, markB));
- }
- {
- INFO("IpMap Fill[v6]: 9d9d address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d9d, markA));
- }
- {
- INFO("IpMap Fill[v6]: 9d9b address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d9e, markB));
- }
- {
- INFO("IpMap Fill[v6]: ::1 has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_0000_0001, markA));
- }
-
- {
- INFO("IpMap Fill[pre-refill]: Bad range count.");
- CHECK(map.count() == 10);
- }
- // These should be ignored by the map as it is completely covered for IPv6.
- map.fill(&a_fe80_9d90, &a_fe80_9d9d, markA);
- map.fill(&a_0000_0001, &a_0000_0001, markC);
- map.fill(&a_0000_0000, &a_ffff_ffff, markB);
- {
- INFO("IpMap Fill[post-refill]: Bad range count.");
- CHECK(map.count() == 10);
- }
- }
-
- SECTION("5")
- {
- map.fill(&a_fe80_9d90, &a_fe80_9d9d, markA);
- map.fill(&a_0000_0001, &a_0000_0001, markC);
- map.fill(&a_0000_0000, &a_ffff_ffff, markB);
- {
- INFO("IpMap Fill[v6-2]: Zero address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_0000_0000, markB));
- }
- {
- INFO("IpMap Fill[v6-2]: Max address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_ffff_ffff, markB));
- }
- {
- INFO("IpMap Fill[v6-2]: 9d90 address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d90, markA));
- }
- {
- INFO("IpMap Fill[v6-2]: 9d8f address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d8f, markB));
- }
- {
- INFO("IpMap Fill[v6-2]: 9d9d address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d9d, markA));
- }
- {
- INFO("IpMap Fill[v6-2]: 9d9b address has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_fe80_9d9e, markB));
- }
- {
- INFO("IpMap Fill[v6-2]: ::1 has bad mark.");
- CHECK_THAT(map, IsMarkedWith(a_0000_0001, markC));
- }
- }
-}
-
-TEST_CASE("IpMap CloseIntersection", "[libts][ipmap]")
-{
- IpMap map;
- void *const markA = reinterpret_cast<void *>(1);
- void *const markB = reinterpret_cast<void *>(2);
- void *const markC = reinterpret_cast<void *>(3);
- void *const markD = reinterpret_cast<void *>(4);
-
- IpEndpoint a_1_l, a_1_u, a_2_l, a_2_u, a_3_l, a_3_u, a_4_l, a_4_u, a_5_l, a_5_u, a_6_l, a_6_u, a_7_l, a_7_u;
- IpEndpoint b_1_l, b_1_u;
- IpEndpoint c_1_l, c_1_u, c_2_l, c_2_u, c_3_l, c_3_u;
- IpEndpoint c_3_m;
- IpEndpoint d_1_l, d_1_u, d_2_l, d_2_u;
-
- IpEndpoint a_1_m;
-
- ats_ip_pton("123.88.172.0", &a_1_l);
- ats_ip_pton("123.88.180.93", &a_1_m);
- ats_ip_pton("123.88.191.255", &a_1_u);
- ats_ip_pton("123.89.132.0", &a_2_l);
- ats_ip_pton("123.89.135.255", &a_2_u);
- ats_ip_pton("123.89.160.0", &a_3_l);
- ats_ip_pton("123.89.167.255", &a_3_u);
- ats_ip_pton("123.90.108.0", &a_4_l);
- ats_ip_pton("123.90.111.255", &a_4_u);
- ats_ip_pton("123.90.152.0", &a_5_l);
- ats_ip_pton("123.90.159.255", &a_5_u);
- ats_ip_pton("123.91.0.0", &a_6_l);
- ats_ip_pton("123.91.35.255", &a_6_u);
- ats_ip_pton("123.91.40.0", &a_7_l);
- ats_ip_pton("123.91.47.255", &a_7_u);
-
- ats_ip_pton("123.78.100.0", &b_1_l);
- ats_ip_pton("123.78.115.255", &b_1_u);
-
- ats_ip_pton("123.88.204.0", &c_1_l);
- ats_ip_pton("123.88.219.255", &c_1_u);
- ats_ip_pton("123.90.112.0", &c_2_l);
- ats_ip_pton("123.90.119.255", &c_2_u);
- ats_ip_pton("123.90.132.0", &c_3_l);
- ats_ip_pton("123.90.134.157", &c_3_m);
- ats_ip_pton("123.90.135.255", &c_3_u);
-
- ats_ip_pton("123.82.196.0", &d_1_l);
- ats_ip_pton("123.82.199.255", &d_1_u);
- ats_ip_pton("123.82.204.0", &d_2_l);
- ats_ip_pton("123.82.219.255", &d_2_u);
-
- map.mark(a_1_l, a_1_u, markA);
- map.mark(a_2_l, a_2_u, markA);
- map.mark(a_3_l, a_3_u, markA);
- map.mark(a_4_l, a_4_u, markA);
- map.mark(a_5_l, a_5_u, markA);
- map.mark(a_6_l, a_6_u, markA);
- map.mark(a_7_l, a_7_u, markA);
- CHECK_THAT(map, IsMarkedAt(a_1_m));
-
- map.mark(b_1_l, b_1_u, markB);
- CHECK_THAT(map, IsMarkedWith(a_1_m, markA));
-
- map.mark(c_1_l, c_1_u, markC);
- map.mark(c_2_l, c_2_u, markC);
- map.mark(c_3_l, c_3_u, markC);
- CHECK_THAT(map, IsMarkedWith(a_1_m, markA));
-
- map.mark(d_1_l, d_1_u, markD);
- map.mark(d_2_l, d_2_u, markD);
- CHECK_THAT(map, IsMarkedAt(a_1_m));
- CHECK_THAT(map, IsMarkedWith(b_1_u, markB));
- CHECK_THAT(map, IsMarkedWith(c_3_m, markC));
- CHECK_THAT(map, IsMarkedWith(d_2_l, markD));
-
- CHECK(map.count() == 13);
-
- // Check move constructor.
- IpMap m2{std::move(map)};
- // Original map should be empty.
- REQUIRE(map.count() == 0);
- // Do all these again on the destination map.
- CHECK_THAT(m2, IsMarkedWith(a_1_m, markA));
- CHECK_THAT(m2, IsMarkedWith(a_1_m, markA));
- CHECK_THAT(m2, IsMarkedWith(a_1_m, markA));
- CHECK_THAT(m2, IsMarkedWith(a_1_m, markA));
- CHECK_THAT(m2, IsMarkedWith(b_1_u, markB));
- CHECK_THAT(m2, IsMarkedWith(c_3_m, markC));
- CHECK_THAT(m2, IsMarkedWith(d_2_l, markD));
- CHECK(m2.count() == 13);
-
-#if 0
- ts::LocalBufferWriter<1024> w;
- std::cout << "Basic map dump" << std::endl;
- std::cout << w.print("{}", m2).view() << std::endl;
- w.reset();
- std::cout << "With tree detail" << std::endl;
- std::cout << w.print("{::x}", m2).view() << std::endl;
-#endif
-};