chromium/third_party/abseil-cpp/absl/container/internal/btree.h

// 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 <string>
#include <type_traits>
#include <utility>

#include "absl/base/config.h"
#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"

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_HWADDRESS_SANITIZER) || \
       defined(ABSL_HAVE_MEMORY_SANITIZER)) &&   \
    !defined(NDEBUG_SANITIZER)  // If defined, performance is important.
// 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

#ifdef ABSL_BTREE_ENABLE_GENERATIONS
constexpr bool BtreeGenerationsEnabled() { return true; }
#else
constexpr bool BtreeGenerationsEnabled() { … }
#endif

compare_result_t;

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

struct StringBtreeDefaultLess { … };

struct StringBtreeDefaultGreater { … };

// See below comments for checked_compare.
template <typename Compare, bool is_class = std::is_class<Compare>::value>
struct checked_compare_base : Compare { … };
checked_compare_base<Compare, false>;

// 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 { … };

template <>
struct key_compare_adapter<std::less<std::string>, std::string> { … };

template <>
struct key_compare_adapter<std::greater<std::string>, std::string> { … };

template <>
struct key_compare_adapter<std::less<absl::string_view>, absl::string_view> { … };

template <>
struct key_compare_adapter<std::greater<absl::string_view>, absl::string_view> { … };

template <>
struct key_compare_adapter<std::less<absl::Cord>, absl::Cord> { … };

template <>
struct key_compare_adapter<std::greater<absl::Cord>, absl::Cord> { … };

// 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 { … };
has_linear_node_search_preference<T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>>;
prefers_linear_node_search<T, absl::void_t<typename T::absl_btree_prefer_linear_node_search>>;

template <typename Compare, typename Key>
constexpr bool compare_has_valid_result_type() { … }

template <typename original_key_compare, typename value_type>
class map_value_compare { … };

template <typename Key, typename Compare, typename Alloc, int TargetNodeSize,
          bool IsMulti, bool IsMap, typename SlotPolicy>
struct common_params : common_policy_traits<SlotPolicy> { … };

// 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 { … };

enum class MatchKind : uint8_t { … };

template <typename V, bool IsCompareTo>
struct SearchResult { … };

// 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.
SearchResult<V, 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 { … };

template <typename Node>
bool AreNodesFromSameContainer(const Node *node_a, const Node *node_b) { … }

class btree_iterator_generation_info_enabled { … };

class btree_iterator_generation_info_disabled { … };

#ifdef ABSL_BTREE_ENABLE_GENERATIONS
using btree_iterator_generation_info = btree_iterator_generation_info_enabled;
#else
btree_iterator_generation_info;
#endif

template <typename Node, typename Reference, typename Pointer>
class btree_iterator : private btree_iterator_generation_info { … };

template <typename Params>
class btree { … };

////
// btree_node methods
template <typename P>
template <typename... Args>
inline void btree_node<P>::emplace_value(const field_type i,
                                         allocator_type *alloc,
                                         Args &&...args) { … }

template <typename P>
inline void btree_node<P>::remove_values(const field_type i,
                                         const field_type to_erase,
                                         allocator_type *alloc) { … }

template <typename P>
void btree_node<P>::rebalance_right_to_left(field_type to_move,
                                            btree_node *right,
                                            allocator_type *alloc) { … }

template <typename P>
void btree_node<P>::rebalance_left_to_right(field_type to_move,
                                            btree_node *right,
                                            allocator_type *alloc) { … }

template <typename P>
void btree_node<P>::split(const int insert_position, btree_node *dest,
                          allocator_type *alloc) { … }

template <typename P>
void btree_node<P>::merge(btree_node *src, allocator_type *alloc) { … }

template <typename P>
void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) { … }

////
// btree_iterator methods

// Note: the implementation here is based on btree_node::clear_and_delete.
template <typename N, typename R, typename P>
auto btree_iterator<N, R, P>::distance_slow(const_iterator other) const
    -> difference_type { … }

template <typename N, typename R, typename P>
void btree_iterator<N, R, P>::increment_slow() { … }

