// Copyright 2018 The Abseil Authors.

//

// Licensed 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

//

//      https://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.

// A btree implementation of the STL set and map interfaces. A btree is smaller

// and generally also faster than STL set/map (refer to the benchmarks below).

// The red-black tree implementation of STL set/map has an overhead of 3

// pointers (left, right and parent) plus the node color information for each

// stored value. So a set<int32_t> consumes 40 bytes for each value stored in

// 64-bit mode. This btree implementation stores multiple values on fixed

// size nodes (usually 256 bytes) and doesn't store child pointers for leaf

// nodes. The result is that a btree_set<int32_t> may use much less memory per

// stored value. For the random insertion benchmark in btree_bench.cc, a

// btree_set<int32_t> with node-size of 256 uses 5.1 bytes per stored value.

//

// The packing of multiple values on to each node of a btree has another effect

// besides better space utilization: better cache locality due to fewer cache

// lines being accessed. Better cache locality translates into faster

// operations.

//

// CAVEATS

//

// Insertions and deletions on a btree can cause splitting, merging or

// rebalancing of btree nodes. And even without these operations, insertions

// and deletions on a btree will move values around within a node. In both

// cases, the result is that insertions and deletions can invalidate iterators

// pointing to values other than the one being inserted/deleted. Therefore, this

// container does not provide pointer stability. This is notably different from

// STL set/map which takes care to not invalidate iterators on insert/erase

// except, of course, for iterators pointing to the value being erased.  A

// partial workaround when erasing is available: erase() returns an iterator

// pointing to the item just after the one that was erased (or end() if none

// exists).

#ifndef ABSL_CONTAINER_INTERNAL_BTREE_H_

#define ABSL_CONTAINER_INTERNAL_BTREE_H_

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <cstdint>

#include <cstring>

#include <functional>

#include <iterator>

#include <limits>

#include <new>

#include <string>

#include <type_traits>

#include <utility>

#include "absl/base/internal/raw_logging.h"

#include "absl/base/macros.h"

#include "absl/container/internal/common.h"

#include "absl/container/internal/common_policy_traits.h"

#include "absl/container/internal/compressed_tuple.h"

#include "absl/container/internal/container_memory.h"

#include "absl/container/internal/layout.h"

#include "absl/memory/memory.h"

#include "absl/meta/type_traits.h"

#include "absl/strings/cord.h"

#include "absl/strings/string_view.h"

#include "absl/types/compare.h"

#include "absl/utility/utility.h"

namespace absl {

ABSL_NAMESPACE_BEGIN

namespace container_internal {

#ifdef ABSL_BTREE_ENABLE_GENERATIONS

#error ABSL_BTREE_ENABLE_GENERATIONS cannot be directly set

#elif defined(ABSL_HAVE_ADDRESS_SANITIZER) || \

    defined(ABSL_HAVE_MEMORY_SANITIZER)

// When compiled in sanitizer mode, we add generation integers to the nodes and

// iterators. When iterators are used, we validate that the container has not

// been mutated since the iterator was constructed.

#define ABSL_BTREE_ENABLE_GENERATIONS

#endif

template <typename Compare, typename T, typename U>

using compare_result_t = absl::result_of_t<const Compare(const T &, const U &)>;

// A helper class that indicates if the Compare parameter is a key-compare-to

// comparator.

template <typename Compare, typename T>

using btree_is_key_compare_to =

    std::is_convertible<compare_result_t<Compare, T, T>, absl::weak_ordering>;

struct StringBtreeDefaultLess {

  using is_transparent = void;

  StringBtreeDefaultLess() = default;

  // Compatibility constructor.

  StringBtreeDefaultLess(std::less<std::string>) {}        // NOLINT

  StringBtreeDefaultLess(std::less<absl::string_view>) {}  // NOLINT

  // Allow converting to std::less for use in key_comp()/value_comp().

  explicit operator std::less<std::string>() const { return {}; }

  explicit operator std::less<absl::string_view>() const { return {}; }

  explicit operator std::less<absl::Cord>() const { return {}; }

  absl::weak_ordering operator()(absl::string_view lhs,

                                 absl::string_view rhs) const {

    return compare_internal::compare_result_as_ordering(lhs.compare(rhs));

  }

  StringBtreeDefaultLess(std::less<absl::Cord>) {}  // NOLINT

  absl::weak_ordering operator()(const absl::Cord &lhs,

                                 const absl::Cord &rhs) const {

    return compare_internal::compare_result_as_ordering(lhs.Compare(rhs));

  }

  absl::weak_ordering operator()(const absl::Cord &lhs,

                                 absl::string_view rhs) const {

    return compare_internal::compare_result_as_ordering(lhs.Compare(rhs));

  }

  absl::weak_ordering operator()(absl::string_view lhs,

                                 const absl::Cord &rhs) const {

    return compare_internal::compare_result_as_ordering(-rhs.Compare(lhs));

  }

};

struct StringBtreeDefaultGreater {

  using is_transparent = void;

  StringBtreeDefaultGreater() = default;

  StringBtreeDefaultGreater(std::greater<std::string>) {}        // NOLINT

  StringBtreeDefaultGreater(std::greater<absl::string_view>) {}  // NOLINT

  // Allow converting to std::greater for use in key_comp()/value_comp().

  explicit operator std::greater<std::string>() const { return {}; }

  explicit operator std::greater<absl::string_view>() const { return {}; }

