summaryrefslogtreecommitdiffstats
path: root/src/common/lru_cache.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/common/lru_cache.h140
1 files changed, 140 insertions, 0 deletions
diff --git a/src/common/lru_cache.h b/src/common/lru_cache.h
new file mode 100644
index 000000000..365488ba5
--- /dev/null
+++ b/src/common/lru_cache.h
@@ -0,0 +1,140 @@
+// 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();
+ auto& item = item_pool.emplace_back();
+ 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