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 synchronized final V get(K key) {
     45         if (key == null) {
     46             throw new NullPointerException();
     47         }
     48 
     49         V result = map.get(key);
     50         if (result != null) {
     51             return result;
     52         }
     53 
     54         result = create(key);
     55 
     56         if (result != null) {
     57             map.put(key, result);
     58             trimToSize(maxSize);
     59         }
     60         return result;
     61     }
     62 
     63     /**
     64      * Caches {@code value} for {@code key}. The value is moved to the head of
     65      * the queue.
     66      *
     67      * @return the previous value mapped by {@code key}. Although that entry is
     68      *     no longer cached, it has not been passed to {@link #entryEvicted}.
     69      */
     70     public synchronized final V put(K key, V value) {
     71         if (key == null || value == null) {
     72             throw new NullPointerException();
     73         }
     74 
     75         V previous = map.put(key, value);
     76         trimToSize(maxSize);
     77         return previous;
     78     }
     79 
     80     private void trimToSize(int maxSize) {
     81         while (map.size() > maxSize) {
     82             Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
     83 
     84             K key = toEvict.getKey();
     85             V value = toEvict.getValue();
     86             map.remove(key);
     87 
     88             entryEvicted(key, value);
     89         }
     90     }
     91 
     92     /**
     93      * Called for entries that have reached the tail of the least recently used
     94      * queue and are be removed. The default implementation does nothing.
     95      */
     96     protected void entryEvicted(K key, V value) {
     97     }
     98 
     99     /**
    100      * Called after a cache miss to compute a value for the corresponding key.
    101      * Returns the computed value or null if no value can be computed. The
    102      * default implementation returns null.
    103      */
    104     protected V create(K key) {
    105         return null;
    106     }
    107 
    108     /**
    109      * Returns a copy of the current contents of the cache, ordered from least
    110      * recently accessed to most recently accessed.
    111      */
    112     public synchronized final Map<K, V> snapshot() {
    113         return new LinkedHashMap<K, V>(map);
    114     }
    115 
    116     /**
    117      * Clear the cache, calling {@link #entryEvicted} on each removed entry.
    118      */
    119     public synchronized final void evictAll() {
    120         trimToSize(0);
    121     }
    122 }
    123