1 /*******************************************************************************
2 * tests/container/lru_cache_test.cpp
3 *
4 * Borrowed from https://github.com/lamerman/cpp-lru-cache by Alexander
5 * Ponomarev under BSD license and modified for Thrill's block pool.
6 *
7 * Part of tlx - http://panthema.net/tlx
8 *
9 * Copyright (C) 2016-2017 Timo Bingmann <tb@panthema.net>
10 *
11 * All rights reserved. Published under the Boost Software License, Version 1.0
12 ******************************************************************************/
13
14 #include <tlx/container/lru_cache.hpp>
15 #include <tlx/die.hpp>
16
17 namespace tlx {
18
19 // instantiations
20 template class tlx::LruCacheSet<size_t>;
21 template class tlx::LruCacheMap<size_t, size_t>;
22
23 } // namespace tlx
24
25 /******************************************************************************/
26 // LruCacheSet
27
test_set_simple_put()28 static void test_set_simple_put() {
29 tlx::LruCacheSet<size_t> cache;
30 cache.put(7);
31 die_unless(cache.exists(7));
32 die_unequal(1u, cache.size());
33 }
34
test_set_missing_value()35 static void test_set_missing_value() {
36 tlx::LruCacheSet<size_t> cache;
37 die_unless_throws(cache.touch(7), std::range_error);
38 }
39
test_set_keep_all_values_within_capacity()40 static void test_set_keep_all_values_within_capacity() {
41 tlx::LruCacheSet<size_t> cache;
42
43 static constexpr size_t test_size = 100;
44 static constexpr size_t capacity = 50;
45
46 // put more items into cache than capacity
47 for (size_t i = 0; i < test_size; ++i) {
48 cache.put(i);
49
50 while (cache.size() > capacity) {
51 auto x = cache.pop();
52 die_unequal(x, i - capacity);
53 }
54 }
55
56 // check state of cache
57 for (size_t i = 0; i < test_size - capacity; ++i) {
58 die_if(cache.exists(i));
59 }
60 for (size_t i = test_size - capacity; i < test_size; ++i) {
61 die_unless(cache.exists(i));
62 }
63
64 die_unequal(capacity, cache.size());
65
66 // touch three existing keys, only two exist
67
68 cache.touch(70);
69 cache.put(75);
70 die_unless(cache.touch_if_exists(80));
71 die_if(cache.touch_if_exists(20));
72
73 // erase some keys
74
75 cache.erase(90);
76 die_unless(cache.erase_if_exists(95));
77 die_if(cache.erase_if_exists(45));
78
79 // check contents of cache
80
81 die_unequal(capacity - 2, cache.size());
82
83 for (size_t i = 0; i < test_size - capacity; ++i) {
84 die_if(cache.exists(i));
85 }
86 for (size_t i = test_size - capacity; i < test_size; ++i) {
87 if (i == 90 || i == 95) {
88 die_if(cache.exists(i));
89 }
90 else {
91 die_unless(cache.exists(i));
92 }
93 }
94
95 // check order in which items are evicted, 70 and 80 must be at the end
96
97 die_unequal(capacity - 2, cache.size());
98
99 for (size_t i = 50; i < 100; ++i) {
100 if (i == 70 || i == 75 || i == 80 || i == 90 || i == 95) ++i;
101 die_unequal(cache.pop(), i);
102 }
103
104 die_unequal(cache.pop(), 70u);
105 die_unequal(cache.pop(), 75u);
106 die_unequal(cache.pop(), 80u);
107 die_unequal(0u, cache.size());
108 }
109
110 /******************************************************************************/
111 // LruCacheMap
112
test_map_simple_put()113 static void test_map_simple_put() {
114 tlx::LruCacheMap<size_t, size_t> cache;
115 cache.put(7, 777);
116 die_unless(cache.exists(7));
117 die_unequal(777u, cache.get(7));
118 die_unequal(1u, cache.size());
119 }
120
test_map_missing_value()121 static void test_map_missing_value() {
122 tlx::LruCacheMap<size_t, size_t> cache;
123 die_unless_throws(cache.get(7), std::range_error);
124 die_unless_throws(cache.touch(7), std::range_error);
125 }
126
test_map_keep_all_values_within_capacity()127 static void test_map_keep_all_values_within_capacity() {
128 tlx::LruCacheMap<size_t, size_t> cache;
129
130 static constexpr size_t test_size = 100;
131 static constexpr size_t capacity = 50;
132
133 // put more items into cache than capacity
134 for (size_t i = 0; i < test_size; ++i) {
135 cache.put(i, i);
136
137 while (cache.size() > capacity) {
138 auto x = cache.pop();
139 die_unequal(x.first, i - capacity);
140 }
141 }
142
143 // check state of cache
144 for (size_t i = 0; i < test_size - capacity; ++i) {
145 die_if(cache.exists(i));
146 }
147 for (size_t i = test_size - capacity; i < test_size; ++i) {
148 die_unless(cache.exists(i));
149 die_unequal(i, cache.get(i));
150 }
151
152 die_unequal(capacity, cache.size());
153
154 // touch three existing keys, only two exist
155
156 cache.touch(70);
157 cache.put(75, 75);
158 die_unless(cache.touch_if_exists(80));
159 die_if(cache.touch_if_exists(20));
160
161 // erase some keys
162
163 cache.erase(90);
164 die_unless(cache.erase_if_exists(95));
165 die_if(cache.erase_if_exists(45));
166
167 // check contents of cache
168
169 die_unequal(capacity - 2, cache.size());
170
171 for (size_t i = 0; i < test_size - capacity; ++i) {
172 die_if(cache.exists(i));
173 }
174 for (size_t i = test_size - capacity; i < test_size; ++i) {
175 if (i == 90 || i == 95) {
176 die_if(cache.exists(i));
177 }
178 else {
179 die_unless(cache.exists(i));
180 die_unequal(i, cache.get(i));
181 }
182 }
183
184 // check order in which items are evicted, 70 and 80 must be at the end
185
186 die_unequal(capacity - 2, cache.size());
187
188 for (size_t i = 50; i < 100; ++i) {
189 if (i == 70 || i == 75 || i == 80 || i == 90 || i == 95) ++i;
190 die_unequal(cache.pop().first, i);
191 }
192
193 die_unequal(cache.pop().first, 70u);
194 die_unequal(cache.pop().first, 75u);
195 die_unequal(cache.pop().first, 80u);
196 die_unequal(0u, cache.size());
197 }
198
main()199 int main() {
200
201 test_set_simple_put();
202 test_set_missing_value();
203 test_set_keep_all_values_within_capacity();
204
205 test_map_simple_put();
206 test_map_missing_value();
207 test_map_keep_all_values_within_capacity();
208
209 return 0;
210 }
211
212 /******************************************************************************/
213