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 17 package libcore.util; 18 19 import java.util.LinkedHashMap; 20 import java.util.Map; 21 22 /** 23 * A minimal least-recently-used cache for libcore. Prefer {@code 24 * android.util.LruCache} where that is available. 25 */ 26 public class BasicLruCache<K, V> { 27 private final LinkedHashMap<K, V> map; 28 private final int maxSize; 29 BasicLruCache(int maxSize)30 public BasicLruCache(int maxSize) { 31 if (maxSize <= 0) { 32 throw new IllegalArgumentException("maxSize <= 0"); 33 } 34 this.maxSize = maxSize; 35 this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 36 } 37 38 /** 39 * Returns the value for {@code key} if it exists in the cache or can be 40 * created by {@code #create}. If a value was returned, it is moved to the 41 * head of the queue. This returns null if a value is not cached and cannot 42 * be created. 43 */ get(K key)44 public final V get(K key) { 45 if (key == null) { 46 throw new NullPointerException("key == null"); 47 } 48 49 V result; 50 synchronized (this) { 51 result = map.get(key); 52 if (result != null) { 53 return result; 54 } 55 } 56 57 // Don't hold any locks while calling create. 58 result = create(key); 59 60 synchronized (this) { 61 // NOTE: Another thread might have already inserted a value for |key| into the map. 62 // This shouldn't be an observable change as long as create creates equal values for 63 // equal keys. We will however attempt to trim the map twice, but that shouldn't be 64 // a big deal since uses of this class aren't heavily contended (and this class 65 // isn't design for such usage anyway). 66 if (result != null) { 67 map.put(key, result); 68 trimToSize(maxSize); 69 } 70 } 71 72 return result; 73 } 74 75 /** 76 * Caches {@code value} for {@code key}. The value is moved to the head of 77 * the queue. 78 * 79 * @return the previous value mapped by {@code key}. Although that entry is 80 * no longer cached, it has not been passed to {@link #entryEvicted}. 81 */ put(K key, V value)82 public synchronized final V put(K key, V value) { 83 if (key == null) { 84 throw new NullPointerException("key == null"); 85 } else if (value == null) { 86 throw new NullPointerException("value == null"); 87 } 88 89 V previous = map.put(key, value); 90 trimToSize(maxSize); 91 return previous; 92 } 93 trimToSize(int maxSize)94 private void trimToSize(int maxSize) { 95 while (map.size() > maxSize) { 96 Map.Entry<K, V> toEvict = map.eldest(); 97 98 K key = toEvict.getKey(); 99 V value = toEvict.getValue(); 100 map.remove(key); 101 102 entryEvicted(key, value); 103 } 104 } 105 106 /** 107 * Called for entries that have reached the tail of the least recently used 108 * queue and are be removed. The default implementation does nothing. 109 */ entryEvicted(K key, V value)110 protected void entryEvicted(K key, V value) {} 111 112 /** 113 * Called after a cache miss to compute a value for the corresponding key. 114 * Returns the computed value or null if no value can be computed. The 115 * default implementation returns null. 116 */ create(K key)117 protected V create(K key) { 118 return null; 119 } 120 121 /** 122 * Returns a copy of the current contents of the cache, ordered from least 123 * recently accessed to most recently accessed. 124 */ snapshot()125 public synchronized final Map<K, V> snapshot() { 126 return new LinkedHashMap<K, V>(map); 127 } 128 129 /** 130 * Clear the cache, calling {@link #entryEvicted} on each removed entry. 131 */ evictAll()132 public synchronized final void evictAll() { 133 trimToSize(0); 134 } 135 } 136