src/tscore/IpMap.cc

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

//----------------------------------------------------------------------------
//----------------------------------------------------------------------------