/* Copyright (c) 2019-2024 The Khronos Group Inc. * Copyright (c) 2019-2024 Valve Corporation * Copyright (c) 2019-2024 LunarG, Inc. * Copyright (C) 2019-2024 Google 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. * * John Zulauf <[email protected]> * */ #pragma once #include <algorithm> #include <cassert> #include <limits> #include <map> #include <string> #include <sstream> #include <utility> #include <cstdint> #include "custom_containers.h" #define RANGE_ASSERT(b) … namespace sparse_container { // range_map // // Implements an ordered map of non-overlapping, non-empty ranges // template <typename Index> struct range { … }; template <typename Range> class range_view { … }; template <typename Range> std::string string_range(const Range &range) { … } template <typename Range> std::string string_range_hex(const Range &range) { … } // Type parameters for the range_map(s) struct insert_range_no_split_bounds { … }; struct insert_range_split_bounds { … }; struct split_op_keep_both { … }; struct split_op_keep_lower { … }; struct split_op_keep_upper { … }; enum class value_precedence { … }; template <typename Iterator, typename Map, typename Range> Iterator split(Iterator in, Map &map, const Range &range); // The range based sparse map implemented on the ImplMap template <typename Key, typename T, typename RangeKey = range<Key>, typename ImplMap = std::map<RangeKey, T>> class range_map { public: protected: using MapKey = RangeKey; ImplMap impl_map_; using ImplIterator = typename ImplMap::iterator; using ImplConstIterator = typename ImplMap::const_iterator; public: using mapped_type = typename ImplMap::mapped_type; using value_type = typename ImplMap::value_type; using key_type = typename ImplMap::key_type; using index_type = typename key_type::index_type; using size_type = typename ImplMap::size_type; protected: template <typename ThisType> using ConstCorrectImplIterator = decltype(std::declval<ThisType>().impl_begin()); template <typename ThisType, typename WrappedIterator = ConstCorrectImplIterator<ThisType>> static WrappedIterator lower_bound_impl(ThisType &that, const key_type &key) { … } ImplIterator lower_bound_impl(const key_type &key) { … } ImplConstIterator lower_bound_impl(const key_type &key) const { … } template <typename ThisType, typename WrappedIterator = ConstCorrectImplIterator<ThisType>> static WrappedIterator upper_bound_impl(ThisType &that, const key_type &key) { … } ImplIterator upper_bound_impl(const key_type &key) { … } ImplConstIterator upper_bound_impl(const key_type &key) const { … } ImplIterator impl_find(const key_type &key) { … } ImplConstIterator impl_find(const key_type &key) const { … } bool impl_not_found(const key_type &key) const { … } ImplIterator impl_end() { … } ImplConstIterator impl_end() const { … } ImplIterator impl_begin() { … } ImplConstIterator impl_begin() const { … } inline bool at_impl_end(const ImplIterator &pos) { … } inline bool at_impl_end(const ImplConstIterator &pos) const { … } inline bool at_impl_begin(const ImplIterator &pos) { … } inline bool at_impl_begin(const ImplConstIterator &pos) const { … } ImplIterator impl_erase(const ImplIterator &pos) { … } template <typename Value> ImplIterator impl_insert(const ImplIterator &hint, Value &&value) { … } ImplIterator impl_insert(const ImplIterator &hint, const key_type &key, const mapped_type &value) { … } ImplIterator impl_insert(const ImplIterator &hint, const index_type &begin, const index_type &end, const mapped_type &value) { … } template <typename SplitOp> ImplIterator split_impl(const ImplIterator &split_it, const index_type &index, const SplitOp &) { … } // do an ranged insert that splits existing ranges at the boundaries, and writes value to any non-initialized sub-ranges range<ImplIterator> infill_and_split(const key_type &bounds, const mapped_type &value, ImplIterator lower, bool split_bounds) { … } template <typename TouchOp> ImplIterator impl_erase_range(const key_type &bounds, ImplIterator lower, const TouchOp &touch_mapped_value) { … } template <typename ValueType, typename WrappedIterator_> struct iterator_impl { public: friend class range_map; using WrappedIterator = WrappedIterator_; private: WrappedIterator pos_; // Create an iterator at a specific internal state -- only from the parent container iterator_impl(const WrappedIterator &pos) : pos_(pos) {} public: iterator_impl() : iterator_impl(WrappedIterator()){}; iterator_impl(const iterator_impl &other) : pos_(other.pos_){}; iterator_impl &operator=(const iterator_impl &rhs) { pos_ = rhs.pos_; return *this; } inline bool operator==(const iterator_impl &rhs) const { return pos_ == rhs.pos_; } inline bool operator!=(const iterator_impl &rhs) const { return pos_ != rhs.pos_; } ValueType &operator*() const { return *pos_; } ValueType *operator->() const { return &*pos_; } iterator_impl &operator++() { ++pos_; return *this; } iterator_impl &operator--() { --pos_; return *this; } // To allow for iterator -> const_iterator construction // NOTE: while it breaks strict encapsulation, it does so less than friend const WrappedIterator &get_pos() const { return pos_; }; }; public: using iterator = iterator_impl<value_type, ImplIterator>; // The const iterator must be derived to allow the conversion from iterator, which iterator doesn't support class const_iterator : public iterator_impl<const value_type, ImplConstIterator> { using Base = iterator_impl<const value_type, ImplConstIterator>; friend range_map; public: const_iterator &operator=(const const_iterator &other) { Base::operator=(other); return *this; } const_iterator(const const_iterator &other) : Base(other){}; const_iterator(const iterator &it) : Base(ImplConstIterator(it.get_pos())) {} const_iterator() : Base() {} private: const_iterator(const ImplConstIterator &pos) : Base(pos) {} }; protected: inline bool at_end(const iterator &it) { … } inline bool at_end(const const_iterator &it) const { … } inline bool at_begin(const iterator &it) { … } template <typename That, typename Iterator> static bool is_contiguous_impl(That *const that, const key_type &range, const Iterator &lower) { … } public: iterator end() { … } // policy and bounds don't matter for end const_iterator end() const { … } // policy and bounds don't matter for end iterator begin() { … } // with default policy, and thus no bounds const_iterator begin() const { … } // with default policy, and thus no bounds const_iterator cbegin() const { … } // with default policy, and thus no bounds const_iterator cend() const { … } // with default policy, and thus no bounds iterator erase(const iterator &pos) { … } iterator erase(range<iterator> bounds) { … } iterator erase(iterator first, iterator last) { … } // Before trying to erase a range, function touch_mapped_value is called on the mapped value. // touch_mapped_value is allowed to have it's parameter type to be non const reference. // If it returns true, regular erase will occur. // Else, range is kept. template <typename TouchOp> iterator erase_range_or_touch(const key_type &bounds, const TouchOp &touch_mapped_value) { … } iterator erase_range(const key_type &bounds) { … } void clear() { … } iterator find(const key_type &key) { … } const_iterator find(const key_type &key) const { … } iterator find(const index_type &index) { … } const_iterator find(const index_type &index) const { … } iterator lower_bound(const key_type &key) { … } const_iterator lower_bound(const key_type &key) const { … } iterator upper_bound(const key_type &key) { … } const_iterator upper_bound(const key_type &key) const { … } range<iterator> bounds(const key_type &key) { … } range<const_iterator> cbounds(const key_type &key) const { … } range<const_iterator> bounds(const key_type &key) const { … } using insert_pair = std::pair<iterator, bool>; // This is traditional no replacement insert. insert_pair insert(const value_type &value) { … }; iterator insert(const_iterator hint, const value_type &value) { … } // Try to insert value. If insertion failed, recursively split union of retrieved stored range with inserted range. // Split at intersection of stored range and inserted range. // Range intersection is merged using merge_op. // Ranges before and after this intersection are recursively inserted. // merge_pos should have this signature: (mapped_type& current_value, const mapped_type& new_value) -> void template <typename MergeOp> iterator split_and_merge_insert(const value_type &value, const MergeOp &merge_op) { … } template <typename SplitOp> iterator split(const iterator whole_it, const index_type &index, const SplitOp &split_op) { … } // The overwrite hint here is lower.... and if it's not right... this fails template <typename Value> iterator overwrite_range(const iterator &lower, Value &&value) { … } template <typename Value> iterator overwrite_range(Value &&value) { … } bool empty() const { … } size_type size() const { … } // For configuration/debug use // Use with caution... ImplMap &get_implementation_map() { … } const ImplMap &get_implementation_map() const { … } }; const_correct_iterator; // The an array based small ordered map for range keys for use as the range map "ImplMap" as an alternate to std::map // // Assumes RangeKey::index_type is unsigned (TBD is it useful to generalize to unsigned?) // Assumes RangeKey implements begin, end, < and (TBD) from template range above template <typename Key, typename T, typename RangeKey = range<Key>, size_t N = 64, typename SmallIndex = uint8_t> class small_range_map { … }; // Forward index iterator, tracking an index value and the appropos lower bound // returns an index_type, lower_bound pair. Supports ++, offset, and seek affecting the index, // lower bound updates as needed. As the index may specify a range for which no entry exist, dereferenced // iterator includes an "valid" field, true IFF the lower_bound is not end() and contains [index, index +1) // // Must be explicitly invalidated when the underlying map is changed. template <typename Map> class cached_lower_bound_impl { … }; template <typename CachedLowerBound, typename MappedType = typename CachedLowerBound::mapped_type> const MappedType &evaluate(const CachedLowerBound &clb, const MappedType &default_value) { … } // Split a range into pieces bound by the intersection of the iterator's range and the supplied range template <typename Iterator, typename Map, typename Range> Iterator split(Iterator in, Map &map, const Range &range) { … } // Apply an operation over a range map, infilling where content is absent, updating where content is present. // The passed pos must *either* be strictly less than range or *is* lower_bound (which may be end) // Trims to range boundaries. // infill op doesn't have to alter map, but mustn't invalidate iterators passed to it. (i.e. no erasure) // infill data (default mapped value or other initial value) is contained with ops. // update allows existing ranges to be updated (merged, whatever) based on data contained in ops. All iterators // passed to update are already trimmed to fit within range. template <typename RangeMap, typename InfillUpdateOps, typename Iterator = typename RangeMap::iterator> Iterator infill_update_range(RangeMap &map, Iterator pos, const typename RangeMap::key_type &range, const InfillUpdateOps &ops) { … } template <typename RangeMap, typename InfillUpdateOps> void infill_update_range(RangeMap &map, const typename RangeMap::key_type &range, const InfillUpdateOps &ops) { … } template <typename RangeMap, typename RangeGen, typename InfillUpdateOps> void infill_update_rangegen(RangeMap &map, RangeGen &range_gen, const InfillUpdateOps &ops) { … } // Parallel iterator // Traverse to range maps over the the same range, but without assumptions of aligned ranges. // ++ increments to the next point where on of the two maps changes range, giving a range over which the two // maps do not transition ranges template <typename MapA, typename MapB = MapA, typename KeyType = typename MapA::key_type> class parallel_iterator { … }; template <typename DstRangeMap, typename SrcRangeMap, typename Updater, typename SourceIterator = typename SrcRangeMap::const_iterator> bool splice(DstRangeMap &to, const SrcRangeMap &from, SourceIterator begin, SourceIterator end, const Updater &updater) { … } // And short hand for "from begin to end" template <typename DstRangeMap, typename SrcRangeMap, typename Updater> bool splice(DstRangeMap &to, const SrcRangeMap &from, const Updater &updater) { … } template <typename T> struct update_prefer_source { … }; template <typename T> struct update_prefer_dest { … }; template <typename RangeMap, typename SourceIterator = typename RangeMap::const_iterator> bool splice(RangeMap &to, const RangeMap &from, value_precedence arbiter, [[maybe_unused]] SourceIterator begin, [[maybe_unused]] SourceIterator end) { … } // And short hand for "from begin to end" template <typename RangeMap> bool splice(RangeMap &to, const RangeMap &from, value_precedence arbiter) { … } template <typename Map, typename Range = typename Map::key_type, typename MapValue = typename Map::mapped_type> bool update_range_value(Map &map, const Range &range, MapValue &&value, value_precedence precedence) { … } // combines directly adjacent ranges with equal RangeMap::mapped_type . template <typename RangeMap> void consolidate(RangeMap &map) { … } } // namespace sparse_container // Returns the intersection of the ranges [x, x + x_size) and [y, y + y_size) static inline sparse_container::range<int64_t> GetRangeIntersection(int64_t x, uint64_t x_size, int64_t y, uint64_t y_size) { … }
Codebase Browser
chromium