11a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal/** 21a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Copyright (c) 2011, Google Inc. 31a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * 41a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Licensed under the Apache License, Version 2.0 (the "License"); 51a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * you may not use this file except in compliance with the License. 61a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * You may obtain a copy of the License at 71a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * 81a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * http://www.apache.org/licenses/LICENSE-2.0 91a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * 101a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Unless required by applicable law or agreed to in writing, software 111a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * distributed under the License is distributed on an "AS IS" BASIS, 121a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * See the License for the specific language governing permissions and 141a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * limitations under the License. 151a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 161a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 171a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwalpackage com.android.mail.utils; 181a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 191a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwalimport java.util.LinkedHashMap; 201a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwalimport java.util.Map; 211a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 221a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal/** 231a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * A simple in-memory LRU cache, which is trivial to implement on top 241a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * of JDK's {@link LinkedHashMap}. 251a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * 261a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * LRU policy is ensured by the underlying LinkedHashMap functionality. 271a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 281a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwalpublic final class LruCache<K, V> extends LinkedHashMap<K, V> { 291a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal private static final long serialVersionUID = 1L; 301a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal private final int maxCapacity; 311a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 321a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal /** 331a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Creates an instance of LRUCache, with given capacity. 341a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * 351a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param capacity maximum number of elements in the cache. This is also 361a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * used as initialCapacity i.e. memory is allocated upfront. 371a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 381a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal public LruCache(int capacity) { 391a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal this(capacity, capacity); 401a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 411a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 421a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal /** 431a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Creates an instance of LRUCache, with given capacity. 441a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * 451a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param initialCapacity initial capacity of the cache. 461a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param maxCapacity maximum number of elements in the cache. 471a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 481a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal private LruCache(int initialCapacity, int maxCapacity) { 491a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal super(initialCapacity, (float) 0.75, true); 501a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal this.maxCapacity = maxCapacity; 511a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 521a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 531a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal // These methods are needed because the default implementation of LinkedHashMap is *not* 541a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal // synchronized. 551a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal /** 561a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Gets an element from the cache, returning the element if found, or null if not 571a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param key 581a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @return 591a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 601a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal public synchronized V getElement(K key) { 611a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal return get(key); 621a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 631a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 641a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal /** 651a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Puts an element into the cache. 661a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param key 671a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param value, a non-null value. 681a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 691a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal public synchronized void putElement(K key, V value) { 701a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal put(key, value); 711a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 721a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 731a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal /** 741a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Removes an element from the cache. Returns the removed element, or null if no such element 751a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * existed in the cache. 761a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param key 771a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @return 781a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 791a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal public synchronized V removeElement(K key) { 801a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal return remove(key); 811a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 821a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 831a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal /** 841a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * {@inheritDoc} 851a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * <p> 861a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * Necessary to override because HashMap increases the capacity of the 871a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * hashtable before inserting the elements. However, here we call put() which 881a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * checks if we can remove the eldest element before increasing the capacity. 891a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 901a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal @Override 911a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal public synchronized void putAll(Map<? extends K, ? extends V> m) { 921a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 931a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal put(e.getKey(), e.getValue()); 941a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 951a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 961a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal 971a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal /** 981a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * This method is called by LinkedHashMap to check whether the eldest entry 991a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * should be removed. 1001a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * 1011a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @param eldest 1021a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal * @return true if element should be removed. 1031a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal */ 1041a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal @Override 1051a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal protected synchronized boolean removeEldestEntry(Map.Entry<K, V> eldest) { 1061a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal return size() > maxCapacity; 1071a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal } 1081a4bcc08699356eeaa25d8ad144a1a00cea76cd0Vikram Aggarwal} 109