summaryrefslogtreecommitdiffstats
path: root/src/common
diff options
context:
space:
mode:
authorFernando Sahmkow <fsahmkow27@gmail.com>2021-08-15 15:35:53 +0200
committerFernando Sahmkow <fsahmkow27@gmail.com>2021-08-28 17:54:12 +0200
commitd540d284b5711f044678191bbab858de626103a9 (patch)
tree42839b218c848973c1886c7b288d2708821130a5 /src/common
parentMerge pull request #6929 from yuzu-emu/revert-6870-trace-back-stack-back-stack-back (diff)
downloadyuzu-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')
-rw-r--r--src/common/lru_cache.h141
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