From 4841dc0b745389fb03edbf900f25511bee4b3d88 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Sat, 3 Feb 2024 22:51:04 +0100 Subject: VideoCore: Move Slot Vector to Common --- src/common/CMakeLists.txt | 1 + src/common/slot_vector.h | 227 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 228 insertions(+) create mode 100644 src/common/slot_vector.h (limited to 'src/common') diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index 85926fc8f..bf3f3b781 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -121,6 +121,7 @@ add_library(common STATIC settings_input.cpp settings_input.h settings_setting.h + slot_vector.h socket_types.h spin_lock.cpp spin_lock.h diff --git a/src/common/slot_vector.h b/src/common/slot_vector.h new file mode 100644 index 000000000..34ff7de94 --- /dev/null +++ b/src/common/slot_vector.h @@ -0,0 +1,227 @@ +// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project +// SPDX-License-Identifier: GPL-2.0-or-later + +#pragma once + +#include +#include +#include +#include +#include +#include + +#include "common/assert.h" +#include "common/common_types.h" +#include "common/polyfill_ranges.h" + +namespace Common { + +struct SlotId { + static constexpr u32 INVALID_INDEX = std::numeric_limits::max(); + + constexpr auto operator<=>(const SlotId&) const noexcept = default; + + constexpr explicit operator bool() const noexcept { + return index != INVALID_INDEX; + } + + u32 index = INVALID_INDEX; +}; + +template + requires std::is_nothrow_move_assignable_v && std::is_nothrow_move_constructible_v +class SlotVector { +public: + class Iterator { + friend SlotVector; + + public: + constexpr Iterator() = default; + + Iterator& operator++() noexcept { + const u64* const bitset = slot_vector->stored_bitset.data(); + const u32 size = static_cast(slot_vector->stored_bitset.size()) * 64; + if (id.index < size) { + do { + ++id.index; + } while (id.index < size && !IsValid(bitset)); + if (id.index == size) { + id.index = SlotId::INVALID_INDEX; + } + } + return *this; + } + + Iterator operator++(int) noexcept { + const Iterator copy{*this}; + ++*this; + return copy; + } + + bool operator==(const Iterator& other) const noexcept { + return id.index == other.id.index; + } + + bool operator!=(const Iterator& other) const noexcept { + return id.index != other.id.index; + } + + std::pair operator*() const noexcept { + return {id, std::addressof((*slot_vector)[id])}; + } + + T* operator->() const noexcept { + return std::addressof((*slot_vector)[id]); + } + + private: + Iterator(SlotVector* slot_vector_, SlotId id_) noexcept + : slot_vector{slot_vector_}, id{id_} {} + + bool IsValid(const u64* bitset) const noexcept { + return ((bitset[id.index / 64] >> (id.index % 64)) & 1) != 0; + } + + SlotVector* slot_vector; + SlotId id; + }; + + ~SlotVector() noexcept { + size_t index = 0; + for (u64 bits : stored_bitset) { + for (size_t bit = 0; bits; ++bit, bits >>= 1) { + if ((bits & 1) != 0) { + values[index + bit].object.~T(); + } + } + index += 64; + } + delete[] values; + } + + [[nodiscard]] T& operator[](SlotId id) noexcept { + ValidateIndex(id); + return values[id.index].object; + } + + [[nodiscard]] const T& operator[](SlotId id) const noexcept { + ValidateIndex(id); + return values[id.index].object; + } + + template + [[nodiscard]] SlotId insert(Args&&... args) noexcept { + const u32 index = FreeValueIndex(); + new (&values[index].object) T(std::forward(args)...); + SetStorageBit(index); + + return SlotId{index}; + } + + void erase(SlotId id) noexcept { + values[id.index].object.~T(); + free_list.push_back(id.index); + ResetStorageBit(id.index); + } + + [[nodiscard]] Iterator begin() noexcept { + const auto it = std::ranges::find_if(stored_bitset, [](u64 value) { return value != 0; }); + if (it == stored_bitset.end()) { + return end(); + } + const u32 word_index = static_cast(std::distance(it, stored_bitset.begin())); + const SlotId first_id{word_index * 64 + static_cast(std::countr_zero(*it))}; + return Iterator(this, first_id); + } + + [[nodiscard]] Iterator end() noexcept { + return Iterator(this, SlotId{SlotId::INVALID_INDEX}); + } + + [[nodiscard]] size_t size() const noexcept { + return values_capacity - free_list.size(); + } + +private: + struct NonTrivialDummy { + NonTrivialDummy() noexcept {} + }; + + union Entry { + Entry() noexcept : dummy{} {} + ~Entry() noexcept {} + + NonTrivialDummy dummy; + T object; + }; + + void SetStorageBit(u32 index) noexcept { + stored_bitset[index / 64] |= u64(1) << (index % 64); + } + + void ResetStorageBit(u32 index) noexcept { + stored_bitset[index / 64] &= ~(u64(1) << (index % 64)); + } + + bool ReadStorageBit(u32 index) noexcept { + return ((stored_bitset[index / 64] >> (index % 64)) & 1) != 0; + } + + void ValidateIndex(SlotId id) const noexcept { + DEBUG_ASSERT(id); + DEBUG_ASSERT(id.index / 64 < stored_bitset.size()); + DEBUG_ASSERT(((stored_bitset[id.index / 64] >> (id.index % 64)) & 1) != 0); + } + + [[nodiscard]] u32 FreeValueIndex() noexcept { + if (free_list.empty()) { + Reserve(values_capacity ? (values_capacity << 1) : 1); + } + const u32 free_index = free_list.back(); + free_list.pop_back(); + return free_index; + } + + void Reserve(size_t new_capacity) noexcept { + Entry* const new_values = new Entry[new_capacity]; + size_t index = 0; + for (u64 bits : stored_bitset) { + for (size_t bit = 0; bits; ++bit, bits >>= 1) { + const size_t i = index + bit; + if ((bits & 1) == 0) { + continue; + } + T& old_value = values[i].object; + new (&new_values[i].object) T(std::move(old_value)); + old_value.~T(); + } + index += 64; + } + + stored_bitset.resize((new_capacity + 63) / 64); + + const size_t old_free_size = free_list.size(); + free_list.resize(old_free_size + (new_capacity - values_capacity)); + std::iota(free_list.begin() + old_free_size, free_list.end(), + static_cast(values_capacity)); + + delete[] values; + values = new_values; + values_capacity = new_capacity; + } + + Entry* values = nullptr; + size_t values_capacity = 0; + + std::vector stored_bitset; + std::vector free_list; +}; + +} // namespace Common + +template <> +struct std::hash { + size_t operator()(const Common::SlotId& id) const noexcept { + return std::hash{}(id.index); + } +}; -- cgit v1.2.3 From 01ba6cf610641f1937092b469843b14ebc2a5962 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Sun, 4 Feb 2024 14:44:17 +0100 Subject: Common: Introduce Range Sets --- src/common/CMakeLists.txt | 2 + src/common/range_sets.h | 73 ++++++++++++ src/common/range_sets.inc | 279 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 354 insertions(+) create mode 100644 src/common/range_sets.h create mode 100644 src/common/range_sets.inc (limited to 'src/common') diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index bf3f3b781..c19af2ab8 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -107,6 +107,8 @@ add_library(common STATIC quaternion.h range_map.h range_mutex.h + range_sets.h + range_sets.inc reader_writer_queue.h ring_buffer.h ${CMAKE_CURRENT_BINARY_DIR}/scm_rev.cpp diff --git a/src/common/range_sets.h b/src/common/range_sets.h new file mode 100644 index 000000000..f4ee00fec --- /dev/null +++ b/src/common/range_sets.h @@ -0,0 +1,73 @@ +// SPDX-FileCopyrightText: 2024 yuzu Emulator Project +// SPDX-License-Identifier: GPL-2.0-or-later + +#pragma once + +#include + +#include "common/common_types.h" + +namespace Common { + +template +class RangeSet { +public: + RangeSet(); + ~RangeSet(); + + RangeSet(RangeSet const&) = delete; + RangeSet& operator=(RangeSet const&) = delete; + + RangeSet(RangeSet&& other); + RangeSet& operator=(RangeSet&& other); + + void Add(AddressType base_address, size_t size); + void Subtract(AddressType base_address, size_t size); + void Clear(); + bool Empty() const; + + template + void ForEach(Func&& func) const; + + template + void ForEachInRange(AddressType device_addr, size_t size, Func&& func) const; + +private: + struct RangeSetImpl; + std::unique_ptr m_impl; +}; + +template +class SplitRangeSet { +public: + SplitRangeSet(); + ~SplitRangeSet(); + + SplitRangeSet(SplitRangeSet const&) = delete; + SplitRangeSet& operator=(SplitRangeSet const&) = delete; + + SplitRangeSet(SplitRangeSet&& other); + SplitRangeSet& operator=(SplitRangeSet&& other); + + void Add(AddressType base_address, size_t size); + void Subtract(AddressType base_address, size_t size); + + template + void Subtract(AddressType base_address, size_t size, Func&& on_delete); + + void DeleteAll(AddressType base_address, size_t size); + void Clear(); + bool Empty() const; + + template + void ForEach(Func&& func) const; + + template + void ForEachInRange(AddressType device_addr, size_t size, Func&& func) const; + +private: + struct SplitRangeSetImpl; + std::unique_ptr m_impl; +}; + +} // namespace Common \ No newline at end of file diff --git a/src/common/range_sets.inc b/src/common/range_sets.inc new file mode 100644 index 000000000..fa55a68fb --- /dev/null +++ b/src/common/range_sets.inc @@ -0,0 +1,279 @@ +// SPDX-FileCopyrightText: 2024 yuzu Emulator Project +// SPDX-License-Identifier: GPL-2.0-or-later + +#pragma once + +#include +#include + +#define BOOST_NO_MT +#include +#undef BOOST_NO_MT +#include +#include +#include +#include +#include +#include +#include +#include + +#include "common/range_sets.h" + +namespace boost { +template +class fast_pool_allocator; +} + +namespace Common { + +template +struct RangeSet::RangeSetImpl { + using IntervalSet = boost::icl::interval_set< + AddressType, std::less, ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), + boost::fast_pool_allocator>; + using IntervalType = typename IntervalSet::interval_type; + + RangeSetImpl() = default; + ~RangeSetImpl() = default; + + void Add(AddressType base_address, size_t size) { + AddressType end_address = base_address + static_cast(size); + IntervalType interval{base_address, end_address}; + m_ranges_set.add(interval); + } + + void Subtract(AddressType base_address, size_t size) { + AddressType end_address = base_address + static_cast(size); + IntervalType interval{base_address, end_address}; + m_ranges_set.subtract(interval); + } + + IntervalSet m_ranges_set; +}; + +template +struct SplitRangeSet::SplitRangeSetImpl { + + using IntervalSet = + boost::icl::split_interval_map; + using IntervalType = typename IntervalSet::interval_type; + + SplitRangeSetImpl() = default; + ~SplitRangeSetImpl() = default; + + void Add(AddressType base_address, size_t size) { + AddressType end_address = base_address + static_cast(size); + IntervalType interval{base_address, end_address}; + m_split_ranges_set += std::make_pair(interval, 1); + } + + template + void Subtract(AddressType base_address, size_t size, s32 amount, + [[maybe_unused]] Func&& on_delete) { + AddressType end_address = base_address + static_cast(size); + IntervalType interval{base_address, end_address}; + bool any_removals = false; + m_split_ranges_set += std::make_pair(interval, -amount); + do { + any_removals = false; + auto it = m_split_ranges_set.lower_bound(interval); + if (it == m_split_ranges_set.end()) { + return; + } + auto end_it = m_split_ranges_set.upper_bound(interval); + for (; it != end_it; it++) { + if (it->second <= 0) { + if constexpr (has_on_delete) { + if (it->second == 0) { + on_delete(it->first.lower(), it->first.upper()); + } + } + any_removals = true; + m_split_ranges_set.erase(it); + break; + } + } + } while (any_removals); + } + + IntervalSet m_split_ranges_set; +}; + +template +RangeSet::RangeSet() { + m_impl = std::make_unique::RangeSetImpl>(); +} + +template +RangeSet::~RangeSet() = default; + +template +RangeSet::RangeSet(RangeSet&& other) { + m_impl = std::make_unique::RangeSetImpl>(); + m_impl->m_ranges_set = std::move(other.m_impl->m_ranges_set); +} + +template +RangeSet& RangeSet::operator=(RangeSet&& other) { + m_impl->m_ranges_set = std::move(other.m_impl->m_ranges_set); +} + +template +void RangeSet::Add(AddressType base_address, size_t size) { + m_impl->Add(base_address, size); +} + +template +void RangeSet::Subtract(AddressType base_address, size_t size) { + m_impl->Subtract(base_address, size); +} + +template +void RangeSet::Clear() { + m_impl->m_ranges_set.clear(); +} + +template +bool RangeSet::Empty() const { + return m_impl->m_ranges_set.empty(); +} + +template +template +void RangeSet::ForEach(Func&& func) const { + if (m_impl->m_ranges_set.empty()) { + return; + } + auto it = m_impl->m_ranges_set.begin(); + auto end_it = m_impl->m_ranges_set.end(); + for (; it != end_it; it++) { + const AddressType inter_addr_end = it->upper(); + const AddressType inter_addr = it->lower(); + func(inter_addr, inter_addr_end); + } +} + +template +template +void RangeSet::ForEachInRange(AddressType base_addr, size_t size, Func&& func) const { + auto& range_set = m_impl->m_ranges_set; + const AddressType start_address = base_addr; + const AddressType end_address = start_address + size; + const RangeSetImpl::IntervalType search_interval{start_address, end_address}; + auto it = range_set.lower_bound(search_interval); + if (it == range_set.end()) { + return; + } + auto end_it = range_set.upper_bound(search_interval); + for (; it != end_it; it++) { + AddressType inter_addr_end = it->upper(); + AddressType inter_addr = it->lower(); + if (inter_addr_end > end_address) { + inter_addr_end = end_address; + } + if (inter_addr < start_address) { + inter_addr = start_address; + } + func(inter_addr, inter_addr_end); + } +} + +template +SplitRangeSet::SplitRangeSet() { + m_impl = std::make_unique::SplitRangeSetImpl>(); +} + +template +SplitRangeSet::~SplitRangeSet() = default; + +template +SplitRangeSet::SplitRangeSet(SplitRangeSet&& other) { + m_impl = std::make_unique::SplitRangeSetImpl>(); + m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set); +} + +template +SplitRangeSet& SplitRangeSet::operator=(SplitRangeSet&& other) { + m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set); +} + +template +void SplitRangeSet::Add(AddressType base_address, size_t size) { + m_impl->Add(base_address, size); +} + +template +void SplitRangeSet::Subtract(AddressType base_address, size_t size) { + m_impl->Subtract(base_address, size, 1, [](AddressType, AddressType) {}); +} + +template +template +void SplitRangeSet::Subtract(AddressType base_address, size_t size, Func&& on_delete) { + m_impl->Subtract(base_address, size, 1, on_delete); +} + +template +void SplitRangeSet::DeleteAll(AddressType base_address, size_t size) { + m_impl->Subtract(base_address, size, std::numeric_limits::max(), + [](AddressType, AddressType) {}); +} + +template +void SplitRangeSet::Clear() { + m_impl->m_split_ranges_set.clear(); +} + +template +bool SplitRangeSet::Empty() const { + return m_impl->m_split_ranges_set.empty(); +} + +template +template +void SplitRangeSet::ForEach(Func&& func) const { + if (m_impl->m_split_ranges_set.empty()) { + return; + } + auto it = m_impl->m_split_ranges_set.begin(); + auto end_it = m_impl->m_split_ranges_set.end(); + for (; it != end_it; it++) { + const AddressType inter_addr_end = it->first.upper(); + const AddressType inter_addr = it->first.lower(); + func(inter_addr, inter_addr_end, it->second); + } +} + +template +template +void SplitRangeSet::ForEachInRange(AddressType base_address, size_t size, + Func&& func) const { + auto& range_set = m_impl->m_split_ranges_set; + const AddressType start_address = base_address; + const AddressType end_address = start_address + size; + const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address}; + auto it = range_set.lower_bound(search_interval); + if (it == range_set.end()) { + return; + } + auto end_it = range_set.upper_bound(search_interval); + for (; it != end_it; it++) { + auto& inter = it->first; + AddressType inter_addr_end = inter.upper(); + AddressType inter_addr = inter.lower(); + if (inter_addr_end > end_address) { + inter_addr_end = end_address; + } + if (inter_addr < start_address) { + inter_addr = start_address; + } + func(inter_addr, inter_addr_end, it->second); + } +} + +} // namespace Common \ No newline at end of file -- cgit v1.2.3 From 0d5a3abeaefd3a1682c48a59c5a9170cfb0a39d0 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Sun, 4 Feb 2024 19:16:07 +0100 Subject: Buffer Cache: Refactor to use Range sets instead --- src/common/range_sets.inc | 184 ++++++++++++++++++++++++++-------------------- 1 file changed, 103 insertions(+), 81 deletions(-) (limited to 'src/common') diff --git a/src/common/range_sets.inc b/src/common/range_sets.inc index fa55a68fb..705ebd4a1 100644 --- a/src/common/range_sets.inc +++ b/src/common/range_sets.inc @@ -6,9 +6,6 @@ #include #include -#define BOOST_NO_MT -#include -#undef BOOST_NO_MT #include #include #include @@ -20,18 +17,16 @@ #include "common/range_sets.h" -namespace boost { -template -class fast_pool_allocator; -} - namespace Common { template struct RangeSet::RangeSetImpl { + template + using MyAllocator = boost::fast_pool_allocator; using IntervalSet = boost::icl::interval_set< AddressType, std::less, ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), - boost::fast_pool_allocator>; + MyAllocator>; using IntervalType = typename IntervalSet::interval_type; RangeSetImpl() = default; @@ -49,18 +44,58 @@ struct RangeSet::RangeSetImpl { m_ranges_set.subtract(interval); } + template + void ForEach(Func&& func) const { + if (m_ranges_set.empty()) { + return; + } + auto it = m_ranges_set.begin(); + auto end_it = m_ranges_set.end(); + for (; it != end_it; it++) { + const AddressType inter_addr_end = it->upper(); + const AddressType inter_addr = it->lower(); + func(inter_addr, inter_addr_end); + } + } + + template + void ForEachInRange(AddressType base_addr, size_t size, Func&& func) const { + if (m_ranges_set.empty()) { + return; + } + const AddressType start_address = base_addr; + const AddressType end_address = start_address + size; + const RangeSetImpl::IntervalType search_interval{start_address, end_address}; + auto it = m_ranges_set.lower_bound(search_interval); + if (it == m_ranges_set.end()) { + return; + } + auto end_it = m_ranges_set.upper_bound(search_interval); + for (; it != end_it; it++) { + AddressType inter_addr_end = it->upper(); + AddressType inter_addr = it->lower(); + if (inter_addr_end > end_address) { + inter_addr_end = end_address; + } + if (inter_addr < start_address) { + inter_addr = start_address; + } + func(inter_addr, inter_addr_end); + } + } + IntervalSet m_ranges_set; }; template struct SplitRangeSet::SplitRangeSetImpl { - - using IntervalSet = - boost::icl::split_interval_map; + template + using MyAllocator = boost::fast_pool_allocator; + using IntervalSet = boost::icl::split_interval_map< + AddressType, s32, boost::icl::partial_enricher, std::less, boost::icl::inplace_plus, + boost::icl::inter_section, + ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), MyAllocator>; using IntervalType = typename IntervalSet::interval_type; SplitRangeSetImpl() = default; @@ -75,6 +110,9 @@ struct SplitRangeSet::SplitRangeSetImpl { template void Subtract(AddressType base_address, size_t size, s32 amount, [[maybe_unused]] Func&& on_delete) { + if (m_split_ranges_set.empty()) { + return; + } AddressType end_address = base_address + static_cast(size); IntervalType interval{base_address, end_address}; bool any_removals = false; @@ -101,6 +139,47 @@ struct SplitRangeSet::SplitRangeSetImpl { } while (any_removals); } + template + void ForEach(Func&& func) const { + if (m_split_ranges_set.empty()) { + return; + } + auto it = m_split_ranges_set.begin(); + auto end_it = m_split_ranges_set.end(); + for (; it != end_it; it++) { + const AddressType inter_addr_end = it->first.upper(); + const AddressType inter_addr = it->first.lower(); + func(inter_addr, inter_addr_end, it->second); + } + } + + template + void ForEachInRange(AddressType base_address, size_t size, Func&& func) const { + if (m_split_ranges_set.empty()) { + return; + } + const AddressType start_address = base_address; + const AddressType end_address = start_address + size; + const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address}; + auto it = m_split_ranges_set.lower_bound(search_interval); + if (it == m_split_ranges_set.end()) { + return; + } + auto end_it = m_split_ranges_set.upper_bound(search_interval); + for (; it != end_it; it++) { + auto& inter = it->first; + AddressType inter_addr_end = inter.upper(); + AddressType inter_addr = inter.lower(); + if (inter_addr_end > end_address) { + inter_addr_end = end_address; + } + if (inter_addr < start_address) { + inter_addr = start_address; + } + func(inter_addr, inter_addr_end, it->second); + } + } + IntervalSet m_split_ranges_set; }; @@ -146,41 +225,13 @@ bool RangeSet::Empty() const { template template void RangeSet::ForEach(Func&& func) const { - if (m_impl->m_ranges_set.empty()) { - return; - } - auto it = m_impl->m_ranges_set.begin(); - auto end_it = m_impl->m_ranges_set.end(); - for (; it != end_it; it++) { - const AddressType inter_addr_end = it->upper(); - const AddressType inter_addr = it->lower(); - func(inter_addr, inter_addr_end); - } + m_impl->ForEach(std::move(func)); } template template -void RangeSet::ForEachInRange(AddressType base_addr, size_t size, Func&& func) const { - auto& range_set = m_impl->m_ranges_set; - const AddressType start_address = base_addr; - const AddressType end_address = start_address + size; - const RangeSetImpl::IntervalType search_interval{start_address, end_address}; - auto it = range_set.lower_bound(search_interval); - if (it == range_set.end()) { - return; - } - auto end_it = range_set.upper_bound(search_interval); - for (; it != end_it; it++) { - AddressType inter_addr_end = it->upper(); - AddressType inter_addr = it->lower(); - if (inter_addr_end > end_address) { - inter_addr_end = end_address; - } - if (inter_addr < start_address) { - inter_addr = start_address; - } - func(inter_addr, inter_addr_end); - } +void RangeSet::ForEachInRange(AddressType base_address, size_t size, Func&& func) const { + m_impl->ForEachInRange(base_address, size, std::move(func)); } template @@ -209,18 +260,18 @@ void SplitRangeSet::Add(AddressType base_address, size_t size) { template void SplitRangeSet::Subtract(AddressType base_address, size_t size) { - m_impl->Subtract(base_address, size, 1, [](AddressType, AddressType) {}); + m_impl->template Subtract(base_address, size, 1, [](AddressType, AddressType) {}); } template template void SplitRangeSet::Subtract(AddressType base_address, size_t size, Func&& on_delete) { - m_impl->Subtract(base_address, size, 1, on_delete); + m_impl->template Subtract(base_address, size, 1, std::move(on_delete)); } template void SplitRangeSet::DeleteAll(AddressType base_address, size_t size) { - m_impl->Subtract(base_address, size, std::numeric_limits::max(), + m_impl->template Subtract(base_address, size, std::numeric_limits::max(), [](AddressType, AddressType) {}); } @@ -237,43 +288,14 @@ bool SplitRangeSet::Empty() const { template template void SplitRangeSet::ForEach(Func&& func) const { - if (m_impl->m_split_ranges_set.empty()) { - return; - } - auto it = m_impl->m_split_ranges_set.begin(); - auto end_it = m_impl->m_split_ranges_set.end(); - for (; it != end_it; it++) { - const AddressType inter_addr_end = it->first.upper(); - const AddressType inter_addr = it->first.lower(); - func(inter_addr, inter_addr_end, it->second); - } + m_impl->ForEach(func); } template template void SplitRangeSet::ForEachInRange(AddressType base_address, size_t size, Func&& func) const { - auto& range_set = m_impl->m_split_ranges_set; - const AddressType start_address = base_address; - const AddressType end_address = start_address + size; - const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address}; - auto it = range_set.lower_bound(search_interval); - if (it == range_set.end()) { - return; - } - auto end_it = range_set.upper_bound(search_interval); - for (; it != end_it; it++) { - auto& inter = it->first; - AddressType inter_addr_end = inter.upper(); - AddressType inter_addr = inter.lower(); - if (inter_addr_end > end_address) { - inter_addr_end = end_address; - } - if (inter_addr < start_address) { - inter_addr = start_address; - } - func(inter_addr, inter_addr_end, it->second); - } + m_impl->ForEachInRange(base_address, size, std::move(func)); } } // namespace Common \ No newline at end of file -- cgit v1.2.3 From fa47ac1c9f8b117d556c7c18ac9dcb062af5cefc Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Mon, 5 Feb 2024 12:46:49 +0100 Subject: Common: Rename SplitRangeSet to OverlapRangeSet --- src/common/range_sets.h | 20 +++++++-------- src/common/range_sets.inc | 63 +++++++++++++++++++++++++---------------------- 2 files changed, 43 insertions(+), 40 deletions(-) (limited to 'src/common') diff --git a/src/common/range_sets.h b/src/common/range_sets.h index f4ee00fec..f8fcee483 100644 --- a/src/common/range_sets.h +++ b/src/common/range_sets.h @@ -38,16 +38,16 @@ private: }; template -class SplitRangeSet { +class OverlapRangeSet { public: - SplitRangeSet(); - ~SplitRangeSet(); + OverlapRangeSet(); + ~OverlapRangeSet(); - SplitRangeSet(SplitRangeSet const&) = delete; - SplitRangeSet& operator=(SplitRangeSet const&) = delete; + OverlapRangeSet(OverlapRangeSet const&) = delete; + OverlapRangeSet& operator=(OverlapRangeSet const&) = delete; - SplitRangeSet(SplitRangeSet&& other); - SplitRangeSet& operator=(SplitRangeSet&& other); + OverlapRangeSet(OverlapRangeSet&& other); + OverlapRangeSet& operator=(OverlapRangeSet&& other); void Add(AddressType base_address, size_t size); void Subtract(AddressType base_address, size_t size); @@ -66,8 +66,8 @@ public: void ForEachInRange(AddressType device_addr, size_t size, Func&& func) const; private: - struct SplitRangeSetImpl; - std::unique_ptr m_impl; + struct OverlapRangeSetImpl; + std::unique_ptr m_impl; }; -} // namespace Common \ No newline at end of file +} // namespace Common diff --git a/src/common/range_sets.inc b/src/common/range_sets.inc index 705ebd4a1..b83eceb7b 100644 --- a/src/common/range_sets.inc +++ b/src/common/range_sets.inc @@ -19,14 +19,18 @@ namespace Common { +namespace { +template +using RangeSetsAllocator = + boost::fast_pool_allocator; +} + template struct RangeSet::RangeSetImpl { - template - using MyAllocator = boost::fast_pool_allocator; using IntervalSet = boost::icl::interval_set< AddressType, std::less, ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), - MyAllocator>; + RangeSetsAllocator>; using IntervalType = typename IntervalSet::interval_type; RangeSetImpl() = default; @@ -88,18 +92,15 @@ struct RangeSet::RangeSetImpl { }; template -struct SplitRangeSet::SplitRangeSetImpl { - template - using MyAllocator = boost::fast_pool_allocator; +struct OverlapRangeSet::OverlapRangeSetImpl { using IntervalSet = boost::icl::split_interval_map< AddressType, s32, boost::icl::partial_enricher, std::less, boost::icl::inplace_plus, boost::icl::inter_section, - ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), MyAllocator>; + ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, AddressType, std::less), RangeSetsAllocator>; using IntervalType = typename IntervalSet::interval_type; - SplitRangeSetImpl() = default; - ~SplitRangeSetImpl() = default; + OverlapRangeSetImpl() = default; + ~OverlapRangeSetImpl() = default; void Add(AddressType base_address, size_t size) { AddressType end_address = base_address + static_cast(size); @@ -160,7 +161,7 @@ struct SplitRangeSet::SplitRangeSetImpl { } const AddressType start_address = base_address; const AddressType end_address = start_address + size; - const SplitRangeSetImpl::IntervalType search_interval{start_address, end_address}; + const OverlapRangeSetImpl::IntervalType search_interval{start_address, end_address}; auto it = m_split_ranges_set.lower_bound(search_interval); if (it == m_split_ranges_set.end()) { return; @@ -230,72 +231,74 @@ void RangeSet::ForEach(Func&& func) const { template template -void RangeSet::ForEachInRange(AddressType base_address, size_t size, Func&& func) const { +void RangeSet::ForEachInRange(AddressType base_address, size_t size, + Func&& func) const { m_impl->ForEachInRange(base_address, size, std::move(func)); } template -SplitRangeSet::SplitRangeSet() { - m_impl = std::make_unique::SplitRangeSetImpl>(); +OverlapRangeSet::OverlapRangeSet() { + m_impl = std::make_unique::OverlapRangeSetImpl>(); } template -SplitRangeSet::~SplitRangeSet() = default; +OverlapRangeSet::~OverlapRangeSet() = default; template -SplitRangeSet::SplitRangeSet(SplitRangeSet&& other) { - m_impl = std::make_unique::SplitRangeSetImpl>(); +OverlapRangeSet::OverlapRangeSet(OverlapRangeSet&& other) { + m_impl = std::make_unique::OverlapRangeSetImpl>(); m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set); } template -SplitRangeSet& SplitRangeSet::operator=(SplitRangeSet&& other) { +OverlapRangeSet& OverlapRangeSet::operator=(OverlapRangeSet&& other) { m_impl->m_split_ranges_set = std::move(other.m_impl->m_split_ranges_set); } template -void SplitRangeSet::Add(AddressType base_address, size_t size) { +void OverlapRangeSet::Add(AddressType base_address, size_t size) { m_impl->Add(base_address, size); } template -void SplitRangeSet::Subtract(AddressType base_address, size_t size) { +void OverlapRangeSet::Subtract(AddressType base_address, size_t size) { m_impl->template Subtract(base_address, size, 1, [](AddressType, AddressType) {}); } template template -void SplitRangeSet::Subtract(AddressType base_address, size_t size, Func&& on_delete) { +void OverlapRangeSet::Subtract(AddressType base_address, size_t size, + Func&& on_delete) { m_impl->template Subtract(base_address, size, 1, std::move(on_delete)); } template -void SplitRangeSet::DeleteAll(AddressType base_address, size_t size) { +void OverlapRangeSet::DeleteAll(AddressType base_address, size_t size) { m_impl->template Subtract(base_address, size, std::numeric_limits::max(), - [](AddressType, AddressType) {}); + [](AddressType, AddressType) {}); } template -void SplitRangeSet::Clear() { +void OverlapRangeSet::Clear() { m_impl->m_split_ranges_set.clear(); } template -bool SplitRangeSet::Empty() const { +bool OverlapRangeSet::Empty() const { return m_impl->m_split_ranges_set.empty(); } template template -void SplitRangeSet::ForEach(Func&& func) const { +void OverlapRangeSet::ForEach(Func&& func) const { m_impl->ForEach(func); } template template -void SplitRangeSet::ForEachInRange(AddressType base_address, size_t size, - Func&& func) const { +void OverlapRangeSet::ForEachInRange(AddressType base_address, size_t size, + Func&& func) const { m_impl->ForEachInRange(base_address, size, std::move(func)); } -} // namespace Common \ No newline at end of file +} // namespace Common -- cgit v1.2.3