  explicit operator std::greater<absl::Cord>() const { return {}; }

  absl::weak_ordering operator()(absl::string_view lhs,

                                 absl::string_view rhs) const {

    return compare_internal::compare_result_as_ordering(rhs.compare(lhs));

  }

  StringBtreeDefaultGreater(std::greater<absl::Cord>) {}  // NOLINT

  absl::weak_ordering operator()(const absl::Cord &lhs,

                                 const absl::Cord &rhs) const {

    return compare_internal::compare_result_as_ordering(rhs.Compare(lhs));

  }

  absl::weak_ordering operator()(const absl::Cord &lhs,

                                 absl::string_view rhs) const {

    return compare_internal::compare_result_as_ordering(-lhs.Compare(rhs));

  }

  absl::weak_ordering operator()(absl::string_view lhs,

                                 const absl::Cord &rhs) const {

    return compare_internal::compare_result_as_ordering(rhs.Compare(lhs));

  }

};

// See below comments for checked_compare.

template <typename Compare, bool is_class = std::is_class<Compare>::value>

struct checked_compare_base : Compare {

  using Compare::Compare;

  explicit checked_compare_base(Compare c) : Compare(std::move(c)) {}

  const Compare &comp() const { return *this; }

};

template <typename Compare>

struct checked_compare_base<Compare, false> {

  explicit checked_compare_base(Compare c) : compare(std::move(c)) {}

  const Compare &comp() const { return compare; }

  Compare compare;

};

// A mechanism for opting out of checked_compare for use only in btree_test.cc.

struct BtreeTestOnlyCheckedCompareOptOutBase {};

// A helper class to adapt the specified comparator for two use cases:

// (1) When using common Abseil string types with common comparison functors,

// convert a boolean comparison into a three-way comparison that returns an

// `absl::weak_ordering`. This helper class is specialized for

// less<std::string>, greater<std::string>, less<string_view>,

// greater<string_view>, less<absl::Cord>, and greater<absl::Cord>.

// (2) Adapt the comparator to diagnose cases of non-strict-weak-ordering (see

// https://en.cppreference.com/w/cpp/named_req/Compare) in debug mode. Whenever

// a comparison is made, we will make assertions to verify that the comparator

// is valid.

template <typename Compare, typename Key>

struct key_compare_adapter {

  // Inherit from checked_compare_base to support function pointers and also

  // keep empty-base-optimization (EBO) support for classes.

  // Note: we can't use CompressedTuple here because that would interfere

  // with the EBO for `btree::rightmost_`. `btree::rightmost_` is itself a

  // CompressedTuple and nested `CompressedTuple`s don't support EBO.

  // TODO(b/214288561): use CompressedTuple instead once it supports EBO for

  // nested `CompressedTuple`s.

  struct checked_compare : checked_compare_base<Compare> {

   private:

    using Base = typename checked_compare::checked_compare_base;

    using Base::comp;

    // If possible, returns whether `t` is equivalent to itself. We can only do

    // this for `Key`s because we can't be sure that it's safe to call

    // `comp()(k, k)` otherwise. Even if SFINAE allows it, there could be a

    // compilation failure inside the implementation of the comparison operator.

    bool is_self_equivalent(const Key &k) const {

      // Note: this works for both boolean and three-way comparators.

      return comp()(k, k) == 0;

    }

    // If we can't compare `t` with itself, returns true unconditionally.

    template <typename T>

    bool is_self_equivalent(const T &) const {

      return true;

    }

   public:

    using Base::Base;

    checked_compare(Compare comp) : Base(std::move(comp)) {}  // NOLINT

    // Allow converting to Compare for use in key_comp()/value_comp().

    explicit operator Compare() const { return comp(); }

    template <typename T, typename U,

              absl::enable_if_t<

                  std::is_same<bool, compare_result_t<Compare, T, U>>::value,

                  int> = 0>

    bool operator()(const T &lhs, const U &rhs) const {

      // NOTE: if any of these assertions fail, then the comparator does not

      // establish a strict-weak-ordering (see

      // https://en.cppreference.com/w/cpp/named_req/Compare).

      assert(is_self_equivalent(lhs));

      assert(is_self_equivalent(rhs));

      const bool lhs_comp_rhs = comp()(lhs, rhs);

      assert(!lhs_comp_rhs || !comp()(rhs, lhs));

      return lhs_comp_rhs;

    }

    template <

        typename T, typename U,

        absl::enable_if_t<std::is_convertible<compare_result_t<Compare, T, U>,

                                              absl::weak_ordering>::value,

                          int> = 0>

    absl::weak_ordering operator()(const T &lhs, const U &rhs) const {

      // NOTE: if any of these assertions fail, then the comparator does not

      // establish a strict-weak-ordering (see

      // https://en.cppreference.com/w/cpp/named_req/Compare).

      assert(is_self_equivalent(lhs));

      assert(is_self_equivalent(rhs));

      const absl::weak_ordering lhs_comp_rhs = comp()(lhs, rhs);

#ifndef NDEBUG

      const absl::weak_ordering rhs_comp_lhs = comp()(rhs, lhs);

      if (lhs_comp_rhs > 0) {

        assert(rhs_comp_lhs < 0 && "lhs_comp_rhs > 0 -> rhs_comp_lhs < 0");

      } else if (lhs_comp_rhs == 0) {

        assert(rhs_comp_lhs == 0 && "lhs_comp_rhs == 0 -> rhs_comp_lhs == 0");

      } else {

        assert(rhs_comp_lhs > 0 && "lhs_comp_rhs < 0 -> rhs_comp_lhs > 0");

      }

#endif

      return lhs_comp_rhs;

    }

  };

