tree 2fb7b7c30dafac2b1ac8f0beaaf85cb9f495549a
parent 2430d665d3f2f3a3f4ec3fbaab137c5dc65c9e84
author Ben Clayton <bclayton@google.com> 1585957693 +0100
committer Ben Clayton <bclayton@google.com> 1587027255 +0000

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>