android/util/LruCacheTest.java

/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package android.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import junit.framework.TestCase;

public final class LruCacheTest extends TestCase {
    private int expectedCreateCount;
    private int expectedPutCount;
    private int expectedHitCount;
    private int expectedMissCount;
    private int expectedEvictionCount;

    public void testStatistics() {
        LruCache<String, String> cache = new LruCache<String, String>(3);
        assertStatistics(cache);

        assertEquals(null, cache.put("a", "A"));
        expectedPutCount++;
        assertStatistics(cache);
        assertHit(cache, "a", "A");
        assertSnapshot(cache, "a", "A");

        assertEquals(null, cache.put("b", "B"));
        expectedPutCount++;
        assertStatistics(cache);
        assertHit(cache, "a", "A");
        assertHit(cache, "b", "B");
        assertSnapshot(cache, "a", "A", "b", "B");

        assertEquals(null, cache.put("c", "C"));
        expectedPutCount++;
        assertStatistics(cache);
        assertHit(cache, "a", "A");
        assertHit(cache, "b", "B");
        assertHit(cache, "c", "C");
        assertSnapshot(cache, "a", "A", "b", "B", "c", "C");

        assertEquals(null, cache.put("d", "D"));
        expectedPutCount++;
        expectedEvictionCount++; // a should have been evicted
        assertStatistics(cache);
        assertMiss(cache, "a");
        assertHit(cache, "b", "B");
        assertHit(cache, "c", "C");
        assertHit(cache, "d", "D");
        assertHit(cache, "b", "B");
        assertHit(cache, "c", "C");
        assertSnapshot(cache, "d", "D", "b", "B", "c", "C");

        assertEquals(null, cache.put("e", "E"));
        expectedPutCount++;
        expectedEvictionCount++; // d should have been evicted
        assertStatistics(cache);
        assertMiss(cache, "d");
        assertMiss(cache, "a");
        assertHit(cache, "e", "E");
        assertHit(cache, "b", "B");
        assertHit(cache, "c", "C");
        assertSnapshot(cache, "e", "E", "b", "B", "c", "C");
    }

    public void testStatisticsWithCreate() {
        LruCache<String, String> cache = newCreatingCache();
        assertStatistics(cache);

        assertCreated(cache, "aa", "created-aa");
        assertHit(cache, "aa", "created-aa");
        assertSnapshot(cache, "aa", "created-aa");

        assertCreated(cache, "bb", "created-bb");
        assertMiss(cache, "c");
        assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb");

        assertCreated(cache, "cc", "created-cc");
        assertSnapshot(cache, "aa", "created-aa", "bb", "created-bb", "cc", "created-cc");

        expectedEvictionCount++; // aa will be evicted
        assertCreated(cache, "dd", "created-dd");
        assertSnapshot(cache, "bb", "created-bb",  "cc", "created-cc", "dd", "created-dd");

        expectedEvictionCount++; // bb will be evicted
        assertCreated(cache, "aa", "created-aa");
        assertSnapshot(cache, "cc", "created-cc", "dd", "created-dd", "aa", "created-aa");
    }

    public void testCreateOnCacheMiss() {
        LruCache<String, String> cache = newCreatingCache();
        String created = cache.get("aa");
        assertEquals("created-aa", created);
    }

    public void testNoCreateOnCacheHit() {
        LruCache<String, String> cache = newCreatingCache();
        cache.put("aa", "put-aa");
        assertEquals("put-aa", cache.get("aa"));
    }

    public void testConstructorDoesNotAllowZeroCacheSize() {
        try {
            new LruCache<String, String>(0);
            fail();
        } catch (IllegalArgumentException expected) {
        }
    }

    public void testCannotPutNullKey() {
        LruCache<String, String> cache = new LruCache<String, String>(3);
        try {
            cache.put(null, "A");
            fail();
        } catch (NullPointerException expected) {
        }
    }