  using type = absl::conditional_t<

      std::is_base_of<BtreeTestOnlyCheckedCompareOptOutBase, Compare>::value,

      Compare, checked_compare>;

};

template <>

struct key_compare_adapter<std::less<std::string>, std::string> {

  using type = StringBtreeDefaultLess;

};

template <>

struct key_compare_adapter<std::greater<std::string>, std::string> {

  using type = StringBtreeDefaultGreater;

};

template <>

struct key_compare_adapter<std::less<absl::string_view>, absl::string_view> {

  using type = StringBtreeDefaultLess;

};

template <>

struct key_compare_adapter<std::greater<absl::string_view>, absl::string_view> {

  using type = StringBtreeDefaultGreater;

};

template <>

struct key_compare_adapter<std::less<absl::Cord>, absl::Cord> {

  using type = StringBtreeDefaultLess;

};

template <>

struct key_compare_adapter<std::greater<absl::Cord>, absl::Cord> {

  using type = StringBtreeDefaultGreater;

};

// Detects an 'absl_btree_prefer_linear_node_search' member. This is

// a protocol used as an opt-in or opt-out of linear search.

//

//  For example, this would be useful for key types that wrap an integer

//  and define their own cheap operator<(). For example:

//

//   class K {

//    public:

//     using absl_btree_prefer_linear_node_search = std::true_type;

//     ...

//    private:

//     friend bool operator<(K a, K b) { return a.k_ < b.k_; }

//     int k_;

//   };

//

//   btree_map<K, V> m;  // Uses linear search

//

// If T has the preference tag, then it has a preference.

// Btree will use the tag's truth value.

template <typename T, typename = void>

struct has_linear_node_search_preference : std::false_type {};

template <typename T, typename = void>

struct prefers_linear_node_search : std::false_type {};

template <typename T>

struct has_linear_node_search_preference<

    T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>>

    : std::true_type {};

template <typename T>

struct prefers_linear_node_search<

    T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>>

    : T::absl_btree_prefer_linear_node_search {};

template <typename Compare, typename Key>

constexpr bool compare_has_valid_result_type() {

  using compare_result_type = compare_result_t<Compare, Key, Key>;

  return std::is_same<compare_result_type, bool>::value ||

         std::is_convertible<compare_result_type, absl::weak_ordering>::value;

}

template <typename original_key_compare, typename value_type>

class map_value_compare {

  template <typename Params>

  friend class btree;

  // Note: this `protected` is part of the API of std::map::value_compare. See

  // https://en.cppreference.com/w/cpp/container/map/value_compare.

 protected:

  explicit map_value_compare(original_key_compare c) : comp(std::move(c)) {}

  original_key_compare comp;  // NOLINT

 public:

  auto operator()(const value_type &lhs, const value_type &rhs) const

      -> decltype(comp(lhs.first, rhs.first)) {

    return comp(lhs.first, rhs.first);

  }

};

template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,

          bool IsMulti, bool IsMap, typename SlotPolicy>

struct common_params : common_policy_traits<SlotPolicy> {

  using original_key_compare = Compare;

  // If Compare is a common comparator for a string-like type, then we adapt it

  // to use heterogeneous lookup and to be a key-compare-to comparator.

  // We also adapt the comparator to diagnose invalid comparators in debug mode.

  // We disable this when `Compare` is invalid in a way that will cause

  // adaptation to fail (having invalid return type) so that we can give a

  // better compilation failure in static_assert_validation. If we don't do

  // this, then there will be cascading compilation failures that are confusing

  // for users.

  using key_compare =

      absl::conditional_t<!compare_has_valid_result_type<Compare, Key>(),

                          Compare,

                          typename key_compare_adapter<Compare, Key>::type>;

  static constexpr bool kIsKeyCompareStringAdapted =

      std::is_same<key_compare, StringBtreeDefaultLess>::value ||

      std::is_same<key_compare, StringBtreeDefaultGreater>::value;

  static constexpr bool kIsKeyCompareTransparent =

      IsTransparent<original_key_compare>::value || kIsKeyCompareStringAdapted;

  static constexpr bool kEnableGenerations =

#ifdef ABSL_BTREE_ENABLE_GENERATIONS

      true;

#else

      false;

#endif

  // A type which indicates if we have a key-compare-to functor or a plain old

  // key-compare functor.

  using is_key_compare_to = btree_is_key_compare_to<key_compare, Key>;

  using allocator_type = Alloc;

  using key_type = Key;

  using size_type = size_t;

  using difference_type = ptrdiff_t;

  using slot_policy = SlotPolicy;

  using slot_type = typename slot_policy::slot_type;

  using value_type = typename slot_policy::value_type;

  using init_type = typename slot_policy::mutable_value_type;

  using pointer = value_type *;

  using const_pointer = const value_type *;

  using reference = value_type &;

  using const_reference = const value_type &;

  using value_compare =

      absl::conditional_t<IsMap,

                          map_value_compare<original_key_compare, value_type>,

                          original_key_compare>;

  using is_map_container = std::integral_constant<bool, IsMap>;

  // For the given lookup key type, returns whether we can have multiple

  // equivalent keys in the btree. If this is a multi-container, then we can.

