1 /*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <stdlib.h>
18 #include <utils/JenkinsHash.h>
19 #include <utils/LruCache.h>
20 #include <cutils/log.h>
21 #include <gtest/gtest.h>
22
23 namespace {
24
25 typedef int SimpleKey;
26 typedef const char* StringValue;
27
28 struct ComplexKey {
29 int k;
30
ComplexKey__anon7a0f245b0111::ComplexKey31 explicit ComplexKey(int k) : k(k) {
32 instanceCount += 1;
33 }
34
ComplexKey__anon7a0f245b0111::ComplexKey35 ComplexKey(const ComplexKey& other) : k(other.k) {
36 instanceCount += 1;
37 }
38
~ComplexKey__anon7a0f245b0111::ComplexKey39 ~ComplexKey() {
40 instanceCount -= 1;
41 }
42
operator ==__anon7a0f245b0111::ComplexKey43 bool operator ==(const ComplexKey& other) const {
44 return k == other.k;
45 }
46
operator !=__anon7a0f245b0111::ComplexKey47 bool operator !=(const ComplexKey& other) const {
48 return k != other.k;
49 }
50
51 static ssize_t instanceCount;
52 };
53
54 ssize_t ComplexKey::instanceCount = 0;
55
56 struct ComplexValue {
57 int v;
58
ComplexValue__anon7a0f245b0111::ComplexValue59 explicit ComplexValue(int v) : v(v) {
60 instanceCount += 1;
61 }
62
ComplexValue__anon7a0f245b0111::ComplexValue63 ComplexValue(const ComplexValue& other) : v(other.v) {
64 instanceCount += 1;
65 }
66
~ComplexValue__anon7a0f245b0111::ComplexValue67 ~ComplexValue() {
68 instanceCount -= 1;
69 }
70
71 static ssize_t instanceCount;
72 };
73
74 ssize_t ComplexValue::instanceCount = 0;
75
76 } // namespace
77
78
79 namespace android {
80
81 typedef LruCache<ComplexKey, ComplexValue> ComplexCache;
82
hash_type(const ComplexKey & value)83 template<> inline android::hash_t hash_type(const ComplexKey& value) {
84 return hash_type(value.k);
85 }
86
87 class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
88 public:
EntryRemovedCallback()89 EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
~EntryRemovedCallback()90 ~EntryRemovedCallback() {}
operator ()(SimpleKey & k,StringValue & v)91 void operator()(SimpleKey& k, StringValue& v) {
92 callbackCount += 1;
93 lastKey = k;
94 lastValue = v;
95 }
96 ssize_t callbackCount;
97 SimpleKey lastKey;
98 StringValue lastValue;
99 };
100
101 class LruCacheTest : public testing::Test {
102 protected:
SetUp()103 virtual void SetUp() {
104 ComplexKey::instanceCount = 0;
105 ComplexValue::instanceCount = 0;
106 }
107
TearDown()108 virtual void TearDown() {
109 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
110 }
111
assertInstanceCount(ssize_t keys,ssize_t values)112 void assertInstanceCount(ssize_t keys, ssize_t values) {
113 if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
114 FAIL() << "Expected " << keys << " keys and " << values << " values "
115 "but there were actually " << ComplexKey::instanceCount << " keys and "
116 << ComplexValue::instanceCount << " values";
117 }
118 }
119 };
120
TEST_F(LruCacheTest,Empty)121 TEST_F(LruCacheTest, Empty) {
122 LruCache<SimpleKey, StringValue> cache(100);
123
124 EXPECT_EQ(NULL, cache.get(0));
125 EXPECT_EQ(0u, cache.size());
126 }
127
TEST_F(LruCacheTest,Simple)128 TEST_F(LruCacheTest, Simple) {
129 LruCache<SimpleKey, StringValue> cache(100);
130
131 cache.put(1, "one");
132 cache.put(2, "two");
133 cache.put(3, "three");
134 EXPECT_STREQ("one", cache.get(1));
135 EXPECT_STREQ("two", cache.get(2));
136 EXPECT_STREQ("three", cache.get(3));
137 EXPECT_EQ(3u, cache.size());
138 }
139
TEST_F(LruCacheTest,MaxCapacity)140 TEST_F(LruCacheTest, MaxCapacity) {
141 LruCache<SimpleKey, StringValue> cache(2);
142
143 cache.put(1, "one");
144 cache.put(2, "two");
145 cache.put(3, "three");
146 EXPECT_EQ(NULL, cache.get(1));
147 EXPECT_STREQ("two", cache.get(2));
148 EXPECT_STREQ("three", cache.get(3));
149 EXPECT_EQ(2u, cache.size());
150 }
151
TEST_F(LruCacheTest,RemoveLru)152 TEST_F(LruCacheTest, RemoveLru) {
153 LruCache<SimpleKey, StringValue> cache(100);
154
155 cache.put(1, "one");
156 cache.put(2, "two");
157 cache.put(3, "three");
158 cache.removeOldest();
159 EXPECT_EQ(NULL, cache.get(1));
160 EXPECT_STREQ("two", cache.get(2));
161 EXPECT_STREQ("three", cache.get(3));
162 EXPECT_EQ(2u, cache.size());
163 }
164
TEST_F(LruCacheTest,GetUpdatesLru)165 TEST_F(LruCacheTest, GetUpdatesLru) {
166 LruCache<SimpleKey, StringValue> cache(100);
167
168 cache.put(1, "one");
169 cache.put(2, "two");
170 cache.put(3, "three");
171 EXPECT_STREQ("one", cache.get(1));
172 cache.removeOldest();
173 EXPECT_STREQ("one", cache.get(1));
174 EXPECT_EQ(NULL, cache.get(2));
175 EXPECT_STREQ("three", cache.get(3));
176 EXPECT_EQ(2u, cache.size());
177 }
178
hash_int(int x)179 uint32_t hash_int(int x) {
180 return JenkinsHashWhiten(JenkinsHashMix(0, x));
181 }
182
TEST_F(LruCacheTest,StressTest)183 TEST_F(LruCacheTest, StressTest) {
184 const size_t kCacheSize = 512;
185 LruCache<SimpleKey, StringValue> cache(512);
186 const size_t kNumKeys = 16 * 1024;
187 const size_t kNumIters = 100000;
188 char* strings[kNumKeys];
189
190 for (size_t i = 0; i < kNumKeys; i++) {
191 strings[i] = (char *)malloc(16);
192 sprintf(strings[i], "%zu", i);
193 }
194
195 srandom(12345);
196 int hitCount = 0;
197 for (size_t i = 0; i < kNumIters; i++) {
198 int index = random() % kNumKeys;
199 uint32_t key = hash_int(index);
200 const char *val = cache.get(key);
201 if (val != NULL) {
202 EXPECT_EQ(strings[index], val);
203 hitCount++;
204 } else {
205 cache.put(key, strings[index]);
206 }
207 }
208 size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys;
209 EXPECT_LT(int(expectedHitCount * 0.9), hitCount);
210 EXPECT_GT(int(expectedHitCount * 1.1), hitCount);
211 EXPECT_EQ(kCacheSize, cache.size());
212
213 for (size_t i = 0; i < kNumKeys; i++) {
214 free((void *)strings[i]);
215 }
216 }
217
TEST_F(LruCacheTest,NoLeak)218 TEST_F(LruCacheTest, NoLeak) {
219 ComplexCache cache(100);
220
221 cache.put(ComplexKey(0), ComplexValue(0));
222 cache.put(ComplexKey(1), ComplexValue(1));
223 EXPECT_EQ(2, cache.size());
224 assertInstanceCount(2, 3); // the null value counts as an instance
225 }
226
TEST_F(LruCacheTest,Clear)227 TEST_F(LruCacheTest, Clear) {
228 ComplexCache cache(100);
229
230 cache.put(ComplexKey(0), ComplexValue(0));
231 cache.put(ComplexKey(1), ComplexValue(1));
232 EXPECT_EQ(2, cache.size());
233 assertInstanceCount(2, 3);
234 cache.clear();
235 assertInstanceCount(0, 1);
236 }
237
TEST_F(LruCacheTest,ClearNoDoubleFree)238 TEST_F(LruCacheTest, ClearNoDoubleFree) {
239 {
240 ComplexCache cache(100);
241
242 cache.put(ComplexKey(0), ComplexValue(0));
243 cache.put(ComplexKey(1), ComplexValue(1));
244 EXPECT_EQ(2, cache.size());
245 assertInstanceCount(2, 3);
246 cache.removeOldest();
247 cache.clear();
248 assertInstanceCount(0, 1);
249 }
250 assertInstanceCount(0, 0);
251 }
252
TEST_F(LruCacheTest,ClearReuseOk)253 TEST_F(LruCacheTest, ClearReuseOk) {
254 ComplexCache cache(100);
255
256 cache.put(ComplexKey(0), ComplexValue(0));
257 cache.put(ComplexKey(1), ComplexValue(1));
258 EXPECT_EQ(2, cache.size());
259 assertInstanceCount(2, 3);
260 cache.clear();
261 assertInstanceCount(0, 1);
262 cache.put(ComplexKey(0), ComplexValue(0));
263 cache.put(ComplexKey(1), ComplexValue(1));
264 EXPECT_EQ(2, cache.size());
265 assertInstanceCount(2, 3);
266 }
267
TEST_F(LruCacheTest,Callback)268 TEST_F(LruCacheTest, Callback) {
269 LruCache<SimpleKey, StringValue> cache(100);
270 EntryRemovedCallback callback;
271 cache.setOnEntryRemovedListener(&callback);
272
273 cache.put(1, "one");
274 cache.put(2, "two");
275 cache.put(3, "three");
276 EXPECT_EQ(3, cache.size());
277 cache.removeOldest();
278 EXPECT_EQ(1, callback.callbackCount);
279 EXPECT_EQ(1, callback.lastKey);
280 EXPECT_STREQ("one", callback.lastValue);
281 }
282
TEST_F(LruCacheTest,CallbackOnClear)283 TEST_F(LruCacheTest, CallbackOnClear) {
284 LruCache<SimpleKey, StringValue> cache(100);
285 EntryRemovedCallback callback;
286 cache.setOnEntryRemovedListener(&callback);
287
288 cache.put(1, "one");
289 cache.put(2, "two");
290 cache.put(3, "three");
291 EXPECT_EQ(3, cache.size());
292 cache.clear();
293 EXPECT_EQ(3, callback.callbackCount);
294 }
295
296 }
297