    public void testCannotPutNullValue() {
        LruCache<String, String> cache = new LruCache<String, String>(3);
        try {
            cache.put("a", null);
            fail();
        } catch (NullPointerException expected) {
        }
    }

    public void testToString() {
        LruCache<String, String> cache = new LruCache<String, String>(3);
        assertEquals("LruCache[maxSize=3,hits=0,misses=0,hitRate=0%]", cache.toString());

        cache.put("a", "A");
        cache.put("b", "B");
        cache.put("c", "C");
        cache.put("d", "D");

        cache.get("a"); // miss
        cache.get("b"); // hit
        cache.get("c"); // hit
        cache.get("d"); // hit
        cache.get("e"); // miss

        assertEquals("LruCache[maxSize=3,hits=3,misses=2,hitRate=60%]", cache.toString());
    }

    public void testEvictionWithSingletonCache() {
        LruCache<String, String> cache = new LruCache<String, String>(1);
        cache.put("a", "A");
        cache.put("b", "B");
        assertSnapshot(cache, "b", "B");
    }

    public void testEntryEvictedWhenFull() {
        List<String> log = new ArrayList<String>();
        LruCache<String, String> cache = newRemovalLogCache(log);

        cache.put("a", "A");
        cache.put("b", "B");
        cache.put("c", "C");
        assertEquals(Collections.<String>emptyList(), log);

        cache.put("d", "D");
        assertEquals(Arrays.asList("a=A"), log);
    }

    /**
     * Replacing the value for a key doesn't cause an eviction but it does bring
     * the replaced entry to the front of the queue.
     */
    public void testPutCauseEviction() {
        List<String> log = new ArrayList<String>();
        LruCache<String, String> cache = newRemovalLogCache(log);

        cache.put("a", "A");
        cache.put("b", "B");
        cache.put("c", "C");
        cache.put("b", "B2");
        assertEquals(Arrays.asList("b=B>B2"), log);
        assertSnapshot(cache, "a", "A", "c", "C", "b", "B2");
    }

    public void testCustomSizesImpactsSize() {
        LruCache<String, String> cache = new LruCache<String, String>(10) {
            @Override protected int sizeOf(String key, String value) {
                return key.length() + value.length();
            }
        };

        assertEquals(0, cache.size());
        cache.put("a", "AA");
        assertEquals(3, cache.size());
        cache.put("b", "BBBB");
        assertEquals(8, cache.size());
        cache.put("a", "");
        assertEquals(6, cache.size());
    }

    public void testEvictionWithCustomSizes() {
        LruCache<String, String> cache = new LruCache<String, String>(4) {
            @Override protected int sizeOf(String key, String value) {
                return value.length();
            }
        };

        cache.put("a", "AAAA");
        assertSnapshot(cache, "a", "AAAA");
        cache.put("b", "BBBB"); // should evict a
        assertSnapshot(cache, "b", "BBBB");
        cache.put("c", "CC"); // should evict b
        assertSnapshot(cache, "c", "CC");
        cache.put("d", "DD");
        assertSnapshot(cache, "c", "CC", "d", "DD");
        cache.put("e", "E"); // should evict c
        assertSnapshot(cache, "d", "DD", "e", "E");
        cache.put("f", "F");
        assertSnapshot(cache, "d", "DD", "e", "E", "f", "F");
        cache.put("g", "G"); // should evict d
        assertSnapshot(cache, "e", "E", "f", "F", "g", "G");
        cache.put("h", "H");
        assertSnapshot(cache, "e", "E", "f", "F", "g", "G", "h", "H");
        cache.put("i", "III"); // should evict e, f, and g
        assertSnapshot(cache, "h", "H", "i", "III");
        cache.put("j", "JJJ"); // should evict h and i
        assertSnapshot(cache, "j", "JJJ");
    }

    public void testEvictionThrowsWhenSizesAreInconsistent() {
        LruCache<String, int[]> cache = new LruCache<String, int[]>(4) {
            @Override protected int sizeOf(String key, int[] value) {
                return value[0];
            }
        };

        int[] a = { 4 };
        cache.put("a", a);

        // get the cache size out of sync
        a[0] = 1;
        assertEquals(4, cache.size());

        // evict something
        try {
            cache.put("b", new int[] { 2 });
            fail();
        } catch (IllegalStateException expected) {
        }
    }