  // Otherwise, we can have multiple equivalent keys only if all of the

  // following conditions are met:

  // - The comparator is transparent.

  // - The lookup key type is not the same as key_type.

  // - The comparator is not a StringBtreeDefault{Less,Greater} comparator

  //   that we know has the same equivalence classes for all lookup types.

  template <typename LookupKey>

  constexpr static bool can_have_multiple_equivalent_keys() {

    return IsMulti || (IsTransparent<key_compare>::value &&

                       !std::is_same<LookupKey, Key>::value &&

                       !kIsKeyCompareStringAdapted);

  }

  enum {

    kTargetNodeSize = TargetNodeSize,

    // Upper bound for the available space for slots. This is largest for leaf

    // nodes, which have overhead of at least a pointer + 4 bytes (for storing

    // 3 field_types and an enum).

    kNodeSlotSpace = TargetNodeSize - /*minimum overhead=*/(sizeof(void *) + 4),

  };

  // This is an integral type large enough to hold as many slots as will fit a

  // node of TargetNodeSize bytes.

  using node_count_type =

      absl::conditional_t<(kNodeSlotSpace / sizeof(slot_type) >

                           (std::numeric_limits<uint8_t>::max)()),

                          uint16_t, uint8_t>;  // NOLINT

};

// An adapter class that converts a lower-bound compare into an upper-bound

// compare. Note: there is no need to make a version of this adapter specialized

// for key-compare-to functors because the upper-bound (the first value greater

// than the input) is never an exact match.

template <typename Compare>

struct upper_bound_adapter {

  explicit upper_bound_adapter(const Compare &c) : comp(c) {}

  template <typename K1, typename K2>

  bool operator()(const K1 &a, const K2 &b) const {

    // Returns true when a is not greater than b.

    return !compare_internal::compare_result_as_less_than(comp(b, a));

  }

 private:

  Compare comp;

};

enum class MatchKind : uint8_t { kEq, kNe };

template <typename V, bool IsCompareTo>

struct SearchResult {

  V value;

  MatchKind match;

  static constexpr bool HasMatch() { return true; }

  bool IsEq() const { return match == MatchKind::kEq; }

};

// When we don't use CompareTo, `match` is not present.

// This ensures that callers can't use it accidentally when it provides no

// useful information.

template <typename V>

struct SearchResult<V, false> {

  SearchResult() {}

  explicit SearchResult(V v) : value(v) {}

  SearchResult(V v, MatchKind /*match*/) : value(v) {}

  V value;

  static constexpr bool HasMatch() { return false; }

  static constexpr bool IsEq() { return false; }

};

// A node in the btree holding. The same node type is used for both internal

// and leaf nodes in the btree, though the nodes are allocated in such a way

// that the children array is only valid in internal nodes.

template <typename Params>

class btree_node {

  using is_key_compare_to = typename Params::is_key_compare_to;

  using field_type = typename Params::node_count_type;

  using allocator_type = typename Params::allocator_type;

  using slot_type = typename Params::slot_type;

  using original_key_compare = typename Params::original_key_compare;

 public:

  using params_type = Params;

  using key_type = typename Params::key_type;

  using value_type = typename Params::value_type;

  using pointer = typename Params::pointer;

  using const_pointer = typename Params::const_pointer;

  using reference = typename Params::reference;

  using const_reference = typename Params::const_reference;

  using key_compare = typename Params::key_compare;

  using size_type = typename Params::size_type;

  using difference_type = typename Params::difference_type;

  // Btree decides whether to use linear node search as follows:

  //   - If the comparator expresses a preference, use that.

  //   - If the key expresses a preference, use that.

  //   - If the key is arithmetic and the comparator is std::less or

  //     std::greater, choose linear.

  //   - Otherwise, choose binary.

  // TODO(ezb): Might make sense to add condition(s) based on node-size.

  using use_linear_search = std::integral_constant<

      bool, has_linear_node_search_preference<original_key_compare>::value

                ? prefers_linear_node_search<original_key_compare>::value

            : has_linear_node_search_preference<key_type>::value

                ? prefers_linear_node_search<key_type>::value

                : std::is_arithmetic<key_type>::value &&

                      (std::is_same<std::less<key_type>,

                                    original_key_compare>::value ||

                       std::is_same<std::greater<key_type>,

                                    original_key_compare>::value)>;

  // This class is organized by absl::container_internal::Layout as if it had

  // the following structure:

  //   // A pointer to the node's parent.

  //   btree_node *parent;

  //

  //   // When ABSL_BTREE_ENABLE_GENERATIONS is defined, we also have a

  //   // generation integer in order to check that when iterators are

  //   // used, they haven't been invalidated already. Only the generation on

  //   // the root is used, but we have one on each node because whether a node

  //   // is root or not can change.

  //   uint32_t generation;

  //

  //   // The position of the node in the node's parent.

  //   field_type position;

  //   // The index of the first populated value in `values`.

  //   // TODO(ezb): right now, `start` is always 0. Update insertion/merge

  //   // logic to allow for floating storage within nodes.

  //   field_type start;

  //   // The index after the last populated value in `values`. Currently, this

  //   // is the same as the count of values.

  //   field_type finish;

  //   // The maximum number of values the node can hold. This is an integer in

  //   // [1, kNodeSlots] for root leaf nodes, kNodeSlots for non-root leaf

  //   // nodes, and kInternalNodeMaxCount (as a sentinel value) for internal

