1 // Copyright 2020 The SwiftShader Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "System/LRUCache.hpp"
16
17 #include <gmock/gmock.h>
18 #include <gtest/gtest.h>
19
20 #include <vector>
21
22 using namespace sw;
23
24 namespace {
25
26 template<typename Cache>
checkRange(const Cache & cache,std::vector<std::pair<typename Cache::Key,typename Cache::Data>> list)27 void checkRange(const Cache &cache, std::vector<std::pair<typename Cache::Key, typename Cache::Data>> list)
28 {
29 size_t i = 0;
30 for(auto it : cache)
31 {
32 ASSERT_EQ(list[i].first, it.key());
33 ASSERT_EQ(list[i].second, it.data());
34 i++;
35 }
36 ASSERT_EQ(i, list.size());
37 }
38
39 } // namespace
40
41 ////////////////////////////////////////////////////////////////////////////////
42 // LRUCache
43 ////////////////////////////////////////////////////////////////////////////////
TEST(LRUCache,Empty)44 TEST(LRUCache, Empty)
45 {
46 LRUCache<std::string, std::string> cache(8);
47 ASSERT_EQ(cache.lookup(""), "");
48 ASSERT_EQ(cache.lookup("123"), "");
49 bool looped = false;
50 for(auto ignored : cache)
51 {
52 (void)ignored;
53 looped = true;
54 }
55 if(looped)
56 {
57 FAIL() << "Should not loop on empty cache";
58 }
59 }
60
TEST(LRUCache,AddNoEviction)61 TEST(LRUCache, AddNoEviction)
62 {
63 LRUCache<std::string, std::string> cache(4);
64
65 cache.add("1", "one");
66 cache.add("2", "two");
67 cache.add("3", "three");
68 cache.add("4", "four");
69
70 ASSERT_EQ(cache.lookup("1"), "one");
71 ASSERT_EQ(cache.lookup("2"), "two");
72 ASSERT_EQ(cache.lookup("3"), "three");
73 ASSERT_EQ(cache.lookup("4"), "four");
74
75 checkRange(cache, {
76 { "4", "four" },
77 { "3", "three" },
78 { "2", "two" },
79 { "1", "one" },
80 });
81 }
82
TEST(LRUCache,AddWithEviction)83 TEST(LRUCache, AddWithEviction)
84 {
85 LRUCache<std::string, std::string> cache(4);
86
87 cache.add("1", "one");
88 cache.add("2", "two");
89 cache.add("3", "three");
90 cache.add("4", "four");
91 cache.add("5", "five");
92 cache.add("6", "six");
93
94 ASSERT_EQ(cache.lookup("1"), "");
95 ASSERT_EQ(cache.lookup("2"), "");
96 ASSERT_EQ(cache.lookup("3"), "three");
97 ASSERT_EQ(cache.lookup("4"), "four");
98 ASSERT_EQ(cache.lookup("5"), "five");
99 ASSERT_EQ(cache.lookup("6"), "six");
100
101 checkRange(cache, {
102 { "6", "six" },
103 { "5", "five" },
104 { "4", "four" },
105 { "3", "three" },
106 });
107 }
108
TEST(LRUCache,AddClearAdd)109 TEST(LRUCache, AddClearAdd)
110 {
111 LRUCache<std::string, std::string> cache(4);
112
113 // Add some data.
114 cache.add("1", "one");
115 cache.add("2", "two");
116 cache.add("3", "three");
117 cache.add("4", "four");
118 cache.add("5", "five");
119 cache.add("6", "six");
120
121 // Clear it.
122 cache.clear();
123
124 // Check has no data.
125 ASSERT_EQ(cache.lookup("1"), "");
126 ASSERT_EQ(cache.lookup("2"), "");
127 ASSERT_EQ(cache.lookup("3"), "");
128 ASSERT_EQ(cache.lookup("4"), "");
129 ASSERT_EQ(cache.lookup("5"), "");
130 ASSERT_EQ(cache.lookup("6"), "");
131
132 checkRange(cache, {});
133
134 // Add it again.
135 cache.add("1", "one");
136 cache.add("2", "two");
137 cache.add("3", "three");
138 cache.add("4", "four");
139 cache.add("5", "five");
140 cache.add("6", "six");
141
142 // Check has data.
143 ASSERT_EQ(cache.lookup("1"), "");
144 ASSERT_EQ(cache.lookup("2"), "");
145 ASSERT_EQ(cache.lookup("3"), "three");
146 ASSERT_EQ(cache.lookup("4"), "four");
147 ASSERT_EQ(cache.lookup("5"), "five");
148 ASSERT_EQ(cache.lookup("6"), "six");
149
150 checkRange(cache, {
151 { "6", "six" },
152 { "5", "five" },
153 { "4", "four" },
154 { "3", "three" },
155 });
156 }
157
TEST(LRUCache,Reordering)158 TEST(LRUCache, Reordering)
159 {
160 LRUCache<std::string, std::string> cache(4);
161
162 // Fill
163 cache.add("1", "one");
164 cache.add("2", "two");
165 cache.add("3", "three");
166 cache.add("4", "four");
167
168 // Push 2 then 4 to most recent
169 cache.add("2", "two");
170 cache.add("4", "four");
171
172 checkRange(cache, {
173 { "4", "four" },
174 { "2", "two" },
175 { "3", "three" },
176 { "1", "one" },
177 });
178 }