LruCacheTest.java revision 56b6ad3e28f9f86fb3186c96ddd8754e190afdf0 
1/*
2 * Copyright (C) 2011 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
17package android.util;
18
19import java.util.ArrayList;
20import java.util.Arrays;
21import java.util.List;
22import java.util.Map;
23import junit.framework.TestCase;
24
25public final class LruCacheTest extends TestCase {
26    private int expectedCreateCount;
27    private int expectedPutCount;
28    private int expectedHitCount;
29    private int expectedMissCount;
30    private int expectedEvictionCount;
31
32    public void testStatistics() {
33        LruCache<String, String> cache = new LruCache<String, String>(3);
34        assertStatistics(cache);
35
36        assertEquals(null, cache.put("a", "A"));
37        expectedPutCount++;
38        assertStatistics(cache);
39        assertHit(cache, "a", "A");
40        assertSnapshot(cache, "a", "A");
41
42        assertEquals(null, cache.put("b", "B"));
43        expectedPutCount++;
44        assertStatistics(cache);
45        assertHit(cache, "a", "A");
46        assertHit(cache, "b", "B");
47        assertSnapshot(cache, "a", "A", "b", "B");
48
49        assertEquals(null, cache.put("c", "C"));
50        expectedPutCount++;
51        assertStatistics(cache);
52        assertHit(cache, "a", "A");
53        assertHit(cache, "b", "B");
54        assertHit(cache, "c", "C");
55        assertSnapshot(cache, "a", "A", "b", "B", "c", "C");
56
57        assertEquals(null, cache.put("d", "D"));
58        expectedPutCount++;
59        expectedEvictionCount++; // a should have been evicted
60        assertStatistics(cache);
61        assertMiss(cache, "a");
62        assertHit(cache, "b", "B");
63        assertHit(cache, "c", "C");
64        assertHit(cache, "d", "D");
65        assertHit(cache, "b", "B");
66        assertHit(cache, "c", "C");
67        assertSnapshot(cache, "d", "D", "b", "B", "c", "C");
68
69        assertEquals(null, cache.put("e", "E"));
70        expectedPutCount++;
71        expectedEvictionCount++; // d should have been evicted
72        assertStatistics(cache);
73        assertMiss(cache, "d");
74        assertMiss(cache, "a");
75        assertHit(cache, "e", "E");
76        assertHit(cache, "b", "B");
77        assertHit(cache, "c", "C");
78        assertSnapshot(cache, "e", "E", "b", "B", "c", "C");
79    }
80
81    public void testStatisticsWithCreate() {
82        LruCache<String, String> cache = newCreatingCache();
83        assertStatistics(cache);
84
85        assertCreated(cache, "aa", "created-aa");
86        assertHit(cache, "aa", "created-aa");
87        assertSnapshot(cache, "aa", "created-aa");
88
89        assertCreated(cache, "bb", "created-bb");
90        assertMiss(cache, "c");
91        assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb");
92
93        assertCreated(cache, "cc", "created-cc");
94        assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb", "cc", "created-cc");
95
96        expectedEvictionCount++; // aa will be evicted
97        assertCreated(cache, "dd", "created-dd");
98        assertSnapshot(cache, "bb", "created-bb",  "cc", "created-cc", "dd", "created-dd");
99
100        expectedEvictionCount++; // bb will be evicted
101        assertCreated(cache, "aa", "created-aa");
102        assertSnapshot(cache, "cc", "created-cc", "dd", "created-dd", "aa", "created-aa");
103    }
104
105    public void testCreateOnCacheMiss() {
106        LruCache<String, String> cache = newCreatingCache();
107        String created = cache.get("aa");
108        assertEquals("created-aa", created);
109    }
110
111    public void testNoCreateOnCacheHit() {
112        LruCache<String, String> cache = newCreatingCache();
113        cache.put("aa", "put-aa");
114        assertEquals("put-aa", cache.get("aa"));
115    }
116
117    public void testConstructorDoesNotAllowZeroCacheSize() {
118        try {
119            new LruCache<String, String>(0);
120            fail();
121        } catch (IllegalArgumentException expected) {
122        }
123    }
124
125    public void testCannotPutNullKey() {
126        LruCache<String, String> cache = new LruCache<String, String>(3);
127        try {
128            cache.put(null, "A");
129            fail();
130        } catch (NullPointerException expected) {
131        }
132    }
133
134    public void testCannotPutNullValue() {
135        LruCache<String, String> cache = new LruCache<String, String>(3);
136        try {
137            cache.put("a", null);
138            fail();
139        } catch (NullPointerException expected) {
140        }
141    }
142
143    public void testToString() {
144        LruCache<String, String> cache = new LruCache<String, String>(3);
145        assertEquals("LruCache[maxSize=3,hits=0,misses=0,hitRate=0%]", cache.toString());
146
147        cache.put("a", "A");
148        cache.put("b", "B");
149        cache.put("c", "C");
150        cache.put("d", "D");
151
152        cache.get("a"); // miss
153        cache.get("b"); // hit
154        cache.get("c"); // hit
155        cache.get("d"); // hit
156        cache.get("e"); // miss
157
158        assertEquals("LruCache[maxSize=3,hits=3,misses=2,hitRate=60%]", cache.toString());
159    }
160
161    public void testEvictionWithSingletonCache() {
162        LruCache<String, String> cache = new LruCache<String, String>(1);
163        cache.put("a", "A");
164        cache.put("b", "B");
165        assertSnapshot(cache, "b", "B");
166    }
167
168    public void testEntryEvictedWhenFull() {
169        List<String> expectedEvictionLog = new ArrayList<String>();
170        final List<String> evictionLog = new ArrayList<String>();
171        LruCache<String, String> cache = new LruCache<String, String>(3) {
172            @Override protected void entryEvicted(String key, String value) {
173                evictionLog.add(key + "=" + value);
174            }
175        };
176
177        cache.put("a", "A");
178        cache.put("b", "B");
179        cache.put("c", "C");
180        assertEquals(expectedEvictionLog, evictionLog);
181
182        cache.put("d", "D");
183        expectedEvictionLog.add("a=A");
184        assertEquals(expectedEvictionLog, evictionLog);
185    }
186
187    /**
188     * Replacing the value for a key doesn't cause an eviction but it does bring
189     * the replaced entry to the front of the queue.
190     */
191    public void testPutDoesNotCauseEviction() {
192        final List<String> evictionLog = new ArrayList<String>();
193        List<String> expectedEvictionLog = new ArrayList<String>();
194        LruCache<String, String> cache = new LruCache<String, String>(3) {
195            @Override protected void entryEvicted(String key, String value) {
196                evictionLog.add(key + "=" + value);
197            }
198        };
199
200        cache.put("a", "A");
201        cache.put("b", "B");
202        cache.put("c", "C");
203        cache.put("b", "B2");
204        assertEquals(expectedEvictionLog, evictionLog);
205        assertSnapshot(cache, "a", "A", "c", "C", "b", "B2");
206    }
207
208    public void testCustomSizesImpactsSize() {
209        LruCache<String, String> cache = new LruCache<String, String>(10) {
210            @Override protected int sizeOf(String key, String value) {
211                return key.length() + value.length();
212            }
213        };
214
215        assertEquals(0, cache.size());
216        cache.put("a", "AA");
217        assertEquals(3, cache.size());
218        cache.put("b", "BBBB");
219        assertEquals(8, cache.size());
220        cache.put("a", "");
221        assertEquals(6, cache.size());
222    }
223
224    public void testEvictionWithCustomSizes() {
225        LruCache<String, String> cache = new LruCache<String, String>(4) {
226            @Override protected int sizeOf(String key, String value) {
227                return value.length();
228            }
229        };
230
231        cache.put("a", "AAAA");
232        assertSnapshot(cache, "a", "AAAA");
233        cache.put("b", "BBBB"); // should evict a
234        assertSnapshot(cache, "b", "BBBB");
235        cache.put("c", "CC"); // should evict b
236        assertSnapshot(cache, "c", "CC");
237        cache.put("d", "DD");
238        assertSnapshot(cache, "c", "CC", "d", "DD");
239        cache.put("e", "E"); // should evict c
240        assertSnapshot(cache, "d", "DD", "e", "E");
241        cache.put("f", "F");
242        assertSnapshot(cache, "d", "DD", "e", "E", "f", "F");
243        cache.put("g", "G"); // should evict d
244        assertSnapshot(cache, "e", "E", "f", "F", "g", "G");
245        cache.put("h", "H");
246        assertSnapshot(cache, "e", "E", "f", "F", "g", "G", "h", "H");
247        cache.put("i", "III"); // should evict e, f, and g
248        assertSnapshot(cache, "h", "H", "i", "III");
249        cache.put("j", "JJJ"); // should evict h and i
250        assertSnapshot(cache, "j", "JJJ");
251    }
252
253    public void testEvictionThrowsWhenSizesAreInconsistent() {
254        LruCache<String, int[]> cache = new LruCache<String, int[]>(4) {
255            @Override protected int sizeOf(String key, int[] value) {
256                return value[0];
257            }
258        };
259
260        int[] a = { 4 };
261        cache.put("a", a);
262
263        // get the cache size out of sync
264        a[0] = 1;
265        assertEquals(4, cache.size());
266
267        // evict something
268        try {
269            cache.put("b", new int[] { 2 });
270            fail();
271        } catch (IllegalStateException expected) {
272        }
273    }
274
275    public void testEvictionThrowsWhenSizesAreNegative() {
276        LruCache<String, String> cache = new LruCache<String, String>(4) {
277            @Override protected int sizeOf(String key, String value) {
278                return -1;
279            }
280        };
281
282        try {
283            cache.put("a", "A");
284            fail();
285        } catch (IllegalStateException expected) {
286        }
287    }
288
289    /**
290     * Naive caches evict at most one element at a time. This is problematic
291     * because evicting a small element may be insufficient to make room for a
292     * large element.
293     */
294    public void testDifferentElementSizes() {
295        LruCache<String, String> cache = new LruCache<String, String>(10) {
296            @Override protected int sizeOf(String key, String value) {
297                return value.length();
298            }
299        };
300
301        cache.put("a", "1");
302        cache.put("b", "12345678");
303        cache.put("c", "1");
304        assertSnapshot(cache, "a", "1", "b", "12345678", "c", "1");
305        cache.put("d", "12345678"); // should evict a and b
306        assertSnapshot(cache, "c", "1", "d", "12345678");
307        cache.put("e", "12345678"); // should evict c and d
308        assertSnapshot(cache, "e", "12345678");
309    }
310
311    public void testEvictAll() {
312        final List<String> evictionLog = new ArrayList<String>();
313        LruCache<String, String> cache = new LruCache<String, String>(10) {
314            @Override protected void entryEvicted(String key, String value) {
315                evictionLog.add(key + "=" + value);
316            }
317        };
318
319        cache.put("a", "A");
320        cache.put("b", "B");
321        cache.put("c", "C");
322        cache.evictAll();
323        assertEquals(0, cache.size());
324        assertEquals(Arrays.asList("a=A", "b=B", "c=C"), evictionLog);
325    }
326
327    public void testEvictAllEvictsSizeZeroElements() {
328        LruCache<String, String> cache = new LruCache<String, String>(10) {
329            @Override protected int sizeOf(String key, String value) {
330                return 0;
331            }
332        };
333
334        cache.put("a", "A");
335        cache.put("b", "B");
336        cache.evictAll();
337        assertSnapshot(cache);
338    }
339
340    public void testRemoveDoesNotCallEntryEvicted() {
341        LruCache<String, String> cache = new LruCache<String, String>(10) {
342            @Override protected void entryEvicted(String key, String value) {
343                fail();
344            }
345        };
346        cache.put("a", "A");
347        assertEquals("A", cache.remove("a"));
348    }
349
350    public void testRemoveWithCustomSizes() {
351        LruCache<String, String> cache = new LruCache<String, String>(10) {
352            @Override protected int sizeOf(String key, String value) {
353                return value.length();
354            }
355        };
356        cache.put("a", "123456");
357        cache.put("b", "1234");
358        cache.remove("a");
359        assertEquals(4, cache.size());
360    }
361
362    public void testRemoveAbsentElement() {
363        LruCache<String, String> cache = new LruCache<String, String>(10);
364        cache.put("a", "A");
365        cache.put("b", "B");
366        assertEquals(null, cache.remove("c"));
367        assertEquals(2, cache.size());
368    }
369
370    public void testRemoveNullThrows() {
371        LruCache<String, String> cache = new LruCache<String, String>(10);
372        try {
373            cache.remove(null);
374            fail();
375        } catch (NullPointerException expected) {
376        }
377    }
378
379    private LruCache<String, String> newCreatingCache() {
380        return new LruCache<String, String>(3) {
381            @Override protected String create(String key) {
382                return (key.length() > 1) ? ("created-" + key) : null;
383            }
384        };
385    }
386
387    private void assertHit(LruCache<String, String> cache, String key, String value) {
388        assertEquals(value, cache.get(key));
389        expectedHitCount++;
390        assertStatistics(cache);
391    }
392
393    private void assertMiss(LruCache<String, String> cache, String key) {
394        assertEquals(null, cache.get(key));
395        expectedMissCount++;
396        assertStatistics(cache);
397    }
398
399    private void assertCreated(LruCache<String, String> cache, String key, String value) {
400        assertEquals(value, cache.get(key));
401        expectedMissCount++;
402        expectedCreateCount++;
403        assertStatistics(cache);
404    }
405
406    private void assertStatistics(LruCache<?, ?> cache) {
407        assertEquals("create count", expectedCreateCount, cache.createCount());
408        assertEquals("put count", expectedPutCount, cache.putCount());
409        assertEquals("hit count", expectedHitCount, cache.hitCount());
410        assertEquals("miss count", expectedMissCount, cache.missCount());
411        assertEquals("eviction count", expectedEvictionCount, cache.evictionCount());
412    }
413
414    private <T> void assertSnapshot(LruCache<T, T> cache, T... keysAndValues) {
415        List<T> actualKeysAndValues = new ArrayList<T>();
416        for (Map.Entry<T, T> entry : cache.snapshot().entrySet()) {
417            actualKeysAndValues.add(entry.getKey());
418            actualKeysAndValues.add(entry.getValue());
419        }
420
421        // assert using lists because order is important for LRUs
422        assertEquals(Arrays.asList(keysAndValues), actualKeysAndValues);
423    }
424}
425