Home | History | Annotate | Download | only in util 
      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 
     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      */
     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      */
     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 
     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      */
    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      */
    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      */
    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      */
    132     public synchronized final void evictAll() {
    133         trimToSize(0);
    134     }
    135 }
    136