    public void testEvictionThrowsWhenSizesAreNegative() {
        LruCache<String, String> cache = new LruCache<String, String>(4) {
            @Override protected int sizeOf(String key, String value) {
                return -1;
            }
        };

        try {
            cache.put("a", "A");
            fail();
        } catch (IllegalStateException expected) {
        }
    }

    /**
     * Naive caches evict at most one element at a time. This is problematic
     * because evicting a small element may be insufficient to make room for a
     * large element.
     */
    public void testDifferentElementSizes() {
        LruCache<String, String> cache = new LruCache<String, String>(10) {
            @Override protected int sizeOf(String key, String value) {
                return value.length();
            }
        };

        cache.put("a", "1");
        cache.put("b", "12345678");
        cache.put("c", "1");
        assertSnapshot(cache, "a", "1", "b", "12345678", "c", "1");
        cache.put("d", "12345678"); // should evict a and b
        assertSnapshot(cache, "c", "1", "d", "12345678");
        cache.put("e", "12345678"); // should evict c and d
        assertSnapshot(cache, "e", "12345678");
    }

    public void testEvictAll() {
        List<String> log = new ArrayList<String>();
        LruCache<String, String> cache = newRemovalLogCache(log);
        cache.put("a", "A");
        cache.put("b", "B");
        cache.put("c", "C");
        cache.evictAll();
        assertEquals(0, cache.size());
        assertEquals(Arrays.asList("a=A", "b=B", "c=C"), log);
    }

    public void testEvictAllEvictsSizeZeroElements() {
        LruCache<String, String> cache = new LruCache<String, String>(10) {
            @Override protected int sizeOf(String key, String value) {
                return 0;
            }
        };

        cache.put("a", "A");
        cache.put("b", "B");
        cache.evictAll();
        assertSnapshot(cache);
    }

    public void testRemoveWithCustomSizes() {
        LruCache<String, String> cache = new LruCache<String, String>(10) {
            @Override protected int sizeOf(String key, String value) {
                return value.length();
            }
        };
        cache.put("a", "123456");
        cache.put("b", "1234");
        cache.remove("a");
        assertEquals(4, cache.size());
    }

    public void testRemoveAbsentElement() {
        LruCache<String, String> cache = new LruCache<String, String>(10);
        cache.put("a", "A");
        cache.put("b", "B");
        assertEquals(null, cache.remove("c"));
        assertEquals(2, cache.size());
    }

    public void testRemoveNullThrows() {
        LruCache<String, String> cache = new LruCache<String, String>(10);
        try {
            cache.remove(null);
            fail();
        } catch (NullPointerException expected) {
        }
    }

    public void testRemoveCallsEntryRemoved() {
        List<String> log = new ArrayList<String>();
        LruCache<String, String> cache = newRemovalLogCache(log);
        cache.put("a", "A");
        cache.remove("a");
        assertEquals(Arrays.asList("a=A>null"), log);
    }

    public void testPutCallsEntryRemoved() {
        List<String> log = new ArrayList<String>();
        LruCache<String, String> cache = newRemovalLogCache(log);
        cache.put("a", "A");
        cache.put("a", "A2");
        assertEquals(Arrays.asList("a=A>A2"), log);
    }

    public void testEntryRemovedIsCalledWithoutSynchronization() {
        LruCache<String, String> cache = new LruCache<String, String>(3) {
            @Override protected void entryRemoved(
                    boolean evicted, String key, String oldValue, String newValue) {
                assertFalse(Thread.holdsLock(this));
            }
        };

        cache.put("a", "A");
        cache.put("a", "A2"); // replaced
        cache.put("b", "B");
        cache.put("c", "C");
        cache.put("d", "D");  // single eviction
        cache.remove("a");    // removed
        cache.evictAll();     // multiple eviction
    }

