Reimplement LRUCache, fold away LRUSnapshotCache, add tests.
LRUCache previously had a complexity of O(n).
Reimplement using a `std::unordered_set` and a linked list to get this reduced to O(1).
Renamed `LRUCache::query()` to `LRUCache::get()`, as this is a more common verb for a cache, and the `query()` suggests it is side effect free (when it actually makes the entry MRU).
Move `LRUCache.hpp` from `src/Device` to `src/System` so it can be tested by `system-unittests`.
Move the logic of `LRUSnapshotCache` into `VkDevice::SamplingRoutineCache`, as this was the only place it was used, and made it exceptionally hard to separate mutex-locked data from non-locked data.
This is part of the work to get our code statically thread-safe-verifiable.
Bug: b/153194656
Change-Id: Ie02888ae6c7ed4066df77d692dfae28c3bc1664d
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/43489
Reviewed-by: Antonio Maiorano <amaiorano@google.com>
Kokoro-Result: kokoro <noreply+kokoro@google.com>
Presubmit-Ready: Ben Clayton <bclayton@google.com>
Tested-by: Ben Clayton <bclayton@google.com>
diff --git a/src/Device/RoutineCache.hpp b/src/Device/RoutineCache.hpp
index 9bf2e31..71046c3 100644
--- a/src/Device/RoutineCache.hpp
+++ b/src/Device/RoutineCache.hpp
@@ -15,7 +15,7 @@
#ifndef sw_RoutineCache_hpp
#define sw_RoutineCache_hpp
-#include "LRUCache.hpp"
+#include "System/LRUCache.hpp"
#include "Reactor/Reactor.hpp"
