1c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath/* 2c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Copyright (C) 2011 The Android Open Source Project 3c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * 4c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Licensed under the Apache License, Version 2.0 (the "License"); 5c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * you may not use this file except in compliance with the License. 6c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * You may obtain a copy of the License at 7c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * 8c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * http://www.apache.org/licenses/LICENSE-2.0 9c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * 10c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Unless required by applicable law or agreed to in writing, software 11c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * distributed under the License is distributed on an "AS IS" BASIS, 12c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * See the License for the specific language governing permissions and 14c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * limitations under the License. 15c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 16c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 17c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamathpackage libcore.util; 18c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 19c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamathimport java.util.LinkedHashMap; 20c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamathimport java.util.Map; 21c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 22c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath/** 23c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * A minimal least-recently-used cache for libcore. Prefer {@code 24c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * android.util.LruCache} where that is available. 25c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 26c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamathpublic class BasicLruCache<K, V> { 27c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath private final LinkedHashMap<K, V> map; 28c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath private final int maxSize; 29c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 30c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath public BasicLruCache(int maxSize) { 31c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath if (maxSize <= 0) { 32c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath throw new IllegalArgumentException("maxSize <= 0"); 33c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 34c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath this.maxSize = maxSize; 35c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 36c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 37c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 38c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath /** 39c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Returns the value for {@code key} if it exists in the cache or can be 40c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * created by {@code #create}. If a value was returned, it is moved to the 41c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * head of the queue. This returns null if a value is not cached and cannot 42c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * be created. 43c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 44c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath public synchronized final V get(K key) { 45c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath if (key == null) { 46c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath throw new NullPointerException(); 47c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 48c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 49c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath V result = map.get(key); 50c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath if (result != null) { 51c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath return result; 52c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 53c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 54c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath result = create(key); 55c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 56c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath if (result != null) { 57c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath map.put(key, result); 58c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath trimToSize(maxSize); 59c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 60c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath return result; 61c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 62c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 63c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath /** 64c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Caches {@code value} for {@code key}. The value is moved to the head of 65c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * the queue. 66c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * 67c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * @return the previous value mapped by {@code key}. Although that entry is 68c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * no longer cached, it has not been passed to {@link #entryEvicted}. 69c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 70c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath public synchronized final V put(K key, V value) { 71c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath if (key == null || value == null) { 72c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath throw new NullPointerException(); 73c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 74c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 75c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath V previous = map.put(key, value); 76c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath trimToSize(maxSize); 77c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath return previous; 78c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 79c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 80c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath private void trimToSize(int maxSize) { 81c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath while (map.size() > maxSize) { 82c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath Map.Entry<K, V> toEvict = map.entrySet().iterator().next(); 83c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 84c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath K key = toEvict.getKey(); 85c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath V value = toEvict.getValue(); 86c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath map.remove(key); 87c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 88c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath entryEvicted(key, value); 89c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 90c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 91c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 92c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath /** 93c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Called for entries that have reached the tail of the least recently used 94c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * queue and are be removed. The default implementation does nothing. 95c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 96c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath protected void entryEvicted(K key, V value) { 97c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 98c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 99c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath /** 100c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Called after a cache miss to compute a value for the corresponding key. 101c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Returns the computed value or null if no value can be computed. The 102c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * default implementation returns null. 103c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 104c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath protected V create(K key) { 105c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath return null; 106c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 107c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 108c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath /** 109c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Returns a copy of the current contents of the cache, ordered from least 110c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * recently accessed to most recently accessed. 111c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 112c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath public synchronized final Map<K, V> snapshot() { 113c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath return new LinkedHashMap<K, V>(map); 114c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 115c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath 116c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath /** 117c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath * Clear the cache, calling {@link #entryEvicted} on each removed entry. 118c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath */ 119c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath public synchronized final void evictAll() { 120c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath trimToSize(0); 121c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath } 122c3f6f16bd4a2338e88275641b9f2f56e816ca377Narayan Kamath} 123