    public void testCreateIsCalledWithoutSynchronization() {
        LruCache<String, String> cache = new LruCache<String, String>(3) {
            @Override protected String create(String key) {
                assertFalse(Thread.holdsLock(this));
                return null;
            }
        };

        cache.get("a");
    }

    /**
     * Test what happens when a value is added to the map while create is
     * working. The map value should be returned by get(), and the created value
     * should be released with entryRemoved().
     */
    public void testCreateWithConcurrentPut() {
        final List<String> log = new ArrayList<String>();
        LruCache<String, String> cache = new LruCache<String, String>(3) {
            @Override protected String create(String key) {
                put(key, "B");
                return "A";
            }
            @Override protected void entryRemoved(
                    boolean evicted, String key, String oldValue, String newValue) {
                log.add(key + "=" + oldValue + ">" + newValue);
            }
        };

        assertEquals("B", cache.get("a"));
        assertEquals(Arrays.asList("a=A>B"), log);
    }

    /**
     * Test what happens when two creates happen concurrently. The result from
     * the first create to return is returned by both gets. The other created
     * values should be released with entryRemove().
     */
    public void testCreateWithConcurrentCreate() {
        final List<String> log = new ArrayList<String>();
        LruCache<String, Integer> cache = new LruCache<String, Integer>(3) {
            int callCount = 0;
            @Override protected Integer create(String key) {
                if (callCount++ == 0) {
                    assertEquals(2, get(key).intValue());
                    return 1;
                } else {
                    return 2;
                }
            }
            @Override protected void entryRemoved(
                    boolean evicted, String key, Integer oldValue, Integer newValue) {
                log.add(key + "=" + oldValue + ">" + newValue);
            }
        };

        assertEquals(2, cache.get("a").intValue());
        assertEquals(Arrays.asList("a=1>2"), log);
    }

    private LruCache<String, String> newCreatingCache() {
        return new LruCache<String, String>(3) {
            @Override protected String create(String key) {
                return (key.length() > 1) ? ("created-" + key) : null;
            }
        };
    }

    private LruCache<String, String> newRemovalLogCache(final List<String> log) {
        return new LruCache<String, String>(3) {
            @Override protected void entryRemoved(
                    boolean evicted, String key, String oldValue, String newValue) {
                String message = evicted
                        ? (key + "=" + oldValue)
                        : (key + "=" + oldValue + ">" + newValue);
                log.add(message);
            }
        };
    }

    private void assertHit(LruCache<String, String> cache, String key, String value) {
        assertEquals(value, cache.get(key));
        expectedHitCount++;
        assertStatistics(cache);
    }

    private void assertMiss(LruCache<String, String> cache, String key) {
        assertEquals(null, cache.get(key));
        expectedMissCount++;
        assertStatistics(cache);
    }

    private void assertCreated(LruCache<String, String> cache, String key, String value) {
        assertEquals(value, cache.get(key));
        expectedMissCount++;
        expectedCreateCount++;
        assertStatistics(cache);
    }

    private void assertStatistics(LruCache<?, ?> cache) {
        assertEquals("create count", expectedCreateCount, cache.createCount());
        assertEquals("put count", expectedPutCount, cache.putCount());
        assertEquals("hit count", expectedHitCount, cache.hitCount());
        assertEquals("miss count", expectedMissCount, cache.missCount());
        assertEquals("eviction count", expectedEvictionCount, cache.evictionCount());
    }

    private <T> void assertSnapshot(LruCache<T, T> cache, T... keysAndValues) {
        List<T> actualKeysAndValues = new ArrayList<T>();
        for (Map.Entry<T, T> entry : cache.snapshot().entrySet()) {
            actualKeysAndValues.add(entry.getKey());
            actualKeysAndValues.add(entry.getValue());
        }

        // assert using lists because order is important for LRUs
        assertEquals(Arrays.asList(keysAndValues), actualKeysAndValues);
    }
}