  //   // nodes (even though there are still kNodeSlots values in the node).

  //   // TODO(ezb): make max_count use only 4 bits and record log2(capacity)

  //   // to free extra bits for is_root, etc.

  //   field_type max_count;

  //

  //   // The array of values. The capacity is `max_count` for leaf nodes and

  //   // kNodeSlots for internal nodes. Only the values in

  //   // [start, finish) have been initialized and are valid.

  //   slot_type values[max_count];

  //

  //   // The array of child pointers. The keys in children[i] are all less

  //   // than key(i). The keys in children[i + 1] are all greater than key(i).

  //   // There are 0 children for leaf nodes and kNodeSlots + 1 children for

  //   // internal nodes.

  //   btree_node *children[kNodeSlots + 1];

  //

  // This class is only constructed by EmptyNodeType. Normally, pointers to the

  // layout above are allocated, cast to btree_node*, and de-allocated within

  // the btree implementation.

  ~btree_node() = default;

  btree_node(btree_node const &) = delete;

  btree_node &operator=(btree_node const &) = delete;

  // Public for EmptyNodeType.

  constexpr static size_type Alignment() {

    static_assert(LeafLayout(1).Alignment() == InternalLayout().Alignment(),

                  "Alignment of all nodes must be equal.");

    return InternalLayout().Alignment();

  }

 protected:

  btree_node() = default;

 private:

  using layout_type =

      absl::container_internal::Layout<btree_node *, uint32_t, field_type,

                                       slot_type, btree_node *>;

  constexpr static size_type SizeWithNSlots(size_type n) {

    return layout_type(

               /*parent*/ 1,

               /*generation*/ params_type::kEnableGenerations ? 1 : 0,

               /*position, start, finish, max_count*/ 4,

               /*slots*/ n,

               /*children*/ 0)

        .AllocSize();

  }

  // A lower bound for the overhead of fields other than slots in a leaf node.

  constexpr static size_type MinimumOverhead() {

    return SizeWithNSlots(1) - sizeof(slot_type);

  }

  // Compute how many values we can fit onto a leaf node taking into account

  // padding.

  constexpr static size_type NodeTargetSlots(const size_type begin,

                                             const size_type end) {

    return begin == end ? begin

           : SizeWithNSlots((begin + end) / 2 + 1) >

                   params_type::kTargetNodeSize

               ? NodeTargetSlots(begin, (begin + end) / 2)

               : NodeTargetSlots((begin + end) / 2 + 1, end);

  }

  constexpr static size_type kTargetNodeSize = params_type::kTargetNodeSize;

  constexpr static size_type kNodeTargetSlots =

      NodeTargetSlots(0, kTargetNodeSize);

  // We need a minimum of 3 slots per internal node in order to perform

  // splitting (1 value for the two nodes involved in the split and 1 value

  // propagated to the parent as the delimiter for the split). For performance

  // reasons, we don't allow 3 slots-per-node due to bad worst case occupancy of

  // 1/3 (for a node, not a b-tree).

  constexpr static size_type kMinNodeSlots = 4;

  constexpr static size_type kNodeSlots =

      kNodeTargetSlots >= kMinNodeSlots ? kNodeTargetSlots : kMinNodeSlots;

  // The node is internal (i.e. is not a leaf node) if and only if `max_count`

  // has this value.

  constexpr static field_type kInternalNodeMaxCount = 0;

  // Leaves can have less than kNodeSlots values.

  constexpr static layout_type LeafLayout(

      const size_type slot_count = kNodeSlots) {

    return layout_type(

        /*parent*/ 1,

        /*generation*/ params_type::kEnableGenerations ? 1 : 0,

        /*position, start, finish, max_count*/ 4,

        /*slots*/ slot_count,

        /*children*/ 0);

  }

  constexpr static layout_type InternalLayout() {

    return layout_type(

        /*parent*/ 1,

        /*generation*/ params_type::kEnableGenerations ? 1 : 0,

        /*position, start, finish, max_count*/ 4,

        /*slots*/ kNodeSlots,

        /*children*/ kNodeSlots + 1);

  }

  constexpr static size_type LeafSize(const size_type slot_count = kNodeSlots) {

    return LeafLayout(slot_count).AllocSize();

  }

  constexpr static size_type InternalSize() {

    return InternalLayout().AllocSize();

  }

  // N is the index of the type in the Layout definition.

  // ElementType<N> is the Nth type in the Layout definition.

  template <size_type N>

  inline typename layout_type::template ElementType<N> *GetField() {

    // We assert that we don't read from values that aren't there.

    assert(N < 4 || is_internal());

    return InternalLayout().template Pointer<N>(reinterpret_cast<char *>(this));

  }

  template <size_type N>

  inline const typename layout_type::template ElementType<N> *GetField() const {

    assert(N < 4 || is_internal());

    return InternalLayout().template Pointer<N>(

        reinterpret_cast<const char *>(this));

  }

  void set_parent(btree_node *p) { *GetField<0>() = p; }

  field_type &mutable_finish() { return GetField<2>()[2]; }

  slot_type *slot(size_type i) { return &GetField<3>()[i]; }

  slot_type *start_slot() { return slot(start()); }

  slot_type *finish_slot() { return slot(finish()); }

  const slot_type *slot(size_type i) const { return &GetField<3>()[i]; }

  void set_position(field_type v) { GetField<2>()[0] = v; }

  void set_start(field_type v) { GetField<2>()[1] = v; }

