From 36f45dce44ddf8074df70fe1c217e08735189d57 Mon Sep 17 00:00:00 2001 From: JosJuice Date: Wed, 18 Feb 2026 20:02:54 +0100 Subject: Move RangeSet from Externals to Common This is a very small libary, and as I understand it, it was more or less developed for Dolphin. This moves the two relevant files from Externals to Common, changes the namespace to Common, reformats the code, and adds Dolphin copyright notices. The change in copyright notice and license was approved by AdmiralCurtiss. --- CMakeLists.txt | 2 - Externals/licenses.md | 2 - Externals/rangeset/CMakeLists.txt | 4 - Externals/rangeset/LICENSE | 17 - Externals/rangeset/include/rangeset/rangeset.h | 394 -------------- Externals/rangeset/include/rangeset/rangesizeset.h | 553 -------------------- Source/Core/Common/CMakeLists.txt | 2 + Source/Core/Common/RangeSet.h | 409 +++++++++++++++ Source/Core/Common/RangeSizeSet.h | 572 +++++++++++++++++++++ Source/Core/Core/CMakeLists.txt | 1 - .../PowerPC/CachedInterpreter/CachedInterpreter.h | 5 +- Source/Core/Core/PowerPC/Jit64/Jit.h | 7 +- Source/Core/DolphinLib.props | 2 + Source/VSProps/Base.Dolphin.props | 1 - 14 files changed, 990 insertions(+), 981 deletions(-) delete mode 100644 Externals/rangeset/CMakeLists.txt delete mode 100644 Externals/rangeset/LICENSE delete mode 100644 Externals/rangeset/include/rangeset/rangeset.h delete mode 100644 Externals/rangeset/include/rangeset/rangesizeset.h create mode 100644 Source/Core/Common/RangeSet.h create mode 100644 Source/Core/Common/RangeSizeSet.h diff --git a/CMakeLists.txt b/CMakeLists.txt index 170b7e0632..0ffe18889b 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -761,8 +761,6 @@ include_directories(Externals/picojson) add_subdirectory(Externals/expr) -add_subdirectory(Externals/rangeset) - add_subdirectory(Externals/FatFs) if (USE_RETRO_ACHIEVEMENTS) diff --git a/Externals/licenses.md b/Externals/licenses.md index 7aed5313ac..9db9cecf1a 100644 --- a/Externals/licenses.md +++ b/Externals/licenses.md @@ -64,8 +64,6 @@ Dolphin includes or links code of the following third-party software projects: [LGPLv2.1+](http://cgit.freedesktop.org/pulseaudio/pulseaudio/tree/LICENSE) - [Qt5](http://qt-project.org/): [LGPLv3 and other licenses](http://doc.qt.io/qt-5/licensing.html) -- [rangeset](https://github.com/AdmiralCurtiss/rangeset) - [zlib license](https://github.com/AdmiralCurtiss/rangeset/blob/master/LICENSE) - [SDL](https://www.libsdl.org/): [zlib license](http://hg.libsdl.org/SDL/file/tip/COPYING.txt) - [SFML](http://www.sfml-dev.org/): diff --git a/Externals/rangeset/CMakeLists.txt b/Externals/rangeset/CMakeLists.txt deleted file mode 100644 index a3dca5a1ec..0000000000 --- a/Externals/rangeset/CMakeLists.txt +++ /dev/null @@ -1,4 +0,0 @@ -add_library(RangeSet::RangeSet INTERFACE IMPORTED GLOBAL) -set_target_properties(RangeSet::RangeSet PROPERTIES - INTERFACE_INCLUDE_DIRECTORIES ${CMAKE_CURRENT_LIST_DIR}/include -) diff --git a/Externals/rangeset/LICENSE b/Externals/rangeset/LICENSE deleted file mode 100644 index 1af3d5b5b5..0000000000 --- a/Externals/rangeset/LICENSE +++ /dev/null @@ -1,17 +0,0 @@ -Copyright (c) 2020 Admiral H. Curtiss - -This software is provided 'as-is', without any express or implied -warranty. In no event will the authors be held liable for any damages -arising from the use of this software. - -Permission is granted to anyone to use this software for any purpose, -including commercial applications, and to alter it and redistribute it -freely, subject to the following restrictions: - -1. The origin of this software must not be misrepresented; you must not - claim that you wrote the original software. If you use this software - in a product, an acknowledgment in the product documentation would be - appreciated but is not required. -2. Altered source versions must be plainly marked as such, and must not be - misrepresented as being the original software. -3. This notice may not be removed or altered from any source distribution. diff --git a/Externals/rangeset/include/rangeset/rangeset.h b/Externals/rangeset/include/rangeset/rangeset.h deleted file mode 100644 index 22c7e81550..0000000000 --- a/Externals/rangeset/include/rangeset/rangeset.h +++ /dev/null @@ -1,394 +0,0 @@ -#pragma once - -#include -#include -#include -#include - -namespace HyoutaUtilities { -template class RangeSet { -private: - using MapT = std::map; - -public: - struct const_iterator { - public: - const T& from() const { - return It->first; - } - - const T& to() const { - return It->second; - } - - const_iterator& operator++() { - ++It; - return *this; - } - - const_iterator operator++(int) { - const_iterator old = *this; - ++It; - return old; - } - - const_iterator& operator--() { - --It; - return *this; - } - - const_iterator operator--(int) { - const_iterator old = *this; - --It; - return old; - } - - bool operator==(const const_iterator& rhs) const { - return this->It == rhs.It; - } - - bool operator!=(const const_iterator& rhs) const { - return !operator==(rhs); - } - - private: - typename MapT::const_iterator It; - const_iterator(typename MapT::const_iterator it) : It(it) {} - friend class RangeSet; - }; - - void insert(T from, T to) { - if (from >= to) - return; - - // Start by finding the closest range. - // upper_bound() returns the closest range whose starting position - // is greater than 'from'. - auto bound = Map.upper_bound(from); - if (bound == Map.end()) { - // There is no range that starts greater than the given one. - // This means we have three options: - // - 1. No range exists yet, this is the first range. - if (Map.empty()) { - insert_range(from, to); - return; - } - - // - 2. The given range does not overlap the last range. - --bound; - if (from > get_to(bound)) { - insert_range(from, to); - return; - } - - // - 3. The given range does overlap the last range. - maybe_expand_to(bound, to); - return; - } - - if (bound == Map.begin()) { - // The given range starts before any of the existing ones. - // We must insert this as a new range even if we potentially overlap - // an existing one as we can't modify a key in a std::map. - auto inserted = insert_range(from, to); - merge_from_iterator_to_value(inserted, bound, to); - return; - } - - auto abound = bound--; - - // 'bound' now points at the first range in the map that - // could possibly be affected. - - // If 'bound' overlaps with given range, update bounds object. - if (get_to(bound) >= from) { - maybe_expand_to(bound, to); - auto inserted = bound; - ++bound; - merge_from_iterator_to_value(inserted, bound, to); - return; - } - - // 'bound' *doesn't* overlap with given range, check next range. - - // If this range overlaps with given range, - if (get_from(abound) <= to) { - // insert new range - auto inserted = insert_range(from, to >= get_to(abound) ? to : get_to(abound)); - // and delete overlaps - abound = erase_range(abound); - merge_from_iterator_to_value(inserted, abound, to); - return; - } - - // Otherwise, if we come here, then this new range overlaps nothing - // and must be inserted as a new range. - insert_range(from, to); - } - - void erase(T from, T to) { - if (from >= to) - return; - - // Like insert(), we use upper_bound to find the closest range. - auto bound = Map.upper_bound(from); - if (bound == Map.end()) { - // There is no range that starts greater than the given one. - if (Map.empty()) { - // nothing to do - return; - } - --bound; - // 'bound' now points at the last range. - if (from >= get_to(bound)) { - // Given range is larger than any range that exists, nothing to do. - return; - } - - if (to >= get_to(bound)) { - if (from == get_from(bound)) { - // Given range fully overlaps last range, erase it. - erase_range(bound); - return; - } else { - // Given range overlaps end of last range, reduce it. - reduce_to(bound, from); - return; - } - } - - if (from == get_from(bound)) { - // Given range overlaps begin of last range, reduce it. - reduce_from(bound, to); - return; - } else { - // Given range overlaps middle of last range, bisect it. - bisect_range(bound, from, to); - return; - } - } - - if (bound == Map.begin()) { - // If we found the first range that means 'from' is before any stored range. - // This means we can just erase from start until 'to' and be done with it. - erase_from_iterator_to_value(bound, to); - return; - } - - // check previous range - auto abound = bound--; - - if (from == get_from(bound)) { - // Similarly, if the previous range starts with the given one, just erase until 'to'. - erase_from_iterator_to_value(bound, to); - return; - } - - // If we come here, the given range may or may not overlap part of the current 'bound' - // (but never the full range), which means we may need to update the end position of it, - // or possibly even split it into two. - if (from < get_to(bound)) { - if (to < get_to(bound)) { - // need to split in two - bisect_range(bound, from, to); - return; - } else { - // just update end - reduce_to(bound, from); - } - } - - // and then just erase until 'to' - erase_from_iterator_to_value(abound, to); - return; - } - - const_iterator erase(const_iterator it) { - return const_iterator(erase_range(it.It)); - } - - void clear() { - Map.clear(); - } - - bool contains(T value) const { - auto it = Map.upper_bound(value); - if (it == Map.begin()) - return false; - --it; - return get_from(it) <= value && value < get_to(it); - } - - std::size_t size() const { - return Map.size(); - } - - bool empty() const { - return Map.empty(); - } - - void swap(RangeSet& other) { - Map.swap(other.Map); - } - - const_iterator begin() const { - return const_iterator(Map.begin()); - } - - const_iterator end() const { - return const_iterator(Map.end()); - } - - const_iterator cbegin() const { - return const_iterator(Map.cbegin()); - } - - const_iterator cend() const { - return const_iterator(Map.cend()); - } - - bool operator==(const RangeSet& other) const { - return this->Map == other.Map; - } - - bool operator!=(const RangeSet& other) const { - return !(*this == other); - } - - // Get free size and fragmentation ratio - std::pair get_stats() const { - std::size_t free_total = 0; - if (begin() == end()) - return {free_total, 1.0}; - std::size_t largest_size = 0; - for (auto iter = begin(); iter != end(); ++iter) { - const std::size_t size = calc_size(iter.from(), iter.to()); - if (size > largest_size) - largest_size = size; - free_total += size; - } - return {free_total, static_cast(free_total - largest_size) / free_total}; - } - -private: - static std::size_t calc_size(T from, T to) { - if constexpr (std::is_pointer_v) { - // For pointers we don't want pointer arithmetic here, else void* breaks. - return reinterpret_cast(to) - reinterpret_cast(from); - } else { - return static_cast(to - from); - } - } - - // Assumptions that can be made about the data: - // - Range are stored in the form [from, to[ - // That is, the starting value is inclusive, and the end value is exclusive. - // - 'from' is the map key, 'to' is the map value - // - 'from' is always smaller than 'to' - // - Stored ranges never touch. - // - Stored ranges never overlap. - MapT Map; - - T get_from(typename MapT::iterator it) const { - return it->first; - } - - T get_to(typename MapT::iterator it) const { - return it->second; - } - - T get_from(typename MapT::const_iterator it) const { - return it->first; - } - - T get_to(typename MapT::const_iterator it) const { - return it->second; - } - - typename MapT::iterator insert_range(T from, T to) { - return Map.emplace(from, to).first; - } - - typename MapT::iterator erase_range(typename MapT::iterator it) { - return Map.erase(it); - } - - typename MapT::const_iterator erase_range(typename MapT::const_iterator it) { - return Map.erase(it); - } - - void bisect_range(typename MapT::iterator it, T from, T to) { - assert(get_from(it) < from); - assert(get_from(it) < to); - assert(get_to(it) > from); - assert(get_to(it) > to); - assert(from < to); - T itto = get_to(it); - reduce_to(it, from); - insert_range(to, itto); - } - - typename MapT::iterator reduce_from(typename MapT::iterator it, T from) { - assert(get_from(it) < from); - T itto = get_to(it); - erase_range(it); - return insert_range(from, itto); - } - - void maybe_expand_to(typename MapT::iterator it, T to) { - if (to <= get_to(it)) - return; - - expand_to(it, to); - } - - void expand_to(typename MapT::iterator it, T to) { - assert(get_to(it) < to); - it->second = to; - } - - void reduce_to(typename MapT::iterator it, T to) { - assert(get_to(it) > to); - it->second = to; - } - - void merge_from_iterator_to_value(typename MapT::iterator inserted, typename MapT::iterator bound, T to) { - // Erase all ranges that overlap the inserted while updating the upper end. - while (bound != Map.end() && get_from(bound) <= to) { - maybe_expand_to(inserted, get_to(bound)); - bound = erase_range(bound); - } - } - - void erase_from_iterator_to_value(typename MapT::iterator bound, T to) { - // Assumption: Given bound starts at or after the 'from' value of the range to erase. - while (true) { - // Given range starts before stored range. - if (to <= get_from(bound)) { - // Range ends before this range too, nothing to do. - return; - } - - if (to < get_to(bound)) { - // Range ends in the middle of current range, reduce current. - reduce_from(bound, to); - return; - } - - if (to == get_to(bound)) { - // Range ends exactly with current range, erase current. - erase_range(bound); - return; - } - - // Range ends later than current range. - // First erase current, then loop to check the range(s) after this one too. - bound = erase_range(bound); - if (bound == Map.end()) { - // Unless that was the last range, in which case there's nothing else to do. - return; - } - } - } -}; -} // namespace HyoutaUtilities diff --git a/Externals/rangeset/include/rangeset/rangesizeset.h b/Externals/rangeset/include/rangeset/rangesizeset.h deleted file mode 100644 index 7128a90602..0000000000 --- a/Externals/rangeset/include/rangeset/rangesizeset.h +++ /dev/null @@ -1,553 +0,0 @@ -#pragma once - -#include -#include -#include -#include -#include - -namespace HyoutaUtilities { -// Like RangeSet, but additionally stores a map of the ranges sorted by their size, for quickly finding the largest or -// smallest range. -template class RangeSizeSet { -private: - // Key type used in the by-size multimap. Should be a type big enough to hold all possible distances between - // possible 'from' and 'to'. - // I'd actually love to just do - // using SizeT = typename std::conditional, - // std::size_t, typename std::make_unsigned::type>::type; - // but that's apparently not possible due to the std::make_unsigned::type not existing for pointer types - // so we'll work around this... - template struct GetSizeType { using S = typename std::make_unsigned::type; }; - template struct GetSizeType { using S = std::size_t; }; - -public: - using SizeT = typename GetSizeType>::S; - -private: - // Value type stored in the regular range map. - struct Value { - // End point of the range. - T To; - - // Pointer to the same range in the by-size multimap. - typename std::multimap::iterator, std::greater>::iterator SizeIt; - - Value(T to) : To(to) {} - - bool operator==(const Value& other) const { - return this->To == other.To; - } - - bool operator!=(const Value& other) const { - return !operator==(other); - } - }; - - using MapT = std::map; - using SizeMapT = std::multimap>; - -public: - struct by_size_const_iterator; - - struct const_iterator { - public: - const T& from() const { - return It->first; - } - - const T& to() const { - return It->second.To; - } - - const_iterator& operator++() { - ++It; - return *this; - } - - const_iterator operator++(int) { - const_iterator old = *this; - ++It; - return old; - } - - const_iterator& operator--() { - --It; - return *this; - } - - const_iterator operator--(int) { - const_iterator old = *this; - --It; - return old; - } - - bool operator==(const const_iterator& rhs) const { - return this->It == rhs.It; - } - - bool operator!=(const const_iterator& rhs) const { - return !operator==(rhs); - } - - by_size_const_iterator to_size_iterator() { - return by_size_const_iterator(It->second.SizeIt); - } - - private: - typename MapT::const_iterator It; - const_iterator(typename MapT::const_iterator it) : It(it) {} - friend class RangeSizeSet; - }; - - struct by_size_const_iterator { - public: - const T& from() const { - return It->second->first; - } - - const T& to() const { - return It->second->second.To; - } - - by_size_const_iterator& operator++() { - ++It; - return *this; - } - - by_size_const_iterator operator++(int) { - by_size_const_iterator old = *this; - ++It; - return old; - } - - by_size_const_iterator& operator--() { - --It; - return *this; - } - - by_size_const_iterator operator--(int) { - by_size_const_iterator old = *this; - --It; - return old; - } - - bool operator==(const by_size_const_iterator& rhs) const { - return this->It == rhs.It; - } - - bool operator!=(const by_size_const_iterator& rhs) const { - return !operator==(rhs); - } - - const_iterator to_range_iterator() { - return const_iterator(It->second); - } - - private: - typename SizeMapT::const_iterator It; - by_size_const_iterator(typename SizeMapT::const_iterator it) : It(it) {} - friend class RangeSizeSet; - }; - - // We store iterators internally, so disallow copying. - RangeSizeSet() = default; - RangeSizeSet(const RangeSizeSet&) = delete; - RangeSizeSet(RangeSizeSet&&) = default; - RangeSizeSet& operator=(const RangeSizeSet&) = delete; - RangeSizeSet& operator=(RangeSizeSet&&) = default; - - void insert(T from, T to) { - if (from >= to) - return; - - // Start by finding the closest range. - // upper_bound() returns the closest range whose starting position - // is greater than 'from'. - auto bound = Map.upper_bound(from); - if (bound == Map.end()) { - // There is no range that starts greater than the given one. - // This means we have three options: - // - 1. No range exists yet, this is the first range. - if (Map.empty()) { - insert_range(from, to); - return; - } - - // - 2. The given range does not overlap the last range. - --bound; - if (from > get_to(bound)) { - insert_range(from, to); - return; - } - - // - 3. The given range does overlap the last range. - maybe_expand_to(bound, to); - return; - } - - if (bound == Map.begin()) { - // The given range starts before any of the existing ones. - // We must insert this as a new range even if we potentially overlap - // an existing one as we can't modify a key in a std::map. - auto inserted = insert_range(from, to); - merge_from_iterator_to_value(inserted, bound, to); - return; - } - - auto abound = bound--; - - // 'bound' now points at the first range in the map that - // could possibly be affected. - - // If 'bound' overlaps with given range, update bounds object. - if (get_to(bound) >= from) { - maybe_expand_to(bound, to); - auto inserted = bound; - ++bound; - merge_from_iterator_to_value(inserted, bound, to); - return; - } - - // 'bound' *doesn't* overlap with given range, check next range. - - // If this range overlaps with given range, - if (get_from(abound) <= to) { - // insert new range - auto inserted = insert_range(from, to >= get_to(abound) ? to : get_to(abound)); - // and delete overlaps - abound = erase_range(abound); - merge_from_iterator_to_value(inserted, abound, to); - return; - } - - // Otherwise, if we come here, then this new range overlaps nothing - // and must be inserted as a new range. - insert_range(from, to); - } - - void erase(T from, T to) { - if (from >= to) - return; - - // Like insert(), we use upper_bound to find the closest range. - auto bound = Map.upper_bound(from); - if (bound == Map.end()) { - // There is no range that starts greater than the given one. - if (Map.empty()) { - // nothing to do - return; - } - --bound; - // 'bound' now points at the last range. - if (from >= get_to(bound)) { - // Given range is larger than any range that exists, nothing to do. - return; - } - - if (to >= get_to(bound)) { - if (from == get_from(bound)) { - // Given range fully overlaps last range, erase it. - erase_range(bound); - return; - } else { - // Given range overlaps end of last range, reduce it. - reduce_to(bound, from); - return; - } - } - - if (from == get_from(bound)) { - // Given range overlaps begin of last range, reduce it. - reduce_from(bound, to); - return; - } else { - // Given range overlaps middle of last range, bisect it. - bisect_range(bound, from, to); - return; - } - } - - if (bound == Map.begin()) { - // If we found the first range that means 'from' is before any stored range. - // This means we can just erase from start until 'to' and be done with it. - erase_from_iterator_to_value(bound, to); - return; - } - - // check previous range - auto abound = bound--; - - if (from == get_from(bound)) { - // Similarly, if the previous range starts with the given one, just erase until 'to'. - erase_from_iterator_to_value(bound, to); - return; - } - - // If we come here, the given range may or may not overlap part of the current 'bound' - // (but never the full range), which means we may need to update the end position of it, - // or possibly even split it into two. - if (from < get_to(bound)) { - if (to < get_to(bound)) { - // need to split in two - bisect_range(bound, from, to); - return; - } else { - // just update end - reduce_to(bound, from); - } - } - - // and then just erase until 'to' - erase_from_iterator_to_value(abound, to); - return; - } - - const_iterator erase(const_iterator it) { - return const_iterator(erase_range(it.It)); - } - - by_size_const_iterator erase(by_size_const_iterator it) { - return by_size_const_iterator(erase_range_by_size(it.It)); - } - - void clear() { - Map.clear(); - Sizes.clear(); - } - - bool contains(T value) const { - auto it = Map.upper_bound(value); - if (it == Map.begin()) - return false; - --it; - return get_from(it) <= value && value < get_to(it); - } - - std::size_t size() const { - return Map.size(); - } - - bool empty() const { - return Map.empty(); - } - - std::size_t by_size_count(const SizeT& key) const { - return Sizes.count(key); - } - - by_size_const_iterator by_size_find(const SizeT& key) const { - return Sizes.find(key); - } - - std::pair by_size_equal_range(const SizeT& key) const { - auto p = Sizes.equal_range(key); - return std::pair(by_size_const_iterator(p.first), - by_size_const_iterator(p.second)); - } - - by_size_const_iterator by_size_lower_bound(const SizeT& key) const { - return Sizes.lower_bound(key); - } - - by_size_const_iterator by_size_upper_bound(const SizeT& key) const { - return Sizes.upper_bound(key); - } - - void swap(RangeSizeSet& other) { - Map.swap(other.Map); - Sizes.swap(other.Sizes); - } - - const_iterator begin() const { - return const_iterator(Map.begin()); - } - - const_iterator end() const { - return const_iterator(Map.end()); - } - - const_iterator cbegin() const { - return const_iterator(Map.cbegin()); - } - - const_iterator cend() const { - return const_iterator(Map.cend()); - } - - by_size_const_iterator by_size_begin() const { - return by_size_const_iterator(Sizes.begin()); - } - - by_size_const_iterator by_size_end() const { - return by_size_const_iterator(Sizes.end()); - } - - by_size_const_iterator by_size_cbegin() const { - return by_size_const_iterator(Sizes.cbegin()); - } - - by_size_const_iterator by_size_cend() const { - return by_size_const_iterator(Sizes.cend()); - } - - bool operator==(const RangeSizeSet& other) const { - return this->Map == other.Map; - } - - bool operator!=(const RangeSizeSet& other) const { - return !(*this == other); - } - - // Get free size and fragmentation ratio - std::pair get_stats() const { - std::size_t free_total = 0; - if (begin() == end()) - return {free_total, 1.0}; - for (auto iter = begin(); iter != end(); ++iter) - free_total += calc_size(iter.from(), iter.to()); - return {free_total, static_cast(free_total - Sizes.begin()->first) / free_total}; - } - -private: - static SizeT calc_size(T from, T to) { - if constexpr (std::is_pointer_v) { - // For pointers we don't want pointer arithmetic here, else void* breaks. - static_assert(sizeof(T) <= sizeof(SizeT)); - return reinterpret_cast(to) - reinterpret_cast(from); - } else { - return static_cast(to - from); - } - } - - // Assumptions that can be made about the data: - // - Range are stored in the form [from, to[ - // That is, the starting value is inclusive, and the end value is exclusive. - // - 'from' is the map key, 'to' is the map value - // - 'from' is always smaller than 'to' - // - Stored ranges never touch. - // - Stored ranges never overlap. - MapT Map; - - // The by-size multimap. - // Key is the size of the range. - // Value is a pointer to the range in the regular range map. - // We use std::greater so that Sizes.begin() gives us the largest range. - SizeMapT Sizes; - - T get_from(typename MapT::iterator it) const { - return it->first; - } - - T get_to(typename MapT::iterator it) const { - return it->second.To; - } - - T get_from(typename MapT::const_iterator it) const { - return it->first; - } - - T get_to(typename MapT::const_iterator it) const { - return it->second.To; - } - - typename MapT::iterator insert_range(T from, T to) { - auto m = Map.emplace(from, to).first; - m->second.SizeIt = Sizes.emplace(calc_size(from, to), m); - return m; - } - - typename MapT::iterator erase_range(typename MapT::iterator it) { - Sizes.erase(it->second.SizeIt); - return Map.erase(it); - } - - typename MapT::const_iterator erase_range(typename MapT::const_iterator it) { - Sizes.erase(it->second.SizeIt); - return Map.erase(it); - } - - typename SizeMapT::const_iterator erase_range_by_size(typename SizeMapT::const_iterator it) { - Map.erase(it->second); - return Sizes.erase(it); - } - - void bisect_range(typename MapT::iterator it, T from, T to) { - assert(get_from(it) < from); - assert(get_from(it) < to); - assert(get_to(it) > from); - assert(get_to(it) > to); - assert(from < to); - T itto = get_to(it); - reduce_to(it, from); - insert_range(to, itto); - } - - typename MapT::iterator reduce_from(typename MapT::iterator it, T from) { - assert(get_from(it) < from); - T itto = get_to(it); - erase_range(it); - return insert_range(from, itto); - } - - void maybe_expand_to(typename MapT::iterator it, T to) { - if (to <= get_to(it)) - return; - - expand_to(it, to); - } - - void expand_to(typename MapT::iterator it, T to) { - assert(get_to(it) < to); - it->second.To = to; - Sizes.erase(it->second.SizeIt); - it->second.SizeIt = Sizes.emplace(calc_size(get_from(it), to), it); - } - - void reduce_to(typename MapT::iterator it, T to) { - assert(get_to(it) > to); - it->second.To = to; - Sizes.erase(it->second.SizeIt); - it->second.SizeIt = Sizes.emplace(calc_size(get_from(it), to), it); - } - - void merge_from_iterator_to_value(typename MapT::iterator inserted, typename MapT::iterator bound, T to) { - // Erase all ranges that overlap the inserted while updating the upper end. - while (bound != Map.end() && get_from(bound) <= to) { - maybe_expand_to(inserted, get_to(bound)); - bound = erase_range(bound); - } - } - - void erase_from_iterator_to_value(typename MapT::iterator bound, T to) { - // Assumption: Given bound starts at or after the 'from' value of the range to erase. - while (true) { - // Given range starts before stored range. - if (to <= get_from(bound)) { - // Range ends before this range too, nothing to do. - return; - } - - if (to < get_to(bound)) { - // Range ends in the middle of current range, reduce current. - reduce_from(bound, to); - return; - } - - if (to == get_to(bound)) { - // Range ends exactly with current range, erase current. - erase_range(bound); - return; - } - - // Range ends later than current range. - // First erase current, then loop to check the range(s) after this one too. - bound = erase_range(bound); - if (bound == Map.end()) { - // Unless that was the last range, in which case there's nothing else to do. - return; - } - } - } -}; -} // namespace HyoutaUtilities diff --git a/Source/Core/Common/CMakeLists.txt b/Source/Core/Common/CMakeLists.txt index fac5900f76..e134acabd3 100644 --- a/Source/Core/Common/CMakeLists.txt +++ b/Source/Core/Common/CMakeLists.txt @@ -127,6 +127,8 @@ add_library(common QoSSession.h Random.cpp Random.h + RangeSet.h + RangeSizeSet.h ScopeGuard.h SDCardUtil.cpp SDCardUtil.h diff --git a/Source/Core/Common/RangeSet.h b/Source/Core/Common/RangeSet.h new file mode 100644 index 0000000000..68212f93fe --- /dev/null +++ b/Source/Core/Common/RangeSet.h @@ -0,0 +1,409 @@ +// Copyright 2020 Dolphin Emulator Project +// SPDX-License-Identifier: GPL-2.0-or-later + +#pragma once + +#include +#include +#include +#include + +namespace Common +{ +template +class RangeSet +{ +private: + using MapT = std::map; + +public: + struct const_iterator + { + public: + const T& from() const { return It->first; } + + const T& to() const { return It->second; } + + const_iterator& operator++() + { + ++It; + return *this; + } + + const_iterator operator++(int) + { + const_iterator old = *this; + ++It; + return old; + } + + const_iterator& operator--() + { + --It; + return *this; + } + + const_iterator operator--(int) + { + const_iterator old = *this; + --It; + return old; + } + + bool operator==(const const_iterator& rhs) const { return this->It == rhs.It; } + + bool operator!=(const const_iterator& rhs) const { return !operator==(rhs); } + + private: + typename MapT::const_iterator It; + const_iterator(typename MapT::const_iterator it) : It(it) {} + friend class RangeSet; + }; + + void insert(T from, T to) + { + if (from >= to) + return; + + // Start by finding the closest range. + // upper_bound() returns the closest range whose starting position + // is greater than 'from'. + auto bound = Map.upper_bound(from); + if (bound == Map.end()) + { + // There is no range that starts greater than the given one. + // This means we have three options: + // - 1. No range exists yet, this is the first range. + if (Map.empty()) + { + insert_range(from, to); + return; + } + + // - 2. The given range does not overlap the last range. + --bound; + if (from > get_to(bound)) + { + insert_range(from, to); + return; + } + + // - 3. The given range does overlap the last range. + maybe_expand_to(bound, to); + return; + } + + if (bound == Map.begin()) + { + // The given range starts before any of the existing ones. + // We must insert this as a new range even if we potentially overlap + // an existing one as we can't modify a key in a std::map. + auto inserted = insert_range(from, to); + merge_from_iterator_to_value(inserted, bound, to); + return; + } + + auto abound = bound--; + + // 'bound' now points at the first range in the map that + // could possibly be affected. + + // If 'bound' overlaps with given range, update bounds object. + if (get_to(bound) >= from) + { + maybe_expand_to(bound, to); + auto inserted = bound; + ++bound; + merge_from_iterator_to_value(inserted, bound, to); + return; + } + + // 'bound' *doesn't* overlap with given range, check next range. + + // If this range overlaps with given range, + if (get_from(abound) <= to) + { + // insert new range + auto inserted = insert_range(from, to >= get_to(abound) ? to : get_to(abound)); + // and delete overlaps + abound = erase_range(abound); + merge_from_iterator_to_value(inserted, abound, to); + return; + } + + // Otherwise, if we come here, then this new range overlaps nothing + // and must be inserted as a new range. + insert_range(from, to); + } + + void erase(T from, T to) + { + if (from >= to) + return; + + // Like insert(), we use upper_bound to find the closest range. + auto bound = Map.upper_bound(from); + if (bound == Map.end()) + { + // There is no range that starts greater than the given one. + if (Map.empty()) + { + // nothing to do + return; + } + --bound; + // 'bound' now points at the last range. + if (from >= get_to(bound)) + { + // Given range is larger than any range that exists, nothing to do. + return; + } + + if (to >= get_to(bound)) + { + if (from == get_from(bound)) + { + // Given range fully overlaps last range, erase it. + erase_range(bound); + return; + } + else + { + // Given range overlaps end of last range, reduce it. + reduce_to(bound, from); + return; + } + } + + if (from == get_from(bound)) + { + // Given range overlaps begin of last range, reduce it. + reduce_from(bound, to); + return; + } + else + { + // Given range overlaps middle of last range, bisect it. + bisect_range(bound, from, to); + return; + } + } + + if (bound == Map.begin()) + { + // If we found the first range that means 'from' is before any stored range. + // This means we can just erase from start until 'to' and be done with it. + erase_from_iterator_to_value(bound, to); + return; + } + + // check previous range + auto abound = bound--; + + if (from == get_from(bound)) + { + // Similarly, if the previous range starts with the given one, just erase until 'to'. + erase_from_iterator_to_value(bound, to); + return; + } + + // If we come here, the given range may or may not overlap part of the current 'bound' + // (but never the full range), which means we may need to update the end position of it, + // or possibly even split it into two. + if (from < get_to(bound)) + { + if (to < get_to(bound)) + { + // need to split in two + bisect_range(bound, from, to); + return; + } + else + { + // just update end + reduce_to(bound, from); + } + } + + // and then just erase until 'to' + erase_from_iterator_to_value(abound, to); + return; + } + + const_iterator erase(const_iterator it) { return const_iterator(erase_range(it.It)); } + + void clear() { Map.clear(); } + + bool contains(T value) const + { + auto it = Map.upper_bound(value); + if (it == Map.begin()) + return false; + --it; + return get_from(it) <= value && value < get_to(it); + } + + std::size_t size() const { return Map.size(); } + + bool empty() const { return Map.empty(); } + + void swap(RangeSet& other) { Map.swap(other.Map); } + + const_iterator begin() const { return const_iterator(Map.begin()); } + + const_iterator end() const { return const_iterator(Map.end()); } + + const_iterator cbegin() const { return const_iterator(Map.cbegin()); } + + const_iterator cend() const { return const_iterator(Map.cend()); } + + bool operator==(const RangeSet& other) const { return this->Map == other.Map; } + + bool operator!=(const RangeSet& other) const { return !(*this == other); } + + // Get free size and fragmentation ratio + std::pair get_stats() const + { + std::size_t free_total = 0; + if (begin() == end()) + return {free_total, 1.0}; + std::size_t largest_size = 0; + for (auto iter = begin(); iter != end(); ++iter) + { + const std::size_t size = calc_size(iter.from(), iter.to()); + if (size > largest_size) + largest_size = size; + free_total += size; + } + return {free_total, static_cast(free_total - largest_size) / free_total}; + } + +private: + static std::size_t calc_size(T from, T to) + { + if constexpr (std::is_pointer_v) + { + // For pointers we don't want pointer arithmetic here, else void* breaks. + return reinterpret_cast(to) - reinterpret_cast(from); + } + else + { + return static_cast(to - from); + } + } + + // Assumptions that can be made about the data: + // - Range are stored in the form [from, to[ + // That is, the starting value is inclusive, and the end value is exclusive. + // - 'from' is the map key, 'to' is the map value + // - 'from' is always smaller than 'to' + // - Stored ranges never touch. + // - Stored ranges never overlap. + MapT Map; + + T get_from(typename MapT::iterator it) const { return it->first; } + + T get_to(typename MapT::iterator it) const { return it->second; } + + T get_from(typename MapT::const_iterator it) const { return it->first; } + + T get_to(typename MapT::const_iterator it) const { return it->second; } + + typename MapT::iterator insert_range(T from, T to) { return Map.emplace(from, to).first; } + + typename MapT::iterator erase_range(typename MapT::iterator it) { return Map.erase(it); } + + typename MapT::const_iterator erase_range(typename MapT::const_iterator it) + { + return Map.erase(it); + } + + void bisect_range(typename MapT::iterator it, T from, T to) + { + assert(get_from(it) < from); + assert(get_from(it) < to); + assert(get_to(it) > from); + assert(get_to(it) > to); + assert(from < to); + T itto = get_to(it); + reduce_to(it, from); + insert_range(to, itto); + } + + typename MapT::iterator reduce_from(typename MapT::iterator it, T from) + { + assert(get_from(it) < from); + T itto = get_to(it); + erase_range(it); + return insert_range(from, itto); + } + + void maybe_expand_to(typename MapT::iterator it, T to) + { + if (to <= get_to(it)) + return; + + expand_to(it, to); + } + + void expand_to(typename MapT::iterator it, T to) + { + assert(get_to(it) < to); + it->second = to; + } + + void reduce_to(typename MapT::iterator it, T to) + { + assert(get_to(it) > to); + it->second = to; + } + + void merge_from_iterator_to_value(typename MapT::iterator inserted, typename MapT::iterator bound, + T to) + { + // Erase all ranges that overlap the inserted while updating the upper end. + while (bound != Map.end() && get_from(bound) <= to) + { + maybe_expand_to(inserted, get_to(bound)); + bound = erase_range(bound); + } + } + + void erase_from_iterator_to_value(typename MapT::iterator bound, T to) + { + // Assumption: Given bound starts at or after the 'from' value of the range to erase. + while (true) + { + // Given range starts before stored range. + if (to <= get_from(bound)) + { + // Range ends before this range too, nothing to do. + return; + } + + if (to < get_to(bound)) + { + // Range ends in the middle of current range, reduce current. + reduce_from(bound, to); + return; + } + + if (to == get_to(bound)) + { + // Range ends exactly with current range, erase current. + erase_range(bound); + return; + } + + // Range ends later than current range. + // First erase current, then loop to check the range(s) after this one too. + bound = erase_range(bound); + if (bound == Map.end()) + { + // Unless that was the last range, in which case there's nothing else to do. + return; + } + } + } +}; +} // namespace Common diff --git a/Source/Core/Common/RangeSizeSet.h b/Source/Core/Common/RangeSizeSet.h new file mode 100644 index 0000000000..8fd7ca8965 --- /dev/null +++ b/Source/Core/Common/RangeSizeSet.h @@ -0,0 +1,572 @@ +// Copyright 2020 Dolphin Emulator Project +// SPDX-License-Identifier: GPL-2.0-or-later + +#pragma once + +#include +#include +#include +#include +#include + +namespace Common +{ +// Like RangeSet, but additionally stores a map of the ranges sorted by their size, for quickly +// finding the largest or smallest range. +template +class RangeSizeSet +{ +private: + // Key type used in the by-size multimap. Should be a type big enough to hold all possible + // distances between possible 'from' and 'to'. + // I'd actually love to just do + // using SizeT = typename std::conditional, + // std::size_t, typename std::make_unsigned::type>::type; + // but that's apparently not possible due to the std::make_unsigned::type not existing for + // pointer types so we'll work around this... + template + struct GetSizeType + { + using S = typename std::make_unsigned::type; + }; + template + struct GetSizeType + { + using S = std::size_t; + }; + +public: + using SizeT = typename GetSizeType>::S; + +private: + // Value type stored in the regular range map. + struct Value + { + // End point of the range. + T To; + + // Pointer to the same range in the by-size multimap. + typename std::multimap::iterator, + std::greater>::iterator SizeIt; + + Value(T to) : To(to) {} + + bool operator==(const Value& other) const { return this->To == other.To; } + + bool operator!=(const Value& other) const { return !operator==(other); } + }; + + using MapT = std::map; + using SizeMapT = std::multimap>; + +public: + struct by_size_const_iterator; + + struct const_iterator + { + public: + const T& from() const { return It->first; } + + const T& to() const { return It->second.To; } + + const_iterator& operator++() + { + ++It; + return *this; + } + + const_iterator operator++(int) + { + const_iterator old = *this; + ++It; + return old; + } + + const_iterator& operator--() + { + --It; + return *this; + } + + const_iterator operator--(int) + { + const_iterator old = *this; + --It; + return old; + } + + bool operator==(const const_iterator& rhs) const { return this->It == rhs.It; } + + bool operator!=(const const_iterator& rhs) const { return !operator==(rhs); } + + by_size_const_iterator to_size_iterator() { return by_size_const_iterator(It->second.SizeIt); } + + private: + typename MapT::const_iterator It; + const_iterator(typename MapT::const_iterator it) : It(it) {} + friend class RangeSizeSet; + }; + + struct by_size_const_iterator + { + public: + const T& from() const { return It->second->first; } + + const T& to() const { return It->second->second.To; } + + by_size_const_iterator& operator++() + { + ++It; + return *this; + } + + by_size_const_iterator operator++(int) + { + by_size_const_iterator old = *this; + ++It; + return old; + } + + by_size_const_iterator& operator--() + { + --It; + return *this; + } + + by_size_const_iterator operator--(int) + { + by_size_const_iterator old = *this; + --It; + return old; + } + + bool operator==(const by_size_const_iterator& rhs) const { return this->It == rhs.It; } + + bool operator!=(const by_size_const_iterator& rhs) const { return !operator==(rhs); } + + const_iterator to_range_iterator() { return const_iterator(It->second); } + + private: + typename SizeMapT::const_iterator It; + by_size_const_iterator(typename SizeMapT::const_iterator it) : It(it) {} + friend class RangeSizeSet; + }; + + // We store iterators internally, so disallow copying. + RangeSizeSet() = default; + RangeSizeSet(const RangeSizeSet&) = delete; + RangeSizeSet(RangeSizeSet&&) = default; + RangeSizeSet& operator=(const RangeSizeSet&) = delete; + RangeSizeSet& operator=(RangeSizeSet&&) = default; + + void insert(T from, T to) + { + if (from >= to) + return; + + // Start by finding the closest range. + // upper_bound() returns the closest range whose starting position + // is greater than 'from'. + auto bound = Map.upper_bound(from); + if (bound == Map.end()) + { + // There is no range that starts greater than the given one. + // This means we have three options: + // - 1. No range exists yet, this is the first range. + if (Map.empty()) + { + insert_range(from, to); + return; + } + + // - 2. The given range does not overlap the last range. + --bound; + if (from > get_to(bound)) + { + insert_range(from, to); + return; + } + + // - 3. The given range does overlap the last range. + maybe_expand_to(bound, to); + return; + } + + if (bound == Map.begin()) + { + // The given range starts before any of the existing ones. + // We must insert this as a new range even if we potentially overlap + // an existing one as we can't modify a key in a std::map. + auto inserted = insert_range(from, to); + merge_from_iterator_to_value(inserted, bound, to); + return; + } + + auto abound = bound--; + + // 'bound' now points at the first range in the map that + // could possibly be affected. + + // If 'bound' overlaps with given range, update bounds object. + if (get_to(bound) >= from) + { + maybe_expand_to(bound, to); + auto inserted = bound; + ++bound; + merge_from_iterator_to_value(inserted, bound, to); + return; + } + + // 'bound' *doesn't* overlap with given range, check next range. + + // If this range overlaps with given range, + if (get_from(abound) <= to) + { + // insert new range + auto inserted = insert_range(from, to >= get_to(abound) ? to : get_to(abound)); + // and delete overlaps + abound = erase_range(abound); + merge_from_iterator_to_value(inserted, abound, to); + return; + } + + // Otherwise, if we come here, then this new range overlaps nothing + // and must be inserted as a new range. + insert_range(from, to); + } + + void erase(T from, T to) + { + if (from >= to) + return; + + // Like insert(), we use upper_bound to find the closest range. + auto bound = Map.upper_bound(from); + if (bound == Map.end()) + { + // There is no range that starts greater than the given one. + if (Map.empty()) + { + // nothing to do + return; + } + --bound; + // 'bound' now points at the last range. + if (from >= get_to(bound)) + { + // Given range is larger than any range that exists, nothing to do. + return; + } + + if (to >= get_to(bound)) + { + if (from == get_from(bound)) + { + // Given range fully overlaps last range, erase it. + erase_range(bound); + return; + } + else + { + // Given range overlaps end of last range, reduce it. + reduce_to(bound, from); + return; + } + } + + if (from == get_from(bound)) + { + // Given range overlaps begin of last range, reduce it. + reduce_from(bound, to); + return; + } + else + { + // Given range overlaps middle of last range, bisect it. + bisect_range(bound, from, to); + return; + } + } + + if (bound == Map.begin()) + { + // If we found the first range that means 'from' is before any stored range. + // This means we can just erase from start until 'to' and be done with it. + erase_from_iterator_to_value(bound, to); + return; + } + + // check previous range + auto abound = bound--; + + if (from == get_from(bound)) + { + // Similarly, if the previous range starts with the given one, just erase until 'to'. + erase_from_iterator_to_value(bound, to); + return; + } + + // If we come here, the given range may or may not overlap part of the current 'bound' + // (but never the full range), which means we may need to update the end position of it, + // or possibly even split it into two. + if (from < get_to(bound)) + { + if (to < get_to(bound)) + { + // need to split in two + bisect_range(bound, from, to); + return; + } + else + { + // just update end + reduce_to(bound, from); + } + } + + // and then just erase until 'to' + erase_from_iterator_to_value(abound, to); + return; + } + + const_iterator erase(const_iterator it) { return const_iterator(erase_range(it.It)); } + + by_size_const_iterator erase(by_size_const_iterator it) + { + return by_size_const_iterator(erase_range_by_size(it.It)); + } + + void clear() + { + Map.clear(); + Sizes.clear(); + } + + bool contains(T value) const + { + auto it = Map.upper_bound(value); + if (it == Map.begin()) + return false; + --it; + return get_from(it) <= value && value < get_to(it); + } + + std::size_t size() const { return Map.size(); } + + bool empty() const { return Map.empty(); } + + std::size_t by_size_count(const SizeT& key) const { return Sizes.count(key); } + + by_size_const_iterator by_size_find(const SizeT& key) const { return Sizes.find(key); } + + std::pair + by_size_equal_range(const SizeT& key) const + { + auto p = Sizes.equal_range(key); + return std::pair( + by_size_const_iterator(p.first), by_size_const_iterator(p.second)); + } + + by_size_const_iterator by_size_lower_bound(const SizeT& key) const + { + return Sizes.lower_bound(key); + } + + by_size_const_iterator by_size_upper_bound(const SizeT& key) const + { + return Sizes.upper_bound(key); + } + + void swap(RangeSizeSet& other) + { + Map.swap(other.Map); + Sizes.swap(other.Sizes); + } + + const_iterator begin() const { return const_iterator(Map.begin()); } + + const_iterator end() const { return const_iterator(Map.end()); } + + const_iterator cbegin() const { return const_iterator(Map.cbegin()); } + + const_iterator cend() const { return const_iterator(Map.cend()); } + + by_size_const_iterator by_size_begin() const { return by_size_const_iterator(Sizes.begin()); } + + by_size_const_iterator by_size_end() const { return by_size_const_iterator(Sizes.end()); } + + by_size_const_iterator by_size_cbegin() const { return by_size_const_iterator(Sizes.cbegin()); } + + by_size_const_iterator by_size_cend() const { return by_size_const_iterator(Sizes.cend()); } + + bool operator==(const RangeSizeSet& other) const { return this->Map == other.Map; } + + bool operator!=(const RangeSizeSet& other) const { return !(*this == other); } + + // Get free size and fragmentation ratio + std::pair get_stats() const + { + std::size_t free_total = 0; + if (begin() == end()) + return {free_total, 1.0}; + for (auto iter = begin(); iter != end(); ++iter) + free_total += calc_size(iter.from(), iter.to()); + return {free_total, static_cast(free_total - Sizes.begin()->first) / free_total}; + } + +private: + static SizeT calc_size(T from, T to) + { + if constexpr (std::is_pointer_v) + { + // For pointers we don't want pointer arithmetic here, else void* breaks. + static_assert(sizeof(T) <= sizeof(SizeT)); + return reinterpret_cast(to) - reinterpret_cast(from); + } + else + { + return static_cast(to - from); + } + } + + // Assumptions that can be made about the data: + // - Range are stored in the form [from, to[ + // That is, the starting value is inclusive, and the end value is exclusive. + // - 'from' is the map key, 'to' is the map value + // - 'from' is always smaller than 'to' + // - Stored ranges never touch. + // - Stored ranges never overlap. + MapT Map; + + // The by-size multimap. + // Key is the size of the range. + // Value is a pointer to the range in the regular range map. + // We use std::greater so that Sizes.begin() gives us the largest range. + SizeMapT Sizes; + + T get_from(typename MapT::iterator it) const { return it->first; } + + T get_to(typename MapT::iterator it) const { return it->second.To; } + + T get_from(typename MapT::const_iterator it) const { return it->first; } + + T get_to(typename MapT::const_iterator it) const { return it->second.To; } + + typename MapT::iterator insert_range(T from, T to) + { + auto m = Map.emplace(from, to).first; + m->second.SizeIt = Sizes.emplace(calc_size(from, to), m); + return m; + } + + typename MapT::iterator erase_range(typename MapT::iterator it) + { + Sizes.erase(it->second.SizeIt); + return Map.erase(it); + } + + typename MapT::const_iterator erase_range(typename MapT::const_iterator it) + { + Sizes.erase(it->second.SizeIt); + return Map.erase(it); + } + + typename SizeMapT::const_iterator erase_range_by_size(typename SizeMapT::const_iterator it) + { + Map.erase(it->second); + return Sizes.erase(it); + } + + void bisect_range(typename MapT::iterator it, T from, T to) + { + assert(get_from(it) < from); + assert(get_from(it) < to); + assert(get_to(it) > from); + assert(get_to(it) > to); + assert(from < to); + T itto = get_to(it); + reduce_to(it, from); + insert_range(to, itto); + } + + typename MapT::iterator reduce_from(typename MapT::iterator it, T from) + { + assert(get_from(it) < from); + T itto = get_to(it); + erase_range(it); + return insert_range(from, itto); + } + + void maybe_expand_to(typename MapT::iterator it, T to) + { + if (to <= get_to(it)) + return; + + expand_to(it, to); + } + + void expand_to(typename MapT::iterator it, T to) + { + assert(get_to(it) < to); + it->second.To = to; + Sizes.erase(it->second.SizeIt); + it->second.SizeIt = Sizes.emplace(calc_size(get_from(it), to), it); + } + + void reduce_to(typename MapT::iterator it, T to) + { + assert(get_to(it) > to); + it->second.To = to; + Sizes.erase(it->second.SizeIt); + it->second.SizeIt = Sizes.emplace(calc_size(get_from(it), to), it); + } + + void merge_from_iterator_to_value(typename MapT::iterator inserted, typename MapT::iterator bound, + T to) + { + // Erase all ranges that overlap the inserted while updating the upper end. + while (bound != Map.end() && get_from(bound) <= to) + { + maybe_expand_to(inserted, get_to(bound)); + bound = erase_range(bound); + } + } + + void erase_from_iterator_to_value(typename MapT::iterator bound, T to) + { + // Assumption: Given bound starts at or after the 'from' value of the range to erase. + while (true) + { + // Given range starts before stored range. + if (to <= get_from(bound)) + { + // Range ends before this range too, nothing to do. + return; + } + + if (to < get_to(bound)) + { + // Range ends in the middle of current range, reduce current. + reduce_from(bound, to); + return; + } + + if (to == get_to(bound)) + { + // Range ends exactly with current range, erase current. + erase_range(bound); + return; + } + + // Range ends later than current range. + // First erase current, then loop to check the range(s) after this one too. + bound = erase_range(bound); + if (bound == Map.end()) + { + // Unless that was the last range, in which case there's nothing else to do. + return; + } + } + } +}; +} // namespace Common diff --git a/Source/Core/Core/CMakeLists.txt b/Source/Core/Core/CMakeLists.txt index e2ae3e9919..b81558e274 100644 --- a/Source/Core/Core/CMakeLists.txt +++ b/Source/Core/Core/CMakeLists.txt @@ -660,7 +660,6 @@ PUBLIC inputcommon MbedTLS::mbedtls pugixml - RangeSet::RangeSet sfml-network videonull videoogl diff --git a/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h b/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h index 12e9c17c50..dd940e89a2 100644 --- a/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h +++ b/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h @@ -5,9 +5,8 @@ #include -#include - #include "Common/CommonTypes.h" +#include "Common/RangeSizeSet.h" #include "Core/PowerPC/CachedInterpreter/CachedInterpreterBlockCache.h" #include "Core/PowerPC/CachedInterpreter/CachedInterpreterEmitter.h" #include "Core/PowerPC/JitCommon/JitBase.h" @@ -112,7 +111,7 @@ private: static s32 CheckIdle(PowerPC::PowerPCState& ppc_state, const CheckIdleOperands& operands); static s32 CheckIdle(std::ostream& stream, const CheckIdleOperands& operands); - HyoutaUtilities::RangeSizeSet m_free_ranges; + Common::RangeSizeSet m_free_ranges; CachedInterpreterBlockCache m_block_cache; }; diff --git a/Source/Core/Core/PowerPC/Jit64/Jit.h b/Source/Core/Core/PowerPC/Jit64/Jit.h index 2d8ef2be55..da1be2db04 100644 --- a/Source/Core/Core/PowerPC/Jit64/Jit.h +++ b/Source/Core/Core/PowerPC/Jit64/Jit.h @@ -19,9 +19,8 @@ #include -#include - #include "Common/CommonTypes.h" +#include "Common/RangeSizeSet.h" #include "Common/x64Emitter.h" #include "Core/PowerPC/Jit64/JitAsm.h" #include "Core/PowerPC/Jit64/RegCache/FPURegCache.h" @@ -295,8 +294,8 @@ private: Jit64AsmRoutineManager asm_routines{*this}; - HyoutaUtilities::RangeSizeSet m_free_ranges_near; - HyoutaUtilities::RangeSizeSet m_free_ranges_far; + Common::RangeSizeSet m_free_ranges_near; + Common::RangeSizeSet m_free_ranges_far; const bool m_im_here_debug = false; const bool m_im_here_log = false; diff --git a/Source/Core/DolphinLib.props b/Source/Core/DolphinLib.props index 34e4b83f13..c6c9c485dd 100644 --- a/Source/Core/DolphinLib.props +++ b/Source/Core/DolphinLib.props @@ -154,6 +154,8 @@ + + diff --git a/Source/VSProps/Base.Dolphin.props b/Source/VSProps/Base.Dolphin.props index 472ff9a89e..93d58df583 100644 --- a/Source/VSProps/Base.Dolphin.props +++ b/Source/VSProps/Base.Dolphin.props @@ -14,7 +14,6 @@ $(ExternalsDir)FFmpeg-bin\$(Platform)\include;%(AdditionalIncludeDirectories) $(ExternalsDir)OpenAL\include;%(AdditionalIncludeDirectories) $(ExternalsDir)expr\include;%(AdditionalIncludeDirectories) - $(ExternalsDir)rangeset\include;%(AdditionalIncludeDirectories) $(ExternalsDir)Vulkan-Headers\include;%(AdditionalIncludeDirectories) $(ExternalsDir)VulkanMemoryAllocator\include;%(AdditionalIncludeDirectories) $(ExternalsDir)watcher\watcher\include;%(AdditionalIncludeDirectories) -- cgit v1.2.3 From c1a26808ce5a09bcc08e029b71d4b1fb47bc4d57 Mon Sep 17 00:00:00 2001 From: JosJuice Date: Sat, 14 Feb 2026 14:42:42 +0100 Subject: Jit: Use RangeSet for physical_addresses This makes JitBaseBlockCache::ErasePhysicalRange around 50% faster and PPCAnalyzer::Analyze around 40% faster. Rogue Squadron 2's notoriously laggy action of switching to and from cockpit view is made something like 20-30% faster by this, though this is a very rough measurement. --- Source/Core/Common/RangeSet.h | 14 ++++++++++ Source/Core/Common/RangeSizeSet.h | 14 ++++++++++ Source/Core/Core/PowerPC/JitArm64/Jit.h | 11 ++++---- Source/Core/Core/PowerPC/JitCommon/JitCache.cpp | 31 +++++++++++++++------- Source/Core/Core/PowerPC/JitCommon/JitCache.h | 7 ++--- Source/Core/Core/PowerPC/PPCAnalyst.cpp | 3 ++- Source/Core/Core/PowerPC/PPCAnalyst.h | 4 +-- .../Core/DolphinQt/Debugger/JitBlockTableModel.cpp | 7 +++-- 8 files changed, 67 insertions(+), 24 deletions(-) diff --git a/Source/Core/Common/RangeSet.h b/Source/Core/Common/RangeSet.h index 68212f93fe..05229c8704 100644 --- a/Source/Core/Common/RangeSet.h +++ b/Source/Core/Common/RangeSet.h @@ -24,6 +24,8 @@ public: const T& to() const { return It->second; } + std::pair operator*() { return {from(), to()}; } + const_iterator& operator++() { ++It; @@ -243,6 +245,18 @@ public: return get_from(it) <= value && value < get_to(it); } + bool overlaps(T from, T to) const + { + if (from >= to) + return false; + + auto it = Map.lower_bound(to); + if (it == Map.begin()) + return false; + --it; + return get_from(it) < to && from < get_to(it); + } + std::size_t size() const { return Map.size(); } bool empty() const { return Map.empty(); } diff --git a/Source/Core/Common/RangeSizeSet.h b/Source/Core/Common/RangeSizeSet.h index 8fd7ca8965..72ec740523 100644 --- a/Source/Core/Common/RangeSizeSet.h +++ b/Source/Core/Common/RangeSizeSet.h @@ -69,6 +69,8 @@ public: const T& to() const { return It->second.To; } + std::pair operator*() { return {from(), to()}; } + const_iterator& operator++() { ++It; @@ -351,6 +353,18 @@ public: return get_from(it) <= value && value < get_to(it); } + bool overlaps(T from, T to) const + { + if (from >= to) + return false; + + auto it = Map.lower_bound(to); + if (it == Map.begin()) + return false; + --it; + return get_from(it) < to && from < get_to(it); + } + std::size_t size() const { return Map.size(); } bool empty() const { return Map.empty(); } diff --git a/Source/Core/Core/PowerPC/JitArm64/Jit.h b/Source/Core/Core/PowerPC/JitArm64/Jit.h index 5b42dff3dd..9c23112e1c 100644 --- a/Source/Core/Core/PowerPC/JitArm64/Jit.h +++ b/Source/Core/Core/PowerPC/JitArm64/Jit.h @@ -7,9 +7,8 @@ #include #include -#include - #include "Common/Arm64Emitter.h" +#include "Common/RangeSizeSet.h" #include "Core/PowerPC/JitArm64/JitArm64Cache.h" #include "Core/PowerPC/JitArm64/JitArm64_RegCache.h" @@ -431,10 +430,10 @@ protected: u8* m_near_code_end = nullptr; bool m_near_code_write_failed = false; - HyoutaUtilities::RangeSizeSet m_free_ranges_near_0; - HyoutaUtilities::RangeSizeSet m_free_ranges_near_1; - HyoutaUtilities::RangeSizeSet m_free_ranges_far_0; - HyoutaUtilities::RangeSizeSet m_free_ranges_far_1; + Common::RangeSizeSet m_free_ranges_near_0; + Common::RangeSizeSet m_free_ranges_near_1; + Common::RangeSizeSet m_free_ranges_far_0; + Common::RangeSizeSet m_free_ranges_far_1; std::unique_ptr m_disassembler; }; diff --git a/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp b/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp index c9050be730..a7226b2ae9 100644 --- a/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp +++ b/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp @@ -31,8 +31,7 @@ using namespace Gen; bool JitBlock::OverlapsPhysicalRange(u32 address, u32 length) const { - return physical_addresses.lower_bound(address) != - physical_addresses.lower_bound(address + length); + return physical_addresses.overlaps(address, address + length); } void JitBlock::ProfileData::BeginProfiling(ProfileData* data) @@ -171,10 +170,13 @@ void JitBaseBlockCache::FinalizeBlock(JitBlock& block, bool block_link, original_buffer_transform_view.end()); } - for (u32 addr : block.physical_addresses) + for (auto [range_start, range_end] : block.physical_addresses) { - valid_block.Set(addr / 32); - block_range_map[addr & BLOCK_RANGE_MAP_MASK].insert(&block); + for (u32 i = range_start & ~31; i < range_end; i += 32) + valid_block.Set(i / 32); + + for (u32 i = range_start & BLOCK_RANGE_MAP_MASK; i < range_end; i += BLOCK_RANGE_SIZE) + block_range_map[i].insert(&block); } if (block_link) @@ -362,9 +364,15 @@ void JitBaseBlockCache::ErasePhysicalRange(u32 address, u32 length) { // If the block overlaps, also remove all other occupied slots in the other macro blocks. // This will leak empty macro blocks, but they may be reused or cleared later on. - for (u32 addr : block->physical_addresses) - if ((addr & BLOCK_RANGE_MAP_MASK) != start->first) - block_range_map[addr & BLOCK_RANGE_MAP_MASK].erase(block); + for (auto [range_start, range_end] : block->physical_addresses) + { + DEBUG_ASSERT(range_start != range_end); + for (u32 i = range_start & BLOCK_RANGE_MAP_MASK; i < range_end; i += BLOCK_RANGE_SIZE) + { + if (i != start->first) + block_range_map[i].erase(block); + } + } // And remove the block. DestroyBlock(*block); @@ -404,8 +412,11 @@ void JitBaseBlockCache::EraseSingleBlock(const JitBlock& block) JitBlock& mutable_block = block_map_iter->second; - for (const u32 addr : mutable_block.physical_addresses) - block_range_map[addr & BLOCK_RANGE_MAP_MASK].erase(&mutable_block); + for (auto [range_start, range_end] : mutable_block.physical_addresses) + { + for (u32 i = range_start & BLOCK_RANGE_MAP_MASK; i < range_end; i += BLOCK_RANGE_SIZE) + block_range_map[i].erase(&mutable_block); + } DestroyBlock(mutable_block); block_map.erase(block_map_iter); // The original JitBlock reference is now dangling. diff --git a/Source/Core/Core/PowerPC/JitCommon/JitCache.h b/Source/Core/Core/PowerPC/JitCommon/JitCache.h index 9d227d62b0..703fb4069e 100644 --- a/Source/Core/Core/PowerPC/JitCommon/JitCache.h +++ b/Source/Core/Core/PowerPC/JitCommon/JitCache.h @@ -10,13 +10,13 @@ #include #include #include -#include #include #include #include #include #include "Common/CommonTypes.h" +#include "Common/RangeSet.h" #include "Core/HW/Memmap.h" #include "Core/PowerPC/Gekko.h" #include "Core/PowerPC/PPCAnalyst.h" @@ -101,7 +101,7 @@ struct JitBlock : public JitBlockData std::vector linkData; // This set stores all physical addresses of all occupied instructions. - std::set physical_addresses; + Common::RangeSet physical_addresses; // This is only available when debugging is enabled. It is a trimmed-down copy of the // PPCAnalyst::CodeBuffer used to recompile this block, including repeat instructions. @@ -218,7 +218,8 @@ private: // Range of overlapping code indexed by a masked physical address. // This is used for invalidation of memory regions. The range is grouped // in macro blocks of each 0x100 bytes. - static constexpr u32 BLOCK_RANGE_MAP_MASK = ~(0x100 - 1); + static constexpr u32 BLOCK_RANGE_SIZE = 0x100; + static constexpr u32 BLOCK_RANGE_MAP_MASK = ~(BLOCK_RANGE_SIZE - 1); std::map> block_range_map; // This bitsets shows which cachelines overlap with any blocks. diff --git a/Source/Core/Core/PowerPC/PPCAnalyst.cpp b/Source/Core/Core/PowerPC/PPCAnalyst.cpp index 8c35ad4923..40b974b0d8 100644 --- a/Source/Core/Core/PowerPC/PPCAnalyst.cpp +++ b/Source/Core/Core/PowerPC/PPCAnalyst.cpp @@ -849,7 +849,8 @@ u32 PPCAnalyzer::Analyze(u32 address, CodeBlock* block, CodeBuffer* buffer, code[i].inst = inst; code[i].skip = false; block->m_stats->numCycles += opinfo->num_cycles; - block->m_physical_addresses.insert(result.physical_address); + block->m_physical_addresses.insert(result.physical_address, + result.physical_address + sizeof(UGeckoInstruction)); SetInstructionStats(block, &code[i], opinfo); diff --git a/Source/Core/Core/PowerPC/PPCAnalyst.h b/Source/Core/Core/PowerPC/PPCAnalyst.h index ed0242498b..879bd06111 100644 --- a/Source/Core/Core/PowerPC/PPCAnalyst.h +++ b/Source/Core/Core/PowerPC/PPCAnalyst.h @@ -5,11 +5,11 @@ #include #include -#include #include #include "Common/BitSet.h" #include "Common/CommonTypes.h" +#include "Common/RangeSet.h" #include "Core/PowerPC/PPCTables.h" class PPCSymbolDB; @@ -129,7 +129,7 @@ struct CodeBlock BitSet32 m_gpr_inputs; // Which memory locations are occupied by this block. - std::set m_physical_addresses; + Common::RangeSet m_physical_addresses; }; class PPCAnalyzer diff --git a/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp b/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp index 25701d26f4..61f5851380 100644 --- a/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp +++ b/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp @@ -236,7 +236,8 @@ QVariant JitBlockTableModel::DisplayRoleData(const QModelIndex& index) const case Column::CodeBufferSize: return QString::number(jit_block.originalSize * sizeof(UGeckoInstruction)); case Column::RepeatInstructions: - return QString::number(jit_block.originalSize - jit_block.physical_addresses.size()); + return QString::number(jit_block.originalSize - jit_block.physical_addresses.get_stats().first / + sizeof(UGeckoInstruction)); case Column::HostNearCodeSize: return QString::number(jit_block.near_end - jit_block.near_begin); case Column::HostFarCodeSize: @@ -329,7 +330,9 @@ QVariant JitBlockTableModel::SortRoleData(const QModelIndex& index) const case Column::CodeBufferSize: return static_cast(jit_block.originalSize); case Column::RepeatInstructions: - return static_cast(jit_block.originalSize - jit_block.physical_addresses.size()); + return static_cast(jit_block.originalSize - + jit_block.physical_addresses.get_stats().first / + sizeof(UGeckoInstruction)); case Column::HostNearCodeSize: return static_cast(jit_block.near_end - jit_block.near_begin); case Column::HostFarCodeSize: -- cgit v1.2.3