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 android {
24
25 typedef int SimpleKey;
26 typedef const char* StringValue;
27
28 struct ComplexKey {
29 int k;
30
ComplexKeyandroid::ComplexKey31 explicit ComplexKey(int k) : k(k) {
32 instanceCount += 1;
33 }
34
ComplexKeyandroid::ComplexKey35 ComplexKey(const ComplexKey& other) : k(other.k) {
36 instanceCount += 1;
37 }
38
~ComplexKeyandroid::ComplexKey39 ~ComplexKey() {
40 instanceCount -= 1;
41 }
42
operator ==android::ComplexKey43 bool operator ==(const ComplexKey& other) const {
44 return k == other.k;
45 }
46
operator !=android::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
hash_type(const ComplexKey & value)56 template<> inline hash_t hash_type(const ComplexKey& value) {
57 return hash_type(value.k);
58 }
59
60 struct ComplexValue {
61 int v;
62
ComplexValueandroid::ComplexValue63 explicit ComplexValue(int v) : v(v) {
64 instanceCount += 1;
65 }
66
ComplexValueandroid::ComplexValue67 ComplexValue(const ComplexValue& other) : v(other.v) {
68 instanceCount += 1;
69 }
70
~ComplexValueandroid::ComplexValue71 ~ComplexValue() {
72 instanceCount -= 1;
73 }
74
75 static ssize_t instanceCount;
76 };
77
78 ssize_t ComplexValue::instanceCount = 0;
79
80 typedef LruCache<ComplexKey, ComplexValue> ComplexCache;
81
82 class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
83 public:
EntryRemovedCallback()84 EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
~EntryRemovedCallback()85 ~EntryRemovedCallback() {}
operator ()(SimpleKey & k,StringValue & v)86 void operator()(SimpleKey& k, StringValue& v) {
87 callbackCount += 1;
88 lastKey = k;
89 lastValue = v;
90 }
91 ssize_t callbackCount;
92 SimpleKey lastKey;
93 StringValue lastValue;
94 };
95
96 class LruCacheTest : public testing::Test {
97 protected:
SetUp()98 virtual void SetUp() {
99 ComplexKey::instanceCount = 0;
100 ComplexValue::instanceCount = 0;
101 }
102
TearDown()103 virtual void TearDown() {
104 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
105 }
106
assertInstanceCount(ssize_t keys,ssize_t values)107 void assertInstanceCount(ssize_t keys, ssize_t values) {
108 if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
109 FAIL() << "Expected " << keys << " keys and " << values << " values "
110 "but there were actually " << ComplexKey::instanceCount << " keys and "
111 << ComplexValue::instanceCount << " values";
112 }
113 }
114 };
115
TEST_F(LruCacheTest,Empty)116 TEST_F(LruCacheTest, Empty) {
117 LruCache<SimpleKey, StringValue> cache(100);
118
119 EXPECT_EQ(NULL, cache.get(0));
120 EXPECT_EQ(0u, cache.size());
121 }
122
TEST_F(LruCacheTest,Simple)123 TEST_F(LruCacheTest, Simple) {
124 LruCache<SimpleKey, StringValue> cache(100);
125
126 cache.put(1, "one");
127 cache.put(2, "two");
128 cache.put(3, "three");
129 EXPECT_STREQ("one", cache.get(1));
130 EXPECT_STREQ("two", cache.get(2));
131 EXPECT_STREQ("three", cache.get(3));
132 EXPECT_EQ(3u, cache.size());
133 }
134
TEST_F(LruCacheTest,MaxCapacity)135 TEST_F(LruCacheTest, MaxCapacity) {
136 LruCache<SimpleKey, StringValue> cache(2);
137
138 cache.put(1, "one");
139 cache.put(2, "two");
140 cache.put(3, "three");
141 EXPECT_EQ(NULL, cache.get(1));
142 EXPECT_STREQ("two", cache.get(2));
143 EXPECT_STREQ("three", cache.get(3));
144 EXPECT_EQ(2u, cache.size());
145 }
146
TEST_F(LruCacheTest,RemoveLru)147 TEST_F(LruCacheTest, RemoveLru) {
148 LruCache<SimpleKey, StringValue> cache(100);
149
150 cache.put(1, "one");
151 cache.put(2, "two");
152 cache.put(3, "three");
153 cache.removeOldest();
154 EXPECT_EQ(NULL, cache.get(1));
155 EXPECT_STREQ("two", cache.get(2));
156 EXPECT_STREQ("three", cache.get(3));
157 EXPECT_EQ(2u, cache.size());
158 }
159
TEST_F(LruCacheTest,GetUpdatesLru)160 TEST_F(LruCacheTest, GetUpdatesLru) {
161 LruCache<SimpleKey, StringValue> cache(100);
162
163 cache.put(1, "one");
164 cache.put(2, "two");
165 cache.put(3, "three");
166 EXPECT_STREQ("one", cache.get(1));
167 cache.removeOldest();
168 EXPECT_STREQ("one", cache.get(1));
169 EXPECT_EQ(NULL, cache.get(2));
170 EXPECT_STREQ("three", cache.get(3));
171 EXPECT_EQ(2u, cache.size());
172 }
173
hash_int(int x)174 uint32_t hash_int(int x) {
175 return JenkinsHashWhiten(JenkinsHashMix(0, x));
176 }
177
TEST_F(LruCacheTest,StressTest)178 TEST_F(LruCacheTest, StressTest) {
179 const size_t kCacheSize = 512;
180 LruCache<SimpleKey, StringValue> cache(512);
181 const size_t kNumKeys = 16 * 1024;
182 const size_t kNumIters = 100000;
183 char* strings[kNumKeys];
184
185 for (size_t i = 0; i < kNumKeys; i++) {
186 strings[i] = (char *)malloc(16);
187 sprintf(strings[i], "%d", i);
188 }
189
190 srandom(12345);
191 int hitCount = 0;
192 for (size_t i = 0; i < kNumIters; i++) {
193 int index = random() % kNumKeys;
194 uint32_t key = hash_int(index);
195 const char *val = cache.get(key);
196 if (val != NULL) {
197 EXPECT_EQ(strings[index], val);
198 hitCount++;
199 } else {
200 cache.put(key, strings[index]);
201 }
202 }
203 size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys;
204 EXPECT_LT(int(expectedHitCount * 0.9), hitCount);
205 EXPECT_GT(int(expectedHitCount * 1.1), hitCount);
206 EXPECT_EQ(kCacheSize, cache.size());
207
208 for (size_t i = 0; i < kNumKeys; i++) {
209 free((void *)strings[i]);
210 }
211 }
212
TEST_F(LruCacheTest,NoLeak)213 TEST_F(LruCacheTest, NoLeak) {
214 ComplexCache cache(100);
215
216 cache.put(ComplexKey(0), ComplexValue(0));
217 cache.put(ComplexKey(1), ComplexValue(1));
218 EXPECT_EQ(2, cache.size());
219 assertInstanceCount(2, 3); // the null value counts as an instance
220 }
221
TEST_F(LruCacheTest,Clear)222 TEST_F(LruCacheTest, Clear) {
223 ComplexCache cache(100);
224
225 cache.put(ComplexKey(0), ComplexValue(0));
226 cache.put(ComplexKey(1), ComplexValue(1));
227 EXPECT_EQ(2, cache.size());
228 assertInstanceCount(2, 3);
229 cache.clear();
230 assertInstanceCount(0, 1);
231 }
232
TEST_F(LruCacheTest,ClearNoDoubleFree)233 TEST_F(LruCacheTest, ClearNoDoubleFree) {
234 {
235 ComplexCache cache(100);
236
237 cache.put(ComplexKey(0), ComplexValue(0));
238 cache.put(ComplexKey(1), ComplexValue(1));
239 EXPECT_EQ(2, cache.size());
240 assertInstanceCount(2, 3);
241 cache.removeOldest();
242 cache.clear();
243 assertInstanceCount(0, 1);
244 }
245 assertInstanceCount(0, 0);
246 }
247
TEST_F(LruCacheTest,ClearReuseOk)248 TEST_F(LruCacheTest, ClearReuseOk) {
249 ComplexCache cache(100);
250
251 cache.put(ComplexKey(0), ComplexValue(0));
252 cache.put(ComplexKey(1), ComplexValue(1));
253 EXPECT_EQ(2, cache.size());
254 assertInstanceCount(2, 3);
255 cache.clear();
256 assertInstanceCount(0, 1);
257 cache.put(ComplexKey(0), ComplexValue(0));
258 cache.put(ComplexKey(1), ComplexValue(1));
259 EXPECT_EQ(2, cache.size());
260 assertInstanceCount(2, 3);
261 }
262
TEST_F(LruCacheTest,Callback)263 TEST_F(LruCacheTest, Callback) {
264 LruCache<SimpleKey, StringValue> cache(100);
265 EntryRemovedCallback callback;
266 cache.setOnEntryRemovedListener(&callback);
267
268 cache.put(1, "one");
269 cache.put(2, "two");
270 cache.put(3, "three");
271 EXPECT_EQ(3, cache.size());
272 cache.removeOldest();
273 EXPECT_EQ(1, callback.callbackCount);
274 EXPECT_EQ(1, callback.lastKey);
275 EXPECT_STREQ("one", callback.lastValue);
276 }
277
TEST_F(LruCacheTest,CallbackOnClear)278 TEST_F(LruCacheTest, CallbackOnClear) {
279 LruCache<SimpleKey, StringValue> cache(100);
280 EntryRemovedCallback callback;
281 cache.setOnEntryRemovedListener(&callback);
282
283 cache.put(1, "one");
284 cache.put(2, "two");
285 cache.put(3, "three");
286 EXPECT_EQ(3, cache.size());
287 cache.clear();
288 EXPECT_EQ(3, callback.callbackCount);
289 }
290
291 }
292