diff options
author | Fernando Sahmkow <fsahmkow27@gmail.com> | 2021-08-15 15:35:53 +0200 |
---|---|---|
committer | Fernando Sahmkow <fsahmkow27@gmail.com> | 2021-08-28 17:54:12 +0200 |
commit | d540d284b5711f044678191bbab858de626103a9 (patch) | |
tree | 42839b218c848973c1886c7b288d2708821130a5 /src/common/lru_cache.h | |
parent | Merge pull request #6929 from yuzu-emu/revert-6870-trace-back-stack-back-stack-back (diff) | |
download | yuzu-d540d284b5711f044678191bbab858de626103a9.tar yuzu-d540d284b5711f044678191bbab858de626103a9.tar.gz yuzu-d540d284b5711f044678191bbab858de626103a9.tar.bz2 yuzu-d540d284b5711f044678191bbab858de626103a9.tar.lz yuzu-d540d284b5711f044678191bbab858de626103a9.tar.xz yuzu-d540d284b5711f044678191bbab858de626103a9.tar.zst yuzu-d540d284b5711f044678191bbab858de626103a9.zip |
Diffstat (limited to 'src/common/lru_cache.h')
-rw-r--r-- | src/common/lru_cache.h | 141 |
1 files changed, 141 insertions, 0 deletions
diff --git a/src/common/lru_cache.h b/src/common/lru_cache.h new file mode 100644 index 000000000..048e9c3da --- /dev/null +++ b/src/common/lru_cache.h @@ -0,0 +1,141 @@ +// Copyright 2021 yuzu Emulator Project +// Licensed under GPLv2+ or any later version +// Refer to the license.txt file included. + +#pragma once + +#include <deque> +#include <memory> +#include <type_traits> + +#include "common/common_types.h" + +namespace Common { + +template <class Traits> +class LeastRecentlyUsedCache { + using ObjectType = typename Traits::ObjectType; + using TickType = typename Traits::TickType; + + struct Item { + ObjectType obj; + TickType tick; + Item* next{}; + Item* prev{}; + }; + +public: + LeastRecentlyUsedCache() : first_item{}, last_item{} {} + ~LeastRecentlyUsedCache() = default; + + size_t Insert(ObjectType obj, TickType tick) { + const auto new_id = build(); + auto& item = item_pool[new_id]; + item.obj = obj; + item.tick = tick; + attach(item); + return new_id; + } + + void Touch(size_t id, TickType tick) { + auto& item = item_pool[id]; + if (item.tick >= tick) { + return; + } + item.tick = tick; + if (&item == last_item) { + return; + } + detach(item); + attach(item); + } + + void Free(size_t id) { + auto& item = item_pool[id]; + detach(item); + item.prev = nullptr; + item.next = nullptr; + free_items.push_back(id); + } + + template <typename Func> + void ForEachItemBelow(TickType tick, Func&& func) { + static constexpr bool RETURNS_BOOL = + std::is_same_v<std::invoke_result<Func, ObjectType>, bool>; + Item* iterator = first_item; + while (iterator) { + if (static_cast<s64>(tick) - static_cast<s64>(iterator->tick) < 0) { + return; + } + Item* next = iterator->next; + if constexpr (RETURNS_BOOL) { + if (func(iterator->obj)) { + return; + } + } else { + func(iterator->obj); + } + iterator = next; + } + } + +private: + size_t build() { + if (free_items.empty()) { + const size_t item_id = item_pool.size(); + item_pool.emplace_back(); + auto& item = item_pool[item_id]; + item.next = nullptr; + item.prev = nullptr; + return item_id; + } + const size_t item_id = free_items.front(); + free_items.pop_front(); + auto& item = item_pool[item_id]; + item.next = nullptr; + item.prev = nullptr; + return item_id; + } + + void attach(Item& item) { + if (!first_item) { + first_item = &item; + } + if (!last_item) { + last_item = &item; + } else { + item.prev = last_item; + last_item->next = &item; + item.next = nullptr; + last_item = &item; + } + } + + void detach(Item& item) { + if (item.prev) { + item.prev->next = item.next; + } + if (item.next) { + item.next->prev = item.prev; + } + if (&item == first_item) { + first_item = item.next; + if (first_item) { + first_item->prev = nullptr; + } + } + if (&item == last_item) { + last_item = item.prev; + if (last_item) { + last_item->next = nullptr; + } + } + } + + std::deque<Item> item_pool; + std::deque<size_t> free_items; + Item* first_item; + Item* last_item; +}; + +} // namespace Common |