apps/AndroidSupportV2/src/android/support/v2/util/LruCache.java

   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 android.support.v2.util;
  18
  19 import java.util.LinkedHashMap;
  20 import java.util.Map;
  21
  22 /**
  23  * Static library version of {@code android.util.LruCache}. Used to write apps
  24  * that run on API levels prior to 12. When running on API level 12 or above,
  25  * this implementation is still used; it does not try to switch to the
  26  * framework's implementation. See the framework SDK documentation for a class
  27  * overview.
  28  */
  29 public class LruCache<K, V> {
  30     private final LinkedHashMap<K, V> map;
  31
  32     /** Size of this cache in units. Not necessarily the number of elements. */
  33     private int size;
  34     private int maxSize;
  35
  36     private int putCount;
  37     private int createCount;
  38     private int evictionCount;
  39     private int hitCount;
  40     private int missCount;
  41
  42     /**
  43      * @param maxSize for caches that do not override {@link #sizeOf}, this is
  44      *     the maximum number of entries in the cache. For all other caches,
  45      *     this is the maximum sum of the sizes of the entries in this cache.
  46      */
  47     public LruCache(int maxSize) {
  48         if (maxSize <= 0) {
  49             throw new IllegalArgumentException("maxSize <= 0");
  50         }
  51         this.maxSize = maxSize;
  52         this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
  53     }
  54
  55     /**
  56      * Returns the value for {@code key} if it exists in the cache or can be
  57      * created by {@code #create}. If a value was returned, it is moved to the
  58      * head of the queue. This returns null if a value is not cached and cannot
  59      * be created.
  60      */
  61     public final V get(K key) {
  62         if (key == null) {
  63             throw new NullPointerException("key == null");
  64         }
  65
  66         V mapValue;
  67         synchronized (this) {
  68             mapValue = map.get(key);
  69             if (mapValue != null) {
  70                 hitCount++;
  71                 return mapValue;
  72             }
  73             missCount++;
  74         }
  75
  76         /*
  77          * Attempt to create a value. This may take a long time, and the map
  78          * may be different when create() returns. If a conflicting value was
  79          * added to the map while create() was working, we leave that value in
  80          * the map and release the created value.
  81          */
  82
  83         V createdValue = create(key);
  84         if (createdValue == null) {
  85             return null;
  86         }
  87
  88         synchronized (this) {
  89             createCount++;
  90             mapValue = map.put(key, createdValue);
  91
  92             if (mapValue != null) {
  93                 // There was a conflict so undo that last put
  94                 map.put(key, mapValue);
  95             } else {
  96                 size += safeSizeOf(key, createdValue);
  97             }
  98         }
  99
 100         if (mapValue != null) {
 101             entryRemoved(false, key, createdValue, mapValue);
 102             return mapValue;
 103         } else {
 104             trimToSize(maxSize);
 105             return createdValue;
 106         }
 107     }
 108
 109     /**
 110      * Caches {@code value} for {@code key}. The value is moved to the head of
 111      * the queue.
 112      *
 113      * @return the previous value mapped by {@code key}.
 114      */
 115     public final V put(K key, V value) {
 116         if (key == null || value == null) {
 117             throw new NullPointerException("key == null || value == null");
 118         }
 119
 120         V previous;
 121         synchronized (this) {
 122             putCount++;
 123             size += safeSizeOf(key, value);
 124             previous = map.put(key, value);
 125             if (previous != null) {
 126                 size -= safeSizeOf(key, previous);
 127             }
 128         }
 129
 130         if (previous != null) {
 131             entryRemoved(false, key, previous, value);
 132         }
 133
 134         trimToSize(maxSize);
 135         return previous;
 136     }
 137
 138     /**
 139      * @param maxSize the maximum size of the cache before returning. May be -1
 140      *     to evict even 0-sized elements.
 141      */
 142     private void trimToSize(int maxSize) {
 143         while (true) {
 144             K key;
 145             V value;
 146             synchronized (this) {
 147                 if (size < 0 || (map.isEmpty() && size != 0)) {
 148                     throw new IllegalStateException(getClass().getName()
 149                             + ".sizeOf() is reporting inconsistent results!");
 150                 }
 151
 152                 if (size <= maxSize || map.isEmpty()) {
 153                     break;
 154                 }
 155
 156                 Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
 157                 key = toEvict.getKey();
 158                 value = toEvict.getValue();
 159                 map.remove(key);
 160                 size -= safeSizeOf(key, value);
 161                 evictionCount++;
 162             }
 163
 164             entryRemoved(true, key, value, null);
 165         }
 166     }
 167
 168     /**
 169      * Removes the entry for {@code key} if it exists.
 170      *
 171      * @return the previous value mapped by {@code key}.
 172      */
 173     public final V remove(K key) {
 174         if (key == null) {
 175             throw new NullPointerException("key == null");
 176         }
 177
 178         V previous;
 179         synchronized (this) {
 180             previous = map.remove(key);
 181             if (previous != null) {
 182                 size -= safeSizeOf(key, previous);
 183             }
 184         }
 185
 186         if (previous != null) {
 187             entryRemoved(false, key, previous, null);
 188         }
 189
 190         return previous;
 191     }
 192
 193     /**
 194      * Called for entries that have been evicted or removed. This method is
 195      * invoked when a value is evicted to make space, removed by a call to
 196      * {@link #remove}, or replaced by a call to {@link #put}. The default
 197      * implementation does nothing.
 198      *
 199      * <p>The method is called without synchronization: other threads may
 200      * access the cache while this method is executing.
 201      *
 202      * @param evicted true if the entry is being removed to make space, false
 203      *     if the removal was caused by a {@link #put} or {@link #remove}.
 204      * @param newValue the new value for {@code key}, if it exists. If non-null,
 205      *     this removal was caused by a {@link #put}. Otherwise it was caused by
 206      *     an eviction or a {@link #remove}.
 207      */
 208     protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
 209
 210     /**
 211      * Called after a cache miss to compute a value for the corresponding key.
 212      * Returns the computed value or null if no value can be computed. The
 213      * default implementation returns null.
 214      *
 215      * <p>The method is called without synchronization: other threads may
 216      * access the cache while this method is executing.
 217      *
 218      * <p>If a value for {@code key} exists in the cache when this method
 219      * returns, the created value will be released with {@link #entryRemoved}
 220      * and discarded. This can occur when multiple threads request the same key
 221      * at the same time (causing multiple values to be created), or when one
 222      * thread calls {@link #put} while another is creating a value for the same
 223      * key.
 224      */
 225     protected V create(K key) {
 226         return null;
 227     }
 228
 229     private int safeSizeOf(K key, V value) {
 230         int result = sizeOf(key, value);
 231         if (result < 0) {
 232             throw new IllegalStateException("Negative size: " + key + "=" + value);
 233         }
 234         return result;
 235     }
 236
 237     /**
 238      * Returns the size of the entry for {@code key} and {@code value} in
 239      * user-defined units.  The default implementation returns 1 so that size
 240      * is the number of entries and max size is the maximum number of entries.
 241      *
 242      * <p>An entry's size must not change while it is in the cache.
 243      */
 244     protected int sizeOf(K key, V value) {
 245         return 1;
 246     }
 247
 248     /**
 249      * Clear the cache, calling {@link #entryRemoved} on each removed entry.
 250      */
 251     public final void evictAll() {
 252         trimToSize(-1); // -1 will evict 0-sized elements
 253     }
 254
 255     /**
 256      * For caches that do not override {@link #sizeOf}, this returns the number
 257      * of entries in the cache. For all other caches, this returns the sum of
 258      * the sizes of the entries in this cache.
 259      */
 260     public synchronized final int size() {
 261         return size;
 262     }
 263
 264     /**
 265      * For caches that do not override {@link #sizeOf}, this returns the maximum
 266      * number of entries in the cache. For all other caches, this returns the
 267      * maximum sum of the sizes of the entries in this cache.
 268      */
 269     public synchronized final int maxSize() {
 270         return maxSize;
 271     }
 272
 273     /**
 274      * Returns the number of times {@link #get} returned a value.
 275      */
 276     public synchronized final int hitCount() {
 277         return hitCount;
 278     }
 279
 280     /**
 281      * Returns the number of times {@link #get} returned null or required a new
 282      * value to be created.
 283      */
 284     public synchronized final int missCount() {
 285         return missCount;
 286     }
 287
 288     /**
 289      * Returns the number of times {@link #create(Object)} returned a value.
 290      */
 291     public synchronized final int createCount() {
 292         return createCount;
 293     }
 294
 295     /**
 296      * Returns the number of times {@link #put} was called.
 297      */
 298     public synchronized final int putCount() {
 299         return putCount;
 300     }
 301
 302     /**
 303      * Returns the number of values that have been evicted.
 304      */
 305     public synchronized final int evictionCount() {
 306         return evictionCount;
 307     }
 308
 309     /**
 310      * Returns a copy of the current contents of the cache, ordered from least
 311      * recently accessed to most recently accessed.
 312      */
 313     public synchronized final Map<K, V> snapshot() {
 314         return new LinkedHashMap<K, V>(map);
 315     }
 316
 317     @Override public synchronized final String toString() {
 318         int accesses = hitCount + missCount;
 319         int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
 320         return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
 321                 maxSize, hitCount, missCount, hitPercent);
 322     }
 323 }