  void set_finish(field_type v) { GetField<2>()[2] = v; }

  // This method is only called by the node init methods.

  void set_max_count(field_type v) { GetField<2>()[3] = v; }

 public:

  // Whether this is a leaf node or not. This value doesn't change after the

  // node is created.

  bool is_leaf() const { return GetField<2>()[3] != kInternalNodeMaxCount; }

  // Whether this is an internal node or not. This value doesn't change after

  // the node is created.

  bool is_internal() const { return !is_leaf(); }

  // Getter for the position of this node in its parent.

  field_type position() const { return GetField<2>()[0]; }

  // Getter for the offset of the first value in the `values` array.

  field_type start() const {

    // TODO(ezb): when floating storage is implemented, return GetField<2>()[1];

    assert(GetField<2>()[1] == 0);

    return 0;

  }

  // Getter for the offset after the last value in the `values` array.

  field_type finish() const { return GetField<2>()[2]; }

  // Getters for the number of values stored in this node.

  field_type count() const {

    assert(finish() >= start());

    return finish() - start();

  }

  field_type max_count() const {

    // Internal nodes have max_count==kInternalNodeMaxCount.

    // Leaf nodes have max_count in [1, kNodeSlots].

    const field_type max_count = GetField<2>()[3];

    return max_count == field_type{kInternalNodeMaxCount}

               ? field_type{kNodeSlots}

               : max_count;

  }

  // Getter for the parent of this node.

  btree_node *parent() const { return *GetField<0>(); }

  // Getter for whether the node is the root of the tree. The parent of the

  // root of the tree is the leftmost node in the tree which is guaranteed to

  // be a leaf.

  bool is_root() const { return parent()->is_leaf(); }

  void make_root() {

    assert(parent()->is_root());

    set_generation(parent()->generation());

    set_parent(parent()->parent());

  }

  // Gets the root node's generation integer, which is the one used by the tree.

  uint32_t *get_root_generation() const {

    assert(params_type::kEnableGenerations);

    const btree_node *curr = this;

    for (; !curr->is_root(); curr = curr->parent()) continue;

    return const_cast<uint32_t *>(&curr->GetField<1>()[0]);

  }

  // Returns the generation for iterator validation.

  uint32_t generation() const {

    return params_type::kEnableGenerations ? *get_root_generation() : 0;

  }

  // Updates generation. Should only be called on a root node or during node

  // initialization.

  void set_generation(uint32_t generation) {

    if (params_type::kEnableGenerations) GetField<1>()[0] = generation;

  }

  // Updates the generation. We do this whenever the node is mutated.

  void next_generation() {

    if (params_type::kEnableGenerations) ++*get_root_generation();

  }

  // Getters for the key/value at position i in the node.

  const key_type &key(size_type i) const { return params_type::key(slot(i)); }

  reference value(size_type i) { return params_type::element(slot(i)); }

  const_reference value(size_type i) const {

    return params_type::element(slot(i));

  }

  // Getters/setter for the child at position i in the node.

  btree_node *child(field_type i) const { return GetField<4>()[i]; }

  btree_node *start_child() const { return child(start()); }

  btree_node *&mutable_child(field_type i) { return GetField<4>()[i]; }

  void clear_child(field_type i) {

    absl::container_internal::SanitizerPoisonObject(&mutable_child(i));

  }

  void set_child(field_type i, btree_node *c) {

    absl::container_internal::SanitizerUnpoisonObject(&mutable_child(i));

    mutable_child(i) = c;

    c->set_position(i);

  }

  void init_child(field_type i, btree_node *c) {

    set_child(i, c);

    c->set_parent(this);

  }

  // Returns the position of the first value whose key is not less than k.

  template <typename K>

  SearchResult<size_type, is_key_compare_to::value> lower_bound(

      const K &k, const key_compare &comp) const {

    return use_linear_search::value ? linear_search(k, comp)

                                    : binary_search(k, comp);

  }

  // Returns the position of the first value whose key is greater than k.

  template <typename K>

  size_type upper_bound(const K &k, const key_compare &comp) const {

    auto upper_compare = upper_bound_adapter<key_compare>(comp);

    return use_linear_search::value ? linear_search(k, upper_compare).value

                                    : binary_search(k, upper_compare).value;

  }

  template <typename K, typename Compare>

  SearchResult<size_type, btree_is_key_compare_to<Compare, key_type>::value>

  linear_search(const K &k, const Compare &comp) const {

    return linear_search_impl(k, start(), finish(), comp,

                              btree_is_key_compare_to<Compare, key_type>());

  }

  template <typename K, typename Compare>

  SearchResult<size_type, btree_is_key_compare_to<Compare, key_type>::value>

  binary_search(const K &k, const Compare &comp) const {

    return binary_search_impl(k, start(), finish(), comp,

                              btree_is_key_compare_to<Compare, key_type>());

  }

  // Returns the position of the first value whose key is not less than k using

  // linear search performed using plain compare.

  template <typename K, typename Compare>

  SearchResult<size_type, false> linear_search_impl(

      const K &k, size_type s, const size_type e, const Compare &comp,

      std::false_type /* IsCompareTo */) const {

    while (s < e) {

      if (!comp(key(s), k)) {

        break;

      }

      ++s;

    }

    return SearchResult<size_type, false>{s};

  }

  // Returns the position of the first value whose key is not less than k using

  // linear search performed using compare-to.

  template <typename K, typename Compare>

