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