Merge pull request #6897 from FernandoS27/pineapple-does-not-belong-in-pizza

Project <tentative title>: Rework Garbage Collection.

3 files changed, 140 insertions, 3 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
diff --git a/src/common/settings.cpp b/src/common/settings.cpp
index 996315999..fd3b639cd 100644
--- a/src/common/settings.cpp
+++ b/src/common/settings.cpp
@@ -59,7 +59,6 @@ void LogSettings() {
     log_setting("Renderer_UseVsync", values.use_vsync.GetValue());
     log_setting("Renderer_ShaderBackend", values.shader_backend.GetValue());
     log_setting("Renderer_UseAsynchronousShaders", values.use_asynchronous_shaders.GetValue());
-    log_setting("Renderer_UseGarbageCollection", values.use_caches_gc.GetValue());
     log_setting("Renderer_AnisotropicFilteringLevel", values.max_anisotropy.GetValue());
     log_setting("Audio_OutputEngine", values.sink_id.GetValue());
     log_setting("Audio_EnableAudioStretching", values.enable_audio_stretching.GetValue());
@@ -143,7 +142,6 @@ void RestoreGlobalState(bool is_powered_on) {
     values.shader_backend.SetGlobal(true);
     values.use_asynchronous_shaders.SetGlobal(true);
     values.use_fast_gpu_time.SetGlobal(true);
-    values.use_caches_gc.SetGlobal(true);
     values.bg_red.SetGlobal(true);
     values.bg_green.SetGlobal(true);
     values.bg_blue.SetGlobal(true);
diff --git a/src/common/settings.h b/src/common/settings.h
index 20769d310..ec4d381e8 100644
--- a/src/common/settings.h
+++ b/src/common/settings.h
@@ -475,7 +475,6 @@ struct Values {
                                                 ShaderBackend::SPIRV, "shader_backend"};
     Setting<bool> use_asynchronous_shaders{false, "use_asynchronous_shaders"};
     Setting<bool> use_fast_gpu_time{true, "use_fast_gpu_time"};
-    Setting<bool> use_caches_gc{false, "use_caches_gc"};
 
     Setting<u8> bg_red{0, "bg_red"};
     Setting<u8> bg_green{0, "bg_green"};