  SearchResult<size_type, true> linear_search_impl(

      const K &k, size_type s, const size_type e, const Compare &comp,

      std::true_type /* IsCompareTo */) const {

    while (s < e) {

      const absl::weak_ordering c = comp(key(s), k);

      if (c == 0) {

        return {s, MatchKind::kEq};

      } else if (c > 0) {

        break;

      }

      ++s;

    }

    return {s, MatchKind::kNe};

  }

  // Returns the position of the first value whose key is not less than k using

  // binary search performed using plain compare.

  template <typename K, typename Compare>

  SearchResult<size_type, false> binary_search_impl(

      const K &k, size_type s, size_type e, const Compare &comp,

      std::false_type /* IsCompareTo */) const {

    while (s != e) {

      const size_type mid = (s + e) >> 1;

      if (comp(key(mid), k)) {

        s = mid + 1;

      } else {

        e = mid;

      }

    }

    return SearchResult<size_type, false>{s};

  }

  // Returns the position of the first value whose key is not less than k using

  // binary search performed using compare-to.

  template <typename K, typename CompareTo>

  SearchResult<size_type, true> binary_search_impl(

      const K &k, size_type s, size_type e, const CompareTo &comp,

      std::true_type /* IsCompareTo */) const {

    if (params_type::template can_have_multiple_equivalent_keys<K>()) {

      MatchKind exact_match = MatchKind::kNe;

      while (s != e) {

        const size_type mid = (s + e) >> 1;

        const absl::weak_ordering c = comp(key(mid), k);

        if (c < 0) {

          s = mid + 1;

        } else {

          e = mid;

          if (c == 0) {

            // Need to return the first value whose key is not less than k,

            // which requires continuing the binary search if there could be

            // multiple equivalent keys.

            exact_match = MatchKind::kEq;

          }

        }

      }

      return {s, exact_match};

    } else {  // Can't have multiple equivalent keys.

      while (s != e) {

        const size_type mid = (s + e) >> 1;

        const absl::weak_ordering c = comp(key(mid), k);

        if (c < 0) {

          s = mid + 1;

        } else if (c > 0) {

          e = mid;

        } else {

          return {mid, MatchKind::kEq};

        }

      }

      return {s, MatchKind::kNe};

    }

  }

  // Emplaces a value at position i, shifting all existing values and

  // children at positions >= i to the right by 1.

  template <typename... Args>

  void emplace_value(field_type i, allocator_type *alloc, Args &&...args);

  // Removes the values at positions [i, i + to_erase), shifting all existing

  // values and children after that range to the left by to_erase. Clears all

  // children between [i, i + to_erase).

  void remove_values(field_type i, field_type to_erase, allocator_type *alloc);

  // Rebalances a node with its right sibling.

  void rebalance_right_to_left(field_type to_move, btree_node *right,

                               allocator_type *alloc);

  void rebalance_left_to_right(field_type to_move, btree_node *right,

                               allocator_type *alloc);

  // Splits a node, moving a portion of the node's values to its right sibling.

  void split(int insert_position, btree_node *dest, allocator_type *alloc);

  // Merges a node with its right sibling, moving all of the values and the

  // delimiting key in the parent node onto itself, and deleting the src node.

  void merge(btree_node *src, allocator_type *alloc);

  // Node allocation/deletion routines.

  void init_leaf(field_type max_count, btree_node *parent) {

    set_generation(0);

    set_parent(parent);

    set_position(0);

    set_start(0);

    set_finish(0);

    set_max_count(max_count);

    absl::container_internal::SanitizerPoisonMemoryRegion(

        start_slot(), max_count * sizeof(slot_type));

  }

  void init_internal(btree_node *parent) {

    init_leaf(kNodeSlots, parent);

    // Set `max_count` to a sentinel value to indicate that this node is

    // internal.

    set_max_count(kInternalNodeMaxCount);

    absl::container_internal::SanitizerPoisonMemoryRegion(

        &mutable_child(start()), (kNodeSlots + 1) * sizeof(btree_node *));

  }

  static void deallocate(const size_type size, btree_node *node,

                         allocator_type *alloc) {

    absl::container_internal::SanitizerUnpoisonMemoryRegion(node, size);

    absl::container_internal::Deallocate<Alignment()>(alloc, node, size);

  }

  // Deletes a node and all of its children.

  static void clear_and_delete(btree_node *node, allocator_type *alloc);

 private:

  template <typename... Args>

  void value_init(const field_type i, allocator_type *alloc, Args &&...args) {

    next_generation();

    absl::container_internal::SanitizerUnpoisonObject(slot(i));

    params_type::construct(alloc, slot(i), std::forward<Args>(args)...);

  }

  void value_destroy(const field_type i, allocator_type *alloc) {

    next_generation();

    params_type::destroy(alloc, slot(i));

    absl::container_internal::SanitizerPoisonObject(slot(i));

  }

  void value_destroy_n(const field_type i, const field_type n,

                       allocator_type *alloc) {

    next_generation();

    for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) {

      params_type::destroy(alloc, s);

      absl::container_internal::SanitizerPoisonObject(s);

    }

  }

  static void transfer(slot_type *dest, slot_type *src, allocator_type *alloc) {

    absl::container_internal::SanitizerUnpoisonObject(dest);

    params_type::transfer(alloc, dest, src);

    absl::container_internal::SanitizerPoisonObject(src);

  }

  // Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`.

