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