include/tscore/IpMap.h - trafficserver - Git at Google

 /** @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
	/** @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