LruCache_test.cpp revision cdc1cfb3e51f3caddc1f290b46dc789c036f22ed 
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
23namespace android {
24
25typedef int SimpleKey;
26typedef const char* StringValue;
27
28struct ComplexKey {
29    int k;
30
31    explicit ComplexKey(int k) : k(k) {
32        instanceCount += 1;
33    }
34
35    ComplexKey(const ComplexKey& other) : k(other.k) {
36        instanceCount += 1;
37    }
38
39    ~ComplexKey() {
40        instanceCount -= 1;
41    }
42
43    bool operator ==(const ComplexKey& other) const {
44        return k == other.k;
45    }
46
47    bool operator !=(const ComplexKey& other) const {
48        return k != other.k;
49    }
50
51    static ssize_t instanceCount;
52};
53
54ssize_t ComplexKey::instanceCount = 0;
55
56template<> inline hash_t hash_type(const ComplexKey& value) {
57    return hash_type(value.k);
58}
59
60struct ComplexValue {
61    int v;
62
63    explicit ComplexValue(int v) : v(v) {
64        instanceCount += 1;
65    }
66
67    ComplexValue(const ComplexValue& other) : v(other.v) {
68        instanceCount += 1;
69    }
70
71    ~ComplexValue() {
72        instanceCount -= 1;
73    }
74
75    static ssize_t instanceCount;
76};
77
78ssize_t ComplexValue::instanceCount = 0;
79
80typedef LruCache<ComplexKey, ComplexValue> ComplexCache;
81
82class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
83public:
84    EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
85    ~EntryRemovedCallback() {}
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
96class LruCacheTest : public testing::Test {
97protected:
98    virtual void SetUp() {
99        ComplexKey::instanceCount = 0;
100        ComplexValue::instanceCount = 0;
101    }
102
103    virtual void TearDown() {
104        ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
105    }
106
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
116TEST_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
123TEST_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
135TEST_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
147TEST_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
160TEST_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
174uint32_t hash_int(int x) {
175    return JenkinsHashWhiten(JenkinsHashMix(0, x));
176}
177
178TEST_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], "%zu", 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
213TEST_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
222TEST_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
233TEST_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
248TEST_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
263TEST_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
278TEST_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