util/lru_cache.h - TerrainGen coverage

util/lru_cache.h

Line	Branch	Exec	Source
1			/// @file
2			/// @brief `LruCache`, a sharded thread-safe least-recently-used cache.
3			#pragma once
4
5			#include <algorithm>
6			#include <array>
7			#include <cstddef>
8			#include <functional>
9			#include <list>
10			#include <memory>
11			#include <mutex>
12			#include <stdexcept>
13			#include <unordered_map>
14			#include <utility>
15
16			namespace terraingen {
17
18			/// A thread-safe cache of recomputable values, holding about `capacity` units of cost and
19			/// evicting the least recently used.
20			///
21			/// Keys are spread over 16 shards with even shares of the capacity; a shard always keeps its
22			/// newest value, so it can exceed its share by one value. If two threads compute the same key at
23			/// once, both get the first value stored.
24			template <typename Key, typename Value, typename Hash = std::hash<Key>> class LruCache {
25			public:
26			/// Measures a value's cost (a count or bytes).
27			using Cost = std::function<std::size_t(const Value&)>;
28			/// Told how many values one store evicted.
29			using OnEvict = std::function<void(std::size_t evicted)>;
30
31			/// An empty cache.
32			/// @param capacity The total cost held, in `cost` units.
33			/// @param onEvict If given, told how many values a store evicted, outside any lock.
34			/// @throws std::invalid_argument if `capacity` is zero.
35		1402	LruCache(std::size_t capacity, Cost cost, OnEvict onEvict = {})
36		1402	: capacity_(capacity), cost_(std::move(cost)), onEvict_(std::move(onEvict)) {
37	11/18 terraingen::LruCache<int, int, std::hash<int> >::LruCache(unsigned long, std::function<unsigned long (int const&)>, std::function<void (unsigned long)>): ✓ Branch 0 taken 1 time. ✗ Branch 1 not taken. terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::LruCache(unsigned long, std::function<unsigned long (std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)>, std::function<void (unsigned long)>): ✗ Branch 0 not taken. ✓ Branch 1 taken 1 time. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::LruCache(unsigned long, std::function<unsigned long (double const&)>, std::function<void (unsigned long)>): ✗ Branch 0 not taken. ✓ Branch 1 taken 2 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::CraterList const&)>, std::function<void (unsigned long)>): ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 885 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::DiffusedProfile::Table const&)>, std::function<void (unsigned long)>): ✗ Branch 0 not taken. ✓ Branch 1 taken 50 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::EvaluationCache::Holder const&)>, std::function<void (unsigned long)>): ✗ Branch 0 not taken. ✓ Branch 1 taken 75 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::Raster<float> const&)>, std::function<void (unsigned long)>): ✓ Branch 0 taken 1 time. ✓ Branch 1 taken 8 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::LruCache(unsigned long, std::function<unsigned long (std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > const&)>, std::function<void (unsigned long)>): ✗ Branch 0 not taken. ✓ Branch 1 taken 189 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::LruCache(unsigned long, std::function<unsigned long (terraingen::BoulderShape const&)>, std::function<void (unsigned long)>): ✗ Branch 0 not taken. ✓ Branch 1 taken 189 times.	1402	if (capacity_ == 0) {
38	3/9 terraingen::LruCache<int, int, std::hash<int> >::LruCache(unsigned long, std::function<unsigned long (int const&)>, std::function<void (unsigned long)>): ✓ Branch 2 taken 1 time. terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::LruCache(unsigned long, std::function<unsigned long (std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)>, std::function<void (unsigned long)>): ✗ Branch 2 not taken. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::LruCache(unsigned long, std::function<unsigned long (double const&)>, std::function<void (unsigned long)>): ✗ Branch 2 not taken. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::CraterList const&)>, std::function<void (unsigned long)>): ✓ Branch 2 taken 1 time. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::DiffusedProfile::Table const&)>, std::function<void (unsigned long)>): ✗ Branch 2 not taken. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::EvaluationCache::Holder const&)>, std::function<void (unsigned long)>): ✗ Branch 2 not taken. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::LruCache(unsigned long, std::function<unsigned long (terraingen::Raster<float> const&)>, std::function<void (unsigned long)>): ✓ Branch 2 taken 1 time. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::LruCache(unsigned long, std::function<unsigned long (std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > const&)>, std::function<void (unsigned long)>): ✗ Branch 2 not taken. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::LruCache(unsigned long, std::function<unsigned long (terraingen::BoulderShape const&)>, std::function<void (unsigned long)>): ✗ Branch 2 not taken.	3	throw std::invalid_argument("A cache needs a positive capacity");
39			}
40		1408	}
41
42			/// The value for a key, computed by `compute` outside the lock when it is not held.
43			/// @throws Whatever `compute` throws; nothing is stored then.
44		4319871	std::shared_ptr<const Value> Get(const Key& key, const std::function<Value()>& compute) {
45	1/1 ✓ Branch 1 taken 254249 times.	4319871	Shard& shard = shards_[Hash{}(key) % kShards];
46			{
47	9/9 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 200 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 320008 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 2510955 times. ✓ Branch 1 taken 254249 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 1085962 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 132231 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 673 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 4405 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 11188 times.	4319871	const std::lock_guard lock(shard.mutex);
48	24/24 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 200 times. ✓ Branch 5 taken 1 time. ✓ Branch 6 taken 199 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 320008 times. ✓ Branch 5 taken 319936 times. ✓ Branch 6 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 2765204 times. ✓ Branch 5 taken 2658621 times. ✓ Branch 6 taken 106583 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 1085962 times. ✓ Branch 5 taken 1085873 times. ✓ Branch 6 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 132231 times. ✓ Branch 5 taken 115448 times. ✓ Branch 6 taken 16783 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 673 times. ✓ Branch 5 taken 34 times. ✓ Branch 6 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 4405 times. ✓ Branch 5 taken 4076 times. ✓ Branch 6 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 11188 times. ✓ Branch 5 taken 10125 times. ✓ Branch 6 taken 1063 times.	4319871	if (const auto found = shard.entries.find(key); found != shard.entries.end()) {
49		4194114	shard.recency.splice(shard.recency.begin(), shard.recency, found->second.recent);
50		4194114	return found->second.value;
51			}
52	16/16 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 199 times. ✓ Branch 2 taken 1 time. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 72 times. ✓ Branch 2 taken 319936 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 106583 times. ✓ Branch 2 taken 2658621 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 89 times. ✓ Branch 2 taken 1085873 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 16783 times. ✓ Branch 2 taken 115448 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 639 times. ✓ Branch 2 taken 34 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 329 times. ✓ Branch 2 taken 4076 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 1063 times. ✓ Branch 2 taken 10125 times.	4319871	}
53	16/16 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 199 times. ✓ Branch 4 taken 199 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 72 times. ✓ Branch 4 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 106583 times. ✓ Branch 4 taken 106583 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 89 times. ✓ Branch 4 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 16783 times. ✓ Branch 4 taken 16783 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 639 times. ✓ Branch 4 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 329 times. ✓ Branch 4 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 1063 times. ✓ Branch 4 taken 1063 times.	125757	auto value = std::make_shared<const Value>(compute());
54	8/8 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 2 taken 199 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 2 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 2 taken 106583 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 2 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 2 taken 16783 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 2 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 2 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 2 taken 1063 times.	125757	const std::size_t cost = cost_(*value);
55		125757	const std::size_t budget = std::max<std::size_t>(1, capacity_ / kShards);
56		125757	std::size_t evicted = 0;
57			{
58	8/8 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 199 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 106583 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 16783 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 1063 times.	125757	const std::lock_guard lock(shard.mutex);
59	19/24 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 199 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 199 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 72 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 106583 times. ✓ Branch 5 taken 110 times. ✓ Branch 6 taken 106473 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 89 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 16783 times. ✓ Branch 5 taken 272 times. ✓ Branch 6 taken 16511 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 639 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 329 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 1063 times. ✓ Branch 5 taken 6 times. ✓ Branch 6 taken 1057 times.	125757	if (const auto found = shard.entries.find(key); found != shard.entries.end()) {
60		388	return found->second.value;
61			}
62	8/8 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 199 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 106473 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 16511 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 1057 times.	125369	shard.recency.push_front(key);
63		125369	shard.entries.emplace(key, Entry{value, cost, shard.recency.begin()});
64		125369	shard.cost += cost;
65	25/48 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 0 taken 183 times. ✓ Branch 1 taken 199 times. ✓ Branch 3 taken 183 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 183 times. ✓ Branch 6 taken 199 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 72 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 0 taken 369 times. ✓ Branch 1 taken 106473 times. ✓ Branch 3 taken 369 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 369 times. ✓ Branch 6 taken 106473 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 89 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 16511 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 16511 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 0 taken 494 times. ✓ Branch 1 taken 639 times. ✓ Branch 3 taken 494 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 494 times. ✓ Branch 6 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 329 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 1057 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 1057 times.	126415	while (shard.cost > budget && shard.recency.size() > 1) {
66	3/8 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 2 taken 183 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✗ Branch 2 not taken. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 2 taken 369 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✗ Branch 2 not taken. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✗ Branch 2 not taken. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 2 taken 494 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✗ Branch 2 not taken. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✗ Branch 2 not taken.	1046	const auto oldest = shard.entries.find(shard.recency.back());
67		1046	shard.cost -= oldest->second.cost;
68	3/8 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 183 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 369 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 494 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✗ Branch 1 not taken.	1046	shard.entries.erase(oldest);
69		1046	shard.recency.pop_back();
70		1046	++evicted;
71			}
72		125369	shard.evictions += evicted;
73	11/16 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 199 times. ✗ Branch 2 not taken. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 1 taken 72 times. ✗ Branch 2 not taken. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 106473 times. ✓ Branch 2 taken 110 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 1 taken 89 times. ✗ Branch 2 not taken. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 1 taken 16511 times. ✓ Branch 2 taken 272 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 1 taken 639 times. ✗ Branch 2 not taken. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 1 taken 329 times. ✗ Branch 2 not taken. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 1 taken 1057 times. ✓ Branch 2 taken 6 times.	125757	}
74	24/48 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 0 taken 183 times. ✓ Branch 1 taken 16 times. ✓ Branch 3 taken 183 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 183 times. ✓ Branch 6 taken 16 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 72 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 72 times. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 0 taken 369 times. ✓ Branch 1 taken 106104 times. ✓ Branch 3 taken 369 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 369 times. ✓ Branch 6 taken 106104 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 89 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 89 times. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 16511 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 16511 times. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 0 taken 494 times. ✓ Branch 1 taken 145 times. ✗ Branch 3 not taken. ✓ Branch 4 taken 494 times. ✗ Branch 5 not taken. ✓ Branch 6 taken 639 times. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 329 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 329 times. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✗ Branch 0 not taken. ✓ Branch 1 taken 1057 times. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✓ Branch 6 taken 1057 times.	125369	if (evicted > 0 && onEvict_) {
75	2/8 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 1 taken 183 times. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 1 taken 369 times. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✗ Branch 1 not taken. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✗ Branch 1 not taken.	552	onEvict_(evicted);
76			}
77		125369	return value;
78	8/24 terraingen::LruCache<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::hash<int> >::Get(int const&, std::function<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > ()> const&): ✓ Branch 3 taken 199 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. terraingen::LruCache<terraingen::BoulderLayer::MeanCell, double, terraingen::BoulderLayer::MeanCellHash>::Get(terraingen::BoulderLayer::MeanCell const&, std::function<double ()> const&): ✓ Branch 3 taken 72 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. terraingen::LruCache<terraingen::CraterCellCache::Key, terraingen::CraterList, terraingen::CraterCellCache::KeyHash>::Get(terraingen::CraterCellCache::Key const&, std::function<terraingen::CraterList ()> const&): ✓ Branch 3 taken 106473 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. terraingen::LruCache<terraingen::DiffusedProfile::Key, terraingen::DiffusedProfile::Table, terraingen::DiffusedProfile::KeyHash>::Get(terraingen::DiffusedProfile::Key const&, std::function<terraingen::DiffusedProfile::Table ()> const&): ✓ Branch 3 taken 89 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. terraingen::LruCache<terraingen::EvaluationCache::Key, terraingen::EvaluationCache::Holder, terraingen::EvaluationCache::KeyHash>::Get(terraingen::EvaluationCache::Key const&, std::function<terraingen::EvaluationCache::Holder ()> const&): ✓ Branch 3 taken 16511 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. terraingen::LruCache<terraingen::TileKey, terraingen::Raster<float>, terraingen::TileKeyHash>::Get(terraingen::TileKey const&, std::function<terraingen::Raster<float> ()> const&): ✓ Branch 3 taken 639 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. terraingen::LruCache<unsigned long, std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> >, std::hash<unsigned long> >::Get(unsigned long const&, std::function<std::vector<terraingen::BoulderFragment, std::allocator<terraingen::BoulderFragment> > ()> const&): ✓ Branch 3 taken 329 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken. terraingen::LruCache<unsigned long, terraingen::BoulderShape, std::hash<unsigned long> >::Get(unsigned long const&, std::function<terraingen::BoulderShape ()> const&): ✓ Branch 3 taken 1057 times. ✗ Branch 6 not taken. ✗ Branch 7 not taken.	251126	}
79
80			/// The total cost of every value held, in `Cost` units.
81		8	std::size_t Size() const {
82		136	return Sum([](const Shard& shard) { return shard.cost; });
83			}
84
85			/// The number of values evicted since construction.
86		6	std::size_t Evictions() const {
87		102	return Sum([](const Shard& shard) { return shard.evictions; });
88			}
89
90			/// The capacity given at construction, in `Cost` units.
91		4	std::size_t Capacity() const {
92		4	return capacity_;
93			}
94
95			private:
96			struct Entry {
97			std::shared_ptr<const Value> value;
98			std::size_t cost = 0;
99			typename std::list<Key>::iterator recent;
100			};
101			struct Shard {
102			mutable std::mutex mutex;
103			std::list<Key> recency;
104			std::unordered_map<Key, Entry, Hash> entries;
105			std::size_t cost = 0;
106			std::size_t evictions = 0;
107			};
108			static constexpr std::size_t kShards = 16;
109
110		14	template <typename Field> std::size_t Sum(Field field) const {
111		14	std::size_t total = 0;
112	2/2 ✓ Branch 2 taken 64 times. ✓ Branch 3 taken 4 times.	238	for (const Shard& shard : shards_) {
113	1/1 ✓ Branch 1 taken 64 times.	224	const std::lock_guard lock(shard.mutex);
114		224	total += field(shard);
115			}
116		14	return total;
117			}
118
119			std::size_t capacity_;
120			Cost cost_;
121			OnEvict onEvict_;
122			std::array<Shard, kShards> shards_;
123			};
124
125			} // namespace terraingen
126