custom_containers.h | Explore in Territory

/* Copyright (c) 2015-2017, 2019-2024 The Khronos Group Inc.
 * Copyright (c) 2015-2017, 2019-2024 Valve Corporation
 * Copyright (c) 2015-2017, 2019-2024 LunarG, Inc.
 *
 * 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
 *
 *     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 <cmath>

#include <cassert>
#include <limits>
#include <memory>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iterator>
#include <type_traits>
#include <optional>
#include <utility>

#ifdef USE_ROBIN_HOOD_HASHING
#include "robin_hood.h"
#else
#include <unordered_set>
#endif

#include <vulkan/utility/vk_concurrent_unordered_map.hpp>

// namespace aliases to allow map and set implementations to easily be swapped out
namespace vvl {

#ifdef USE_ROBIN_HOOD_HASHING
template <typename T>
using hash = robin_hood::hash<T>;

template <typename Key, typename Hash = robin_hood::hash<Key>, typename KeyEqual = std::equal_to<Key>>
using unordered_set = robin_hood::unordered_set<Key, Hash, KeyEqual>;

template <typename Key, typename T, typename Hash = robin_hood::hash<Key>, typename KeyEqual = std::equal_to<Key>>
using unordered_map = robin_hood::unordered_map<Key, T, Hash, KeyEqual>;

template <typename Key, typename T>
using map_entry = robin_hood::pair<Key, T>;

// robin_hood-compatible insert_iterator (std:: uses the wrong insert method)
// NOTE: std::iterator was deprecated in C++17, and newer versions of libstdc++ appear to mark this as such.
template <typename T>
struct insert_iterator {
    using iterator_category = std::output_iterator_tag;
    using value_type = typename T::value_type;
    using iterator = typename T::iterator;
    using difference_type = void;
    using pointer = void;
    using reference = T &;

    insert_iterator(reference t, iterator i) : container(&t), iter(i) {}

    insert_iterator &operator=(const value_type &value) {
        auto result = container->insert(value);
        iter = result.first;
        ++iter;
        return *this;
    }

    insert_iterator &operator=(value_type &&value) {
        auto result = container->insert(std::move(value));
        iter = result.first;
        ++iter;
        return *this;
    }

    insert_iterator &operator*() { return *this; }

    insert_iterator &operator++() { return *this; }

    insert_iterator &operator++(int) { return *this; }

  private:
    T *container;
    iterator iter;
};
#else
hash;

unordered_set;

unordered_map;

map_entry;

insert_iterator;
#endif

#if 1
concurrent_unordered_map;
#else
template <typename Key, typename T, int BucketsLog2 = 2>
using concurrent_unordered_map = vku::concurrent_unordered_map<Key, T, BucketsLog2, vvl::unordered_map<Key, T>>;
#endif

}  // namespace vvl

// A vector class with "small string optimization" -- meaning that the class contains a fixed working store for N elements.
// Useful in in situations where the needed size is unknown, but the typical size is known  If size increases beyond the
// fixed capacity, a dynamically allocated working store is created.
//
// NOTE: Unlike std::vector which only requires T to be CopyAssignable and CopyConstructable, small_vector requires T to be
//       MoveAssignable and MoveConstructable
// NOTE: Unlike std::vector, iterators are invalidated by move assignment between small_vector objects effectively the
//       "small string" allocation functions as an incompatible allocator.
template <typename T, size_t N, typename SizeType = uint32_t>
class small_vector { … };

// This is a wrapper around unordered_map that optimizes for the common case
// of only containing a small number of elements. The first N elements are stored
// inline in the object and don't require hashing or memory (de)allocation.

template <typename Key, typename value_type, typename inner_container_type, typename value_type_helper, int N>
class small_container { … };

// Helper function objects to compare/assign/get keys in small_unordered_set/map.
// This helps to abstract away whether value_type is a Key or a pair<Key, T>.
template <typename MapType>
class value_type_helper_map { … };

template <typename Key>
class value_type_helper_set { … };

template <typename Key, typename T, int N = 1>
class small_unordered_map : public small_container<Key, typename vvl::unordered_map<Key, T>::value_type, vvl::unordered_map<Key, T>,
                                                   value_type_helper_map<vvl::unordered_map<Key, T>>, N> { … };

template <typename Key, int N = 1>
class small_unordered_set : public small_container<Key, Key, vvl::unordered_set<Key>, value_type_helper_set<Key>, N> { … };

// For the given data key, look up the layer_data instance from given layer_data_map
template <typename DATA_T>
DATA_T *GetLayerDataPtr(void *data_key, small_unordered_map<void *, DATA_T *, 2> &layer_data_map) { … }

template <typename DATA_T>
void FreeLayerDataPtr(void *data_key, small_unordered_map<void *, DATA_T *, 2> &layer_data_map) { … }

// For the given data key, look up the layer_data instance from given layer_data_map
template <typename DATA_T>
DATA_T *GetLayerDataPtr(void *data_key, std::unordered_map<void *, DATA_T *> &layer_data_map) { … }

template <typename DATA_T>
void FreeLayerDataPtr(void *data_key, std::unordered_map<void *, DATA_T *> &layer_data_map) { … }

namespace vvl {

inline constexpr std::in_place_t in_place{ … };

// Partial implementation of std::span for C++11
template <typename T, typename Iterator>
class enumeration { … };

template <typename T, typename IndexType = size_t>
class IndexedIterator { … };

span;

//
// Allow type inference that using the constructor doesn't allow in C++11
template <typename T>
span<T> make_span(T *begin, size_t count) { … }
template <typename T>
span<T> make_span(T *begin, T *end) { … }

template <typename T, typename IndexType>
enumeration<T, IndexedIterator<T, IndexType>> enumerate(T *begin, IndexType count) { … }
template <typename T>
enumeration<T, IndexedIterator<T>> enumerate(T *begin, T *end) { … }

template <typename Container>
enumeration<typename Container::value_type, IndexedIterator<typename Container::value_type, typename Container::size_type>>
enumerate(Container &container) { … }

base_type;

// Helper for thread local Validate -> Record phase data
// Define T unique to each entrypoint which will persist data
// Use only in with singleton (leaf) validation objects
// State machine transition state changes of payload relative to TlsGuard object lifecycle:
//  State INIT: bool(payload_)
//  State RESET: NOT bool(payload_)
//    * PreCallValidate* phase
//        * Initialized with skip (in PreCallValidate*)
//            * RESET -> INIT
//        * Destruct with skip == true
//           * INIT -> RESET
//    * PreCallRecord* phase (optional IF PostCallRecord present)
//        * Initialized w/o skip (set "persist_" IFF PostCallRecord present)
//           * Must be in state INIT
//        * Destruct with NOT persist_
//           * INIT -> RESET
//    * PreCallRecord* phase (optional IF PreCallRecord present)
//        * Initialized w/o skip ("persist_" *must be false)
//           * Must be in state INIT
//        * Destruct
//           * INIT -> RESET

struct TlsGuardPersist { … };
template <typename T>
class TlsGuard { … };

// Only use this if you aren't planning to use what you would have gotten from a find.
template <typename Container, typename Key = typename Container::key_type>
bool Contains(const Container &container, const Key &key) { … }

//
// if (vvl::Contains(objects_vector, candidate)) { candidate->jump(); }
//
template <typename T>
bool Contains(const std::vector<T> &v, const T &value) { … }

//
// if (auto* thing = vvl::Find(map, key)) { thing->jump(); }
//
template <typename Container, typename Key = typename Container::key_type, typename Value = typename Container::mapped_type>
Value *Find(Container &container, const Key &key) { … }
template <typename Container, typename Key = typename Container::key_type, typename Value = typename Container::mapped_type>
const Value *Find(const Container &container, const Key &key) { … }

// EraseIf is not implemented as std::erase(std::remove_if(...), ...) for two reasons:
//   1) Robin Hood containers don't support two-argument erase functions
//   2) STL remove_if requires the predicate to be const w.r.t the value-type, and std::erase_if doesn't AFAICT
template <typename Container, typename Predicate>
typename Container::size_type EraseIf(Container &c, Predicate &&p) { … }

template <typename T>
constexpr T MaxTypeValue([[maybe_unused]] T) { … }

template <typename T>
constexpr T MinTypeValue([[maybe_unused]] T) { … }

// Typesafe UINT32_MAX
constexpr auto kU32Max = …;
// Typesafe UINT64_MAX
constexpr auto kU64Max = …;
// Typesafe INT32_MAX
constexpr auto kI32Max = …;
// Typesafe INT64_MAX
constexpr auto kI64Max = …;

// Descriptive names to indicate uninitialized/invalid unsigned index values
constexpr auto kNoIndex32 = …;
constexpr auto kNoIndex64 = …;

template <typename T>
T GetQuotientCeil(T numerator, T denominator) { … }

}  // namespace vvl
chromium/third_party/vulkan-validation-layers/src/layers/containers/custom_containers.h
