diff options
author | Fernando Sahmkow <fsahmkow27@gmail.com> | 2022-11-17 16:36:53 +0100 |
---|---|---|
committer | Fernando Sahmkow <fsahmkow27@gmail.com> | 2023-01-01 22:43:57 +0100 |
commit | 18637766efd1ff9a0c22967553983cfda69c96ca (patch) | |
tree | 142d4cab2de27ce250d246f0355fec97748a7bcf /src/common/range_map.h | |
parent | MacroHLE: Add HLE replacement for base vertex and base instance. (diff) | |
download | yuzu-18637766efd1ff9a0c22967553983cfda69c96ca.tar yuzu-18637766efd1ff9a0c22967553983cfda69c96ca.tar.gz yuzu-18637766efd1ff9a0c22967553983cfda69c96ca.tar.bz2 yuzu-18637766efd1ff9a0c22967553983cfda69c96ca.tar.lz yuzu-18637766efd1ff9a0c22967553983cfda69c96ca.tar.xz yuzu-18637766efd1ff9a0c22967553983cfda69c96ca.tar.zst yuzu-18637766efd1ff9a0c22967553983cfda69c96ca.zip |
Diffstat (limited to 'src/common/range_map.h')
-rw-r--r-- | src/common/range_map.h | 139 |
1 files changed, 139 insertions, 0 deletions
diff --git a/src/common/range_map.h b/src/common/range_map.h new file mode 100644 index 000000000..993e21643 --- /dev/null +++ b/src/common/range_map.h @@ -0,0 +1,139 @@ +// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project +// SPDX-License-Identifier: GPL-3.0-or-later + +#pragma once + +#include <map> +#include <type_traits> + +#include "common/common_types.h" + +namespace Common { + +template <typename KeyTBase, typename ValueT> +class RangeMap { +private: + using KeyT = std::conditional_t<std::is_signed_v<KeyTBase>, typename KeyTBase, + std::make_signed_t<KeyTBase>>; + +public: + explicit RangeMap(ValueT null_value_) : null_value{null_value_} { + container.emplace(std::numeric_limits<KeyT>::min(), null_value); + }; + ~RangeMap() = default; + + void Map(KeyTBase address, KeyTBase address_end, ValueT value) { + KeyT new_address = static_cast<KeyT>(address); + KeyT new_address_end = static_cast<KeyT>(address_end); + if (new_address < 0) { + new_address = 0; + } + if (new_address_end < 0) { + new_address_end = 0; + } + InternalMap(new_address, new_address_end, value); + } + + void Unmap(KeyTBase address, KeyTBase address_end) { + Map(address, address_end, null_value); + } + + [[nodiscard]] size_t GetContinousSizeFrom(KeyTBase address) const { + const KeyT new_address = static_cast<KeyT>(address); + if (new_address < 0) { + return 0; + } + return ContinousSizeInternal(new_address); + } + + [[nodiscard]] ValueT GetValueAt(KeyT address) const { + const KeyT new_address = static_cast<KeyT>(address); + if (new_address < 0) { + return null_value; + } + return GetValueInternal(new_address); + } + +private: + using MapType = std::map<KeyT, ValueT>; + using IteratorType = MapType::iterator; + using ConstIteratorType = MapType::const_iterator; + + size_t ContinousSizeInternal(KeyT address) const { + const auto it = GetFirstElemnentBeforeOrOn(address); + if (it == container.end() || it->second == null_value) { + return 0; + } + const auto it_end = std::next(it); + if (it_end == container.end()) { + return std::numeric_limits<KeyT>::max() - address; + } + return it_end->first - address; + } + + ValueT GetValueInternal(KeyT address) const { + const auto it = GetFirstElemnentBeforeOrOn(address); + if (it == container.end()) { + return null_value; + } + return it->second; + } + + ConstIteratorType GetFirstElemnentBeforeOrOn(KeyT address) const { + auto it = container.lower_bound(address); + if (it == container.begin()) { + return it; + } + if (it != container.end() && (it->first == address)) { + return it; + } + --it; + return it; + } + + ValueT GetFirstValueWithin(KeyT address) { + auto it = container.lower_bound(address); + if (it == container.begin()) { + return it->second; + } + if (it == container.end()) [[unlikely]] { // this would be a bug + return null_value; + } + --it; + return it->second; + } + + ValueT GetLastValueWithin(KeyT address) { + auto it = container.upper_bound(address); + if (it == container.end()) { + return null_value; + } + if (it == container.begin()) [[unlikely]] { // this would be a bug + return it->second; + } + --it; + return it->second; + } + + void InternalMap(KeyT address, KeyT address_end, ValueT value) { + const bool must_add_start = GetFirstValueWithin(address) != value; + const ValueT last_value = GetLastValueWithin(address_end); + const bool must_add_end = last_value != value; + auto it = container.lower_bound(address); + const auto it_end = container.upper_bound(address_end); + while (it != it_end) { + it = container.erase(it); + } + if (must_add_start) { + container.emplace(address, value); + } + if (must_add_end) { + container.emplace(address_end, last_value); + } + } + + ValueT null_value; + MapType container; +}; + +} // namespace Common |