  void transfer(const size_type dest_i, const size_type src_i,

                btree_node *src_node, allocator_type *alloc) {

    next_generation();

    transfer(slot(dest_i), src_node->slot(src_i), alloc);

  }

  // Transfers `n` values starting at value `src_i` in `src_node` into the

  // values starting at value `dest_i` in `this`.

  void transfer_n(const size_type n, const size_type dest_i,

                  const size_type src_i, btree_node *src_node,

                  allocator_type *alloc) {

    next_generation();

    for (slot_type *src = src_node->slot(src_i), *end = src + n,

                   *dest = slot(dest_i);

         src != end; ++src, ++dest) {

      transfer(dest, src, alloc);

    }

  }

  // Same as above, except that we start at the end and work our way to the

  // beginning.

  void transfer_n_backward(const size_type n, const size_type dest_i,

                           const size_type src_i, btree_node *src_node,

                           allocator_type *alloc) {

    next_generation();

    for (slot_type *src = src_node->slot(src_i + n), *end = src - n,

                   *dest = slot(dest_i + n);

         src != end; --src, --dest) {

      // If we modified the loop index calculations above to avoid the -1s here,

      // it would result in UB in the computation of `end` (and possibly `src`

      // as well, if n == 0), since slot() is effectively an array index and it

      // is UB to compute the address of any out-of-bounds array element except

      // for one-past-the-end.

      transfer(dest - 1, src - 1, alloc);

    }

  }

  template <typename P>

  friend class btree;

  template <typename N, typename R, typename P>

  friend class btree_iterator;

  friend class BtreeNodePeer;

  friend struct btree_access;

};

template <typename Node>

bool AreNodesFromSameContainer(const Node *node_a, const Node *node_b) {

  // If either node is null, then give up on checking whether they're from the

  // same container. (If exactly one is null, then we'll trigger the

  // default-constructed assert in Equals.)

  if (node_a == nullptr || node_b == nullptr) return true;

  while (!node_a->is_root()) node_a = node_a->parent();

  while (!node_b->is_root()) node_b = node_b->parent();

  return node_a == node_b;

}

class btree_iterator_generation_info_enabled {

 public:

  explicit btree_iterator_generation_info_enabled(uint32_t g)

      : generation_(g) {}

  // Updates the generation. For use internally right before we return an

  // iterator to the user.

  template <typename Node>

  void update_generation(const Node *node) {

    if (node != nullptr) generation_ = node->generation();

  }

  uint32_t generation() const { return generation_; }

  template <typename Node>

  void assert_valid_generation(const Node *node) const {

    if (node != nullptr && node->generation() != generation_) {

      ABSL_INTERNAL_LOG(

          FATAL,

          "Attempting to use an invalidated iterator. The corresponding b-tree "

          "container has been mutated since this iterator was constructed.");

    }

  }

 private:

  // Used to check that the iterator hasn't been invalidated.

  uint32_t generation_;

};

class btree_iterator_generation_info_disabled {

 public:

  explicit btree_iterator_generation_info_disabled(uint32_t) {}

  void update_generation(const void *) {}

  uint32_t generation() const { return 0; }

  void assert_valid_generation(const void *) const {}

};

#ifdef ABSL_BTREE_ENABLE_GENERATIONS

using btree_iterator_generation_info = btree_iterator_generation_info_enabled;

#else

using btree_iterator_generation_info = btree_iterator_generation_info_disabled;

#endif

template <typename Node, typename Reference, typename Pointer>

class btree_iterator : private btree_iterator_generation_info {

  using field_type = typename Node::field_type;

  using key_type = typename Node::key_type;

  using size_type = typename Node::size_type;

  using params_type = typename Node::params_type;

  using is_map_container = typename params_type::is_map_container;

  using node_type = Node;

  using normal_node = typename std::remove_const<Node>::type;

  using const_node = const Node;

  using normal_pointer = typename params_type::pointer;

  using normal_reference = typename params_type::reference;

  using const_pointer = typename params_type::const_pointer;

  using const_reference = typename params_type::const_reference;

  using slot_type = typename params_type::slot_type;

  using iterator =

     btree_iterator<normal_node, normal_reference, normal_pointer>;

  using const_iterator =

      btree_iterator<const_node, const_reference, const_pointer>;

 public:

  // These aliases are public for std::iterator_traits.

  using difference_type = typename Node::difference_type;

  using value_type = typename params_type::value_type;

  using pointer = Pointer;

  using reference = Reference;

  using iterator_category = std::bidirectional_iterator_tag;

  btree_iterator() : btree_iterator(nullptr, -1) {}

  explicit btree_iterator(Node *n) : btree_iterator(n, n->start()) {}

  btree_iterator(Node *n, int p)

      : btree_iterator_generation_info(n != nullptr ? n->generation()

                                                    : ~uint32_t{}),

        node_(n),

        position_(p) {}

  // NOTE: this SFINAE allows for implicit conversions from iterator to

  // const_iterator, but it specifically avoids hiding the copy constructor so

  // that the trivial one will be used when possible.

  template <typename N, typename R, typename P,

            absl::enable_if_t<

                std::is_same<btree_iterator<N, R, P>, iterator>::value &&

                    std::is_same<btree_iterator, const_iterator>::value,

                int> = 0>

  btree_iterator(const btree_iterator<N, R, P> other)  // NOLINT

      : btree_iterator_generation_info(other),

        node_(other.node_),

        position_(other.position_) {}