blob: 36cea5d27e5046ab1672160789ae012ea6755e90 (
plain) (
tree)
|
|
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later
#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
|
