src/com/cyanogenmod/eleven/cache/LruCache.java

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