chromium/base/containers/flat_tree.h

// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
#pragma allow_unsafe_buffers
#endif

#ifndef BASE_CONTAINERS_FLAT_TREE_H_
#define BASE_CONTAINERS_FLAT_TREE_H_

#include <algorithm>
#include <array>
#include <compare>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <ranges>
#include <type_traits>
#include <utility>

#include "base/check.h"
#include "base/compiler_specific.h"
#include "base/memory/raw_ptr_exclusion.h"
#include "base/ranges/algorithm.h"

namespace base {

// Tag type that allows skipping the sort_and_unique step when constructing a
// flat_tree in case the underlying container is already sorted and has no
// duplicate elements.
struct sorted_unique_t { … };
inline constexpr sorted_unique_t sorted_unique;

namespace internal {

// Helper functions used in DCHECKs below to make sure that inputs tagged with
// sorted_unique are indeed sorted and unique.
template <typename Range, typename Comp>
constexpr bool is_sorted_and_unique(const Range& range, Comp comp) { … }

// Helper inspired by C++20's std::to_array to convert a C-style array to a
// std::array. As opposed to the C++20 version this implementation does not
// provide an overload for rvalues and does not strip cv qualifers from the
// returned std::array::value_type. The returned value_type needs to be
// specified explicitly, allowing the construction of std::arrays with const
// elements.
//
// Reference: https://en.cppreference.com/w/cpp/container/array/to_array
template <typename U, typename T, size_t N, size_t... I>
constexpr std::array<U, N> ToArrayImpl(const T (&data)[N],
                                       std::index_sequence<I...>) { … }

template <typename U, typename T, size_t N>
constexpr std::array<U, N> ToArray(const T (&data)[N]) { … }

// Helper that calls `container.reserve(std::size(source))`.
template <typename T, typename U>
void ReserveIfSupported(T& container, const U& source) { … }

// Implementation -------------------------------------------------------------

// Implementation for the sorted associative flat_set and flat_map using a
// sorted vector as the backing store. Do not use directly.
//
// The use of "value" in this is like std::map uses, meaning it's the thing
// contained (in the case of map it's a <Key, Mapped> pair). The Key is how
// things are looked up. In the case of a set, Key == Value. In the case of
// a map, the Key is a component of a Value.
//
// The helper class GetKeyFromValue provides the means to extract a key from a
// value for comparison purposes. It should implement:
//   const Key& operator()(const Value&).
template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
class flat_tree { … };

// ----------------------------------------------------------------------------
// Lifetime.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    const KeyCompare& comp)
    : … { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class InputIterator>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    InputIterator first,
    InputIterator last,
    const KeyCompare& comp)
    : comp_(comp), body_(first, last) { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    const container_type& items,
    const KeyCompare& comp)
    : … { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    container_type&& items,
    const KeyCompare& comp)
    : … { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    std::initializer_list<value_type> ilist,
    const KeyCompare& comp)
    : … { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class InputIterator>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    sorted_unique_t,
    InputIterator first,
    InputIterator last,
    const KeyCompare& comp)
    : comp_(comp), body_(first, last) { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    sorted_unique_t,
    const container_type& items,
    const KeyCompare& comp)
    : … { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    sorted_unique_t,
    container_type&& items,
    const KeyCompare& comp)
    : … { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
    sorted_unique_t,
    std::initializer_list<value_type> ilist,
    const KeyCompare& comp)
    : … { … }

// ----------------------------------------------------------------------------
// Assignments.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::operator=(
    std::initializer_list<value_type> ilist) -> flat_tree& { … }

// ----------------------------------------------------------------------------
// Memory management.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::reserve(
    size_type new_capacity) { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::capacity() const
    -> size_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::shrink_to_fit() { … }

// ----------------------------------------------------------------------------
// Size management.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::clear() { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::size()
    const -> size_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr auto
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::max_size() const
    -> size_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::empty()
    const { … }

// ----------------------------------------------------------------------------
// Iterators.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin()
    -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin()
    const -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cbegin() const
    -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end() -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end()
    const -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cend() const
    -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin()
    -> reverse_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin() const
    -> const_reverse_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crbegin() const
    -> const_reverse_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend()
    -> reverse_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend() const
    -> const_reverse_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crend() const
    -> const_reverse_iterator { … }

// ----------------------------------------------------------------------------
// Insert operations.
//
// Currently we use position_hint the same way as eastl or boost:
// https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
    const value_type& val) -> std::pair<iterator, bool> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
    value_type&& val) -> std::pair<iterator, bool> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
    const_iterator position_hint,
    const value_type& val) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
    const_iterator position_hint,
    value_type&& val) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class InputIterator>
void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
    InputIterator first,
    InputIterator last) { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class... Args>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace(
    Args&&... args) -> std::pair<iterator, bool> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class... Args>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_hint(
    const_iterator position_hint,
    Args&&... args) -> iterator { … }

// ----------------------------------------------------------------------------
// Underlying type operations.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::
    extract() && -> container_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::replace(
    container_type&& body) { … }

// ----------------------------------------------------------------------------
// Erase operations.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
    iterator position) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename DummyT>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
    const_iterator position) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
    const Key& val) -> size_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(const K& val)
    -> size_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
    const_iterator first,
    const_iterator last) -> iterator { … }

// ----------------------------------------------------------------------------
// Comparators.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr auto
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::key_comp() const
    -> key_compare { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
constexpr auto
flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::value_comp() const
    -> value_compare { … }

// ----------------------------------------------------------------------------
// Search operations.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::count(
    const K& key) const -> size_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::count(
    const Key& key) const -> size_type { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(
    const Key& key) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(
    const Key& key) const -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(const K& key)
    -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(
    const K& key) const -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::contains(
    const Key& key) const { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::contains(
    const K& key) const { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
    const Key& key) -> std::pair<iterator, iterator> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
    const Key& key) const -> std::pair<const_iterator, const_iterator> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
    const K& key) -> std::pair<iterator, iterator> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
    const K& key) const -> std::pair<const_iterator, const_iterator> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
    const Key& key) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
    const Key& key) const -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
    const K& key) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
    const K& key) const -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
    const Key& key) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
    const Key& key) const -> const_iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
    const K& key) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
    const K& key) const -> const_iterator { … }

// ----------------------------------------------------------------------------
// General operations.

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::swap(
    flat_tree& other) noexcept { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class... Args>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::unsafe_emplace(
    const_iterator position,
    Args&&... args) -> iterator { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class K, class... Args>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_key_args(
    const K& key,
    Args&&... args) -> std::pair<iterator, bool> { … }

template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <class K, class... Args>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::
    emplace_hint_key_args(const_iterator hint, const K& key, Args&&... args)
        -> std::pair<iterator, bool> { … }

}  // namespace internal

// ----------------------------------------------------------------------------
// Free functions.

// Erases all elements that match predicate. It has O(size) complexity.
template <class Key,
          class GetKeyFromValue,
          class KeyCompare,
          class Container,
          typename Predicate>
size_t EraseIf(
    base::internal::flat_tree<Key, GetKeyFromValue, KeyCompare, Container>&
        container,
    Predicate pred) { … }

}  // namespace base

#endif  // BASE_CONTAINERS_FLAT_TREE_H_