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 com.android.contacts.util;
     18 
     19 import com.android.contacts.test.NeededForTesting;
     20 
     21 import android.util.LruCache;
     22 
     23 import java.util.concurrent.atomic.AtomicInteger;
     24 
     25 import javax.annotation.concurrent.Immutable;
     26 import javax.annotation.concurrent.ThreadSafe;
     27 
     28 /**
     29  * An LRU cache in which all items can be marked as expired at a given time and it is possible to
     30  * query whether a particular cached value is expired or not.
     31  * <p>
     32  * A typical use case for this is caching of values which are expensive to compute but which are
     33  * still useful when out of date.
     34  * <p>
     35  * Consider a cache for contact information:
     36  * <pre>{@code
     37  *     private ExpirableCache<String, Contact> mContactCache;}</pre>
     38  * which stores the contact information for a given phone number.
     39  * <p>
     40  * When we need to store contact information for a given phone number, we can look up the info in
     41  * the cache:
     42  * <pre>{@code
     43  *     CachedValue<Contact> cachedContact = mContactCache.getCachedValue(phoneNumber);
     44  * }</pre>
     45  * We might also want to fetch the contact information again if the item is expired.
     46  * <pre>
     47  *     if (cachedContact.isExpired()) {
     48  *         fetchContactForNumber(phoneNumber,
     49  *                 new FetchListener() {
     50  *                     &#64;Override
     51  *                     public void onFetched(Contact contact) {
     52  *                         mContactCache.put(phoneNumber, contact);
     53  *                     }
     54  *                 });
     55  *     }</pre>
     56  * and insert it back into the cache when the fetch completes.
     57  * <p>
     58  * At a certain point we want to expire the content of the cache because we know the content may
     59  * no longer be up-to-date, for instance, when resuming the activity this is shown into:
     60  * <pre>
     61  *     &#64;Override
     62  *     protected onResume() {
     63  *         // We were paused for some time, the cached value might no longer be up to date.
     64  *         mContactCache.expireAll();
     65  *         super.onResume();
     66  *     }
     67  * </pre>
     68  * The values will be still available from the cache, but they will be expired.
     69  * <p>
     70  * If interested only in the value itself, not whether it is expired or not, one should use the
     71  * {@link #getPossiblyExpired(Object)} method. If interested only in non-expired values, one should
     72  * use the {@link #get(Object)} method instead.
     73  * <p>
     74  * This class wraps around an {@link LruCache} instance: it follows the {@link LruCache} behavior
     75  * for evicting items when the cache is full. It is possible to supply your own subclass of LruCache
     76  * by using the {@link #create(LruCache)} method, which can define a custom expiration policy.
     77  * Since the underlying cache maps keys to cached values it can determine which items are expired
     78  * and which are not, allowing for an implementation that evicts expired items before non expired
     79  * ones.
     80  * <p>
     81  * This class is thread-safe.
     82  *
     83  * @param <K> the type of the keys
     84  * @param <V> the type of the values
     85  */
     86 @ThreadSafe
     87 public class ExpirableCache<K, V> {
     88     /**
     89      * A cached value stored inside the cache.
     90      * <p>
     91      * It provides access to the value stored in the cache but also allows to check whether the
     92      * value is expired.
     93      *
     94      * @param <V> the type of value stored in the cache
     95      */
     96     public interface CachedValue<V> {
     97         /** Returns the value stored in the cache for a given key. */
     98         public V getValue();
     99 
    100         /**
    101          * Checks whether the value, while still being present in the cache, is expired.
    102          *
    103          * @return true if the value is expired
    104          */
    105         public boolean isExpired();
    106     }
    107 
    108     /**
    109      * Cached values storing the generation at which they were added.
    110      */
    111     @Immutable
    112     private static class GenerationalCachedValue<V> implements ExpirableCache.CachedValue<V> {
    113         /** The value stored in the cache. */
    114         public final V mValue;
    115         /** The generation at which the value was added to the cache. */
    116         private final int mGeneration;
    117         /** The atomic integer storing the current generation of the cache it belongs to. */
    118         private final AtomicInteger mCacheGeneration;
    119 
    120         /**
    121          * @param cacheGeneration the atomic integer storing the generation of the cache in which
    122          *        this value will be stored
    123          */
    124         public GenerationalCachedValue(V value, AtomicInteger cacheGeneration) {
    125             mValue = value;
    126             mCacheGeneration = cacheGeneration;
    127             // Snapshot the current generation.
    128             mGeneration = mCacheGeneration.get();
    129         }
    130 
    131         @Override
    132         public V getValue() {
    133             return mValue;
    134         }
    135 
    136         @Override
    137         public boolean isExpired() {
    138             return mGeneration != mCacheGeneration.get();
    139         }
    140     }
    141 
    142     /** The underlying cache used to stored the cached values. */
    143     private LruCache<K, CachedValue<V>> mCache;
    144 
    145     /**
    146      * The current generation of items added to the cache.
    147      * <p>
    148      * Items in the cache can belong to a previous generation, but in that case they would be
    149      * expired.
    150      *
    151      * @see ExpirableCache.CachedValue#isExpired()
    152      */
    153     private final AtomicInteger mGeneration;
    154 
    155     private ExpirableCache(LruCache<K, CachedValue<V>> cache) {
    156         mCache = cache;
    157         mGeneration = new AtomicInteger(0);
    158     }
    159 
    160     /**
    161      * Returns the cached value for the given key, or null if no value exists.
    162      * <p>
    163      * The cached value gives access both to the value associated with the key and whether it is
    164      * expired or not.
    165      * <p>
    166      * If not interested in whether the value is expired, use {@link #getPossiblyExpired(Object)}
    167      * instead.
    168      * <p>
    169      * If only wants values that are not expired, use {@link #get(Object)} instead.
    170      *
    171      * @param key the key to look up
    172      */
    173     public CachedValue<V> getCachedValue(K key) {
    174         return mCache.get(key);
    175     }
    176 
    177     /**
    178      * Returns the value for the given key, or null if no value exists.
    179      * <p>
    180      * When using this method, it is not possible to determine whether the value is expired or not.
    181      * Use {@link #getCachedValue(Object)} to achieve that instead. However, if using
    182      * {@link #getCachedValue(Object)} to determine if an item is expired, one should use the item
    183      * within the {@link CachedValue} and not call {@link #getPossiblyExpired(Object)} to get the
    184      * value afterwards, since that is not guaranteed to return the same value or that the newly
    185      * returned value is in the same state.
    186      *
    187      * @param key the key to look up
    188      */
    189     public V getPossiblyExpired(K key) {
    190         CachedValue<V> cachedValue = getCachedValue(key);
    191         return cachedValue == null ? null : cachedValue.getValue();
    192     }
    193 
    194     /**
    195      * Returns the value for the given key only if it is not expired, or null if no value exists or
    196      * is expired.
    197      * <p>
    198      * This method will return null if either there is no value associated with this key or if the
    199      * associated value is expired.
    200      *
    201      * @param key the key to look up
    202      */
    203     @NeededForTesting
    204     public V get(K key) {
    205         CachedValue<V> cachedValue = getCachedValue(key);
    206         return cachedValue == null || cachedValue.isExpired() ? null : cachedValue.getValue();
    207     }
    208 
    209     /**
    210      * Puts an item in the cache.
    211      * <p>
    212      * Newly added item will not be expired until {@link #expireAll()} is next called.
    213      *
    214      * @param key the key to look up
    215      * @param value the value to associate with the key
    216      */
    217     public void put(K key, V value) {
    218         mCache.put(key, newCachedValue(value));
    219     }
    220 
    221     /**
    222      * Mark all items currently in the cache as expired.
    223      * <p>
    224      * Newly added items after this call will be marked as not expired.
    225      * <p>
    226      * Expiring the items in the cache does not imply they will be evicted.
    227      */
    228     public void expireAll() {
    229         mGeneration.incrementAndGet();
    230     }
    231 
    232     /**
    233      * Creates a new {@link CachedValue} instance to be stored in this cache.
    234      * <p>
    235      * Implementation of {@link LruCache#create(K)} can use this method to create a new entry.
    236      */
    237     public CachedValue<V> newCachedValue(V value) {
    238         return new GenerationalCachedValue<V>(value, mGeneration);
    239     }
    240 
    241     /**
    242      * Creates a new {@link ExpirableCache} that wraps the given {@link LruCache}.
    243      * <p>
    244      * The created cache takes ownership of the cache passed in as an argument.
    245      *
    246      * @param <K> the type of the keys
    247      * @param <V> the type of the values
    248      * @param cache the cache to store the value in
    249      * @return the newly created expirable cache
    250      * @throws IllegalArgumentException if the cache is not empty
    251      */
    252     public static <K, V> ExpirableCache<K, V> create(LruCache<K, CachedValue<V>> cache) {
    253         return new ExpirableCache<K, V>(cache);
    254     }
    255 
    256     /**
    257      * Creates a new {@link ExpirableCache} with the given maximum size.
    258      *
    259      * @param <K> the type of the keys
    260      * @param <V> the type of the values
    261      * @return the newly created expirable cache
    262      */
    263     public static <K, V> ExpirableCache<K, V> create(int maxSize) {
    264         return create(new LruCache<K, CachedValue<V>>(maxSize));
    265     }
    266 }
    267