template <typename N, typename R, typename P>
void btree_iterator<N, R, P>::decrement_slow() { … }

////
// btree methods
template <typename P>
template <typename Btree>
void btree<P>::copy_or_move_values_in_order(Btree &other) { … }

template <typename P>
constexpr bool btree<P>::static_assert_validation() { … }

template <typename P>
template <typename K>
auto btree<P>::lower_bound_equal(const K &key) const
    -> std::pair<iterator, bool> { … }

template <typename P>
template <typename K>
auto btree<P>::equal_range(const K &key) -> std::pair<iterator, iterator> { … }

template <typename P>
template <typename K, typename... Args>
auto btree<P>::insert_unique(const K &key, Args &&...args)
    -> std::pair<iterator, bool> { … }

template <typename P>
template <typename K, typename... Args>
inline auto btree<P>::insert_hint_unique(iterator position, const K &key,
                                         Args &&...args)
    -> std::pair<iterator, bool> { … }

template <typename P>
template <typename InputIterator, typename>
void btree<P>::insert_iterator_unique(InputIterator b, InputIterator e, int) { … }

template <typename P>
template <typename InputIterator>
void btree<P>::insert_iterator_unique(InputIterator b, InputIterator e, char) { … }

template <typename P>
template <typename ValueType>
auto btree<P>::insert_multi(const key_type &key, ValueType &&v) -> iterator { … }

template <typename P>
template <typename ValueType>
auto btree<P>::insert_hint_multi(iterator position, ValueType &&v) -> iterator { … }

template <typename P>
template <typename InputIterator>
void btree<P>::insert_iterator_multi(InputIterator b, InputIterator e) { … }

template <typename P>
auto btree<P>::operator=(const btree &other) -> btree & { … }

template <typename P>
auto btree<P>::operator=(btree &&other) noexcept -> btree & { … }

template <typename P>
auto btree<P>::erase(iterator iter) -> iterator { … }

template <typename P>
auto btree<P>::rebalance_after_delete(iterator iter) -> iterator { … }

// Note: we tried implementing this more efficiently by erasing all of the
// elements in [begin, end) at once and then doing rebalancing once at the end
// (rather than interleaving deletion and rebalancing), but that adds a lot of
// complexity, which seems to outweigh the performance win.
template <typename P>
auto btree<P>::erase_range(iterator begin, iterator end)
    -> std::pair<size_type, iterator> { … }

template <typename P>
void btree<P>::clear() { … }

template <typename P>
void btree<P>::swap(btree &other) { … }

template <typename P>
void btree<P>::verify() const { … }

template <typename P>
void btree<P>::rebalance_or_split(iterator *iter) { … }

template <typename P>
void btree<P>::merge_nodes(node_type *left, node_type *right) { … }

template <typename P>
bool btree<P>::try_merge_or_rebalance(iterator *iter) { … }

template <typename P>
void btree<P>::try_shrink() { … }

template <typename P>
template <typename IterType>
inline IterType btree<P>::internal_last(IterType iter) { … }

template <typename P>
template <typename... Args>
inline auto btree<P>::internal_emplace(iterator iter, Args &&...args)
    -> iterator { … }

template <typename P>
template <typename K>
inline auto btree<P>::internal_locate(const K &key) const
    -> SearchResult<iterator, is_key_compare_to::value> { … }

template <typename P>
template <typename K>
auto btree<P>::internal_lower_bound(const K &key) const
    -> SearchResult<iterator, is_key_compare_to::value> { … }

template <typename P>
template <typename K>
auto btree<P>::internal_upper_bound(const K &key) const -> iterator { … }

template <typename P>
template <typename K>
auto btree<P>::internal_find(const K &key) const -> iterator { … }

template <typename P>
typename btree<P>::size_type btree<P>::internal_verify(
    const node_type *node, const key_type *lo, const key_type *hi) const { … }

struct btree_access { … };

#undef ABSL_BTREE_ENABLE_GENERATIONS

}  // namespace container_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_CONTAINER_INTERNAL_BTREE_H_