1d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen/** 2d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * $Revision: 1456 $ 3d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * $Date: 2005-06-01 22:04:54 -0700 (Wed, 01 Jun 2005) $ 4d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 5d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Copyright 2003-2005 Jive Software. 6d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 7d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * All rights reserved. Licensed under the Apache License, Version 2.0 (the "License"); 8d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * you may not use this file except in compliance with the License. 9d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * You may obtain a copy of the License at 10d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 11d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * http://www.apache.org/licenses/LICENSE-2.0 12d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 13d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Unless required by applicable law or agreed to in writing, software 14d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * distributed under the License is distributed on an "AS IS" BASIS, 15d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * See the License for the specific language governing permissions and 17d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * limitations under the License. 18d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 19d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 20d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chenpackage org.jivesoftware.smack.util; 21d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 22d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chenimport org.jivesoftware.smack.util.collections.AbstractMapEntry; 23d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 24d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chenimport java.util.*; 25d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 26d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen/** 27d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * A specialized Map that is size-limited (using an LRU algorithm) and 28d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * has an optional expiration time for cache items. The Map is thread-safe.<p> 29d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 30d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * The algorithm for cache is as follows: a HashMap is maintained for fast 31d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * object lookup. Two linked lists are maintained: one keeps objects in the 32d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * order they are accessed from cache, the other keeps objects in the order 33d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * they were originally added to cache. When objects are added to cache, they 34d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * are first wrapped by a CacheObject which maintains the following pieces 35d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * of information:<ul> 36d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * <li> A pointer to the node in the linked list that maintains accessed 37d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * order for the object. Keeping a reference to the node lets us avoid 38d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * linear scans of the linked list. 39d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * <li> A pointer to the node in the linked list that maintains the age 40d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * of the object in cache. Keeping a reference to the node lets us avoid 41d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * linear scans of the linked list.</ul> 42d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * <p/> 43d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * To get an object from cache, a hash lookup is performed to get a reference 44d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * to the CacheObject that wraps the real object we are looking for. 45d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * The object is subsequently moved to the front of the accessed linked list 46d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * and any necessary cache cleanups are performed. Cache deletion and expiration 47d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * is performed as needed. 48d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 49d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @author Matt Tucker 50d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 51d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chenpublic class Cache<K, V> implements Map<K, V> { 52d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 53d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 54d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * The map the keys and values are stored in. 55d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 56d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected Map<K, CacheObject<V>> map; 57d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 58d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 59d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Linked list to maintain order that cache objects are accessed 60d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * in, most used to least used. 61d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 62d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected LinkedList lastAccessedList; 63d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 64d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 65d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Linked list to maintain time that cache objects were initially added 66d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * to the cache, most recently added to oldest added. 67d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 68d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected LinkedList ageList; 69d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 70d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 71d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Maximum number of items the cache will hold. 72d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 73d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected int maxCacheSize; 74d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 75d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 76d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Maximum length of time objects can exist in cache before expiring. 77d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 78d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected long maxLifetime; 79d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 80d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 81d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Maintain the number of cache hits and misses. A cache hit occurs every 82d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * time the get method is called and the cache contains the requested 83d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * object. A cache miss represents the opposite occurence.<p> 84d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 85d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Keeping track of cache hits and misses lets one measure how efficient 86d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * the cache is; the higher the percentage of hits, the more efficient. 87d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 88d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected long cacheHits, cacheMisses = 0L; 89d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 90d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 91d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Create a new cache and specify the maximum size of for the cache in 92d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * bytes, and the maximum lifetime of objects. 93d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 94d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param maxSize the maximum number of objects the cache will hold. -1 95d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * means the cache has no max size. 96d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param maxLifetime the maximum amount of time (in ms) objects can exist in 97d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * cache before being deleted. -1 means objects never expire. 98d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 99d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public Cache(int maxSize, long maxLifetime) { 100d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (maxSize == 0) { 101d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen throw new IllegalArgumentException("Max cache size cannot be 0."); 102d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 103d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.maxCacheSize = maxSize; 104d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.maxLifetime = maxLifetime; 105d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 106d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Our primary data structure is a hash map. The default capacity of 11 107d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // is too small in almost all cases, so we set it bigger. 108d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen map = new HashMap<K, CacheObject<V>>(103); 109d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 110d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen lastAccessedList = new LinkedList(); 111d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen ageList = new LinkedList(); 112d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 113d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 114d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized V put(K key, V value) { 115d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen V oldValue = null; 116d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Delete an old entry if it exists. 117d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (map.containsKey(key)) { 118d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen oldValue = remove(key, true); 119d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 120d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 121d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen CacheObject<V> cacheObject = new CacheObject<V>(value); 122d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen map.put(key, cacheObject); 123d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Make an entry into the cache order list. 124d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Store the cache order list entry so that we can get back to it 125d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // during later lookups. 126d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.lastAccessedListNode = lastAccessedList.addFirst(key); 127d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Add the object to the age list 128d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode ageNode = ageList.addFirst(key); 129d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen ageNode.timestamp = System.currentTimeMillis(); 130d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.ageListNode = ageNode; 131d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 132d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // If cache is too full, remove least used cache entries until it is not too full. 133d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cullCache(); 134d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 135d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return oldValue; 136d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 137d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 138d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized V get(Object key) { 139d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 140d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 141d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 142d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 143d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen CacheObject<V> cacheObject = map.get(key); 144d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (cacheObject == null) { 145d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // The object didn't exist in cache, so increment cache misses. 146d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheMisses++; 147d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return null; 148d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 149d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Remove the object from it's current place in the cache order list, 150d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // and re-insert it at the front of the list. 151d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.lastAccessedListNode.remove(); 152d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen lastAccessedList.addFirst(cacheObject.lastAccessedListNode); 153d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 154d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // The object exists in cache, so increment cache hits. Also, increment 155d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // the object's read count. 156d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheHits++; 157d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.readCount++; 158d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 159d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return cacheObject.object; 160d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 161d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 162d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized V remove(Object key) { 163d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return remove(key, false); 164d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 165d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 166d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /* 167d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Remove operation with a flag so we can tell coherence if the remove was 168d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * caused by cache internal processing such as eviction or loading 169d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 170d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized V remove(Object key, boolean internal) { 171d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen //noinspection SuspiciousMethodCalls 172d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen CacheObject<V> cacheObject = map.remove(key); 173d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // If the object is not in cache, stop trying to remove it. 174d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (cacheObject == null) { 175d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return null; 176d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 177d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Remove from the cache order list 178d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.lastAccessedListNode.remove(); 179d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.ageListNode.remove(); 180d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Remove references to linked list nodes 181d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.ageListNode = null; 182d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheObject.lastAccessedListNode = null; 183d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 184d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return cacheObject.object; 185d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 186d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 187d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized void clear() { 188d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen Object[] keys = map.keySet().toArray(); 189d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen for (Object key : keys) { 190d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen remove(key); 191d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 192d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 193d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Now, reset all containers. 194d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen map.clear(); 195d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen lastAccessedList.clear(); 196d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen ageList.clear(); 197d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 198d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheHits = 0; 199d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cacheMisses = 0; 200d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 201d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 202d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized int size() { 203d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 204d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 205d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 206d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 207d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return map.size(); 208d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 209d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 210d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized boolean isEmpty() { 211d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 212d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 213d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 214d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 215d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return map.isEmpty(); 216d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 217d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 218d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized Collection<V> values() { 219d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 220d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 221d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 222d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 223d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return Collections.unmodifiableCollection(new AbstractCollection<V>() { 224d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen Collection<CacheObject<V>> values = map.values(); 225d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public Iterator<V> iterator() { 226d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return new Iterator<V>() { 227d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen Iterator<CacheObject<V>> it = values.iterator(); 228d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 229d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public boolean hasNext() { 230d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return it.hasNext(); 231d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 232d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 233d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public V next() { 234d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return it.next().object; 235d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 236d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 237d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public void remove() { 238d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen it.remove(); 239d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 240d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen }; 241d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 242d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 243d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public int size() { 244d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return values.size(); 245d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 246d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen }); 247d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 248d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 249d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized boolean containsKey(Object key) { 250d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 251d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 252d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 253d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 254d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return map.containsKey(key); 255d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 256d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 257d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public void putAll(Map<? extends K, ? extends V> map) { 258d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen for (Entry<? extends K, ? extends V> entry : map.entrySet()) { 259d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen V value = entry.getValue(); 260d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // If the map is another DefaultCache instance than the 261d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // entry values will be CacheObject instances that need 262d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // to be converted to the normal object form. 263d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (value instanceof CacheObject) { 264d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen //noinspection unchecked 265d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen value = ((CacheObject<V>) value).object; 266d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 267d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen put(entry.getKey(), value); 268d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 269d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 270d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 271d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized boolean containsValue(Object value) { 272d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 273d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 274d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 275d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 276d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen //noinspection unchecked 277d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen CacheObject<V> cacheObject = new CacheObject<V>((V) value); 278d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 279d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return map.containsValue(cacheObject); 280d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 281d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 282d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized Set<Map.Entry<K, V>> entrySet() { 283d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Warning -- this method returns CacheObject instances and not Objects 284d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // in the same form they were put into cache. 285d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 286d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 287d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 288d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 289d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 290d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return new AbstractSet<Map.Entry<K, V>>() { 291d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen private final Set<Map.Entry<K, CacheObject<V>>> set = map.entrySet(); 292d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 293d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public Iterator<Entry<K, V>> iterator() { 294d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return new Iterator<Entry<K, V>>() { 295d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen private final Iterator<Entry<K, CacheObject<V>>> it = set.iterator(); 296d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public boolean hasNext() { 297d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return it.hasNext(); 298d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 299d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 300d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public Entry<K, V> next() { 301d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen Map.Entry<K, CacheObject<V>> entry = it.next(); 302d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return new AbstractMapEntry<K, V>(entry.getKey(), entry.getValue().object) { 303d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen @Override 304d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public V setValue(V value) { 305d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen throw new UnsupportedOperationException("Cannot set"); 306d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 307d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen }; 308d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 309d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 310d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public void remove() { 311d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen it.remove(); 312d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 313d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen }; 314d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 315d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 316d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 317d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public int size() { 318d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return set.size(); 319d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 320d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen }; 321d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 322d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 323d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized Set<K> keySet() { 324d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, clear all entries that have been in cache longer than the 325d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // maximum defined age. 326d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 327d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 328d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return Collections.unmodifiableSet(map.keySet()); 329d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 330d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 331d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public long getCacheHits() { 332d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return cacheHits; 333d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 334d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 335d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public long getCacheMisses() { 336d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return cacheMisses; 337d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 338d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 339d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public int getMaxCacheSize() { 340d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return maxCacheSize; 341d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 342d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 343d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public synchronized void setMaxCacheSize(int maxCacheSize) { 344d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.maxCacheSize = maxCacheSize; 345d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // It's possible that the new max size is smaller than our current cache 346d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // size. If so, we need to delete infrequently used items. 347d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen cullCache(); 348d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 349d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 350d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public long getMaxLifetime() { 351d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return maxLifetime; 352d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 353d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 354d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public void setMaxLifetime(long maxLifetime) { 355d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.maxLifetime = maxLifetime; 356d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 357d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 358d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 359d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Clears all entries out of cache where the entries are older than the 360d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * maximum defined age. 361d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 362d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected synchronized void deleteExpiredEntries() { 363d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Check if expiration is turned on. 364d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (maxLifetime <= 0) { 365d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return; 366d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 367d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 368d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Remove all old entries. To do this, we remove objects from the end 369d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // of the linked list until they are no longer too old. We get to avoid 370d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // any hash lookups or looking at any more objects than is strictly 371d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // neccessary. 372d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode node = ageList.getLast(); 373d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // If there are no entries in the age list, return. 374d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (node == null) { 375d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return; 376d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 377d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 378d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Determine the expireTime, which is the moment in time that elements 379d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // should expire from cache. Then, we can do an easy check to see 380d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // if the expire time is greater than the expire time. 381d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen long expireTime = System.currentTimeMillis() - maxLifetime; 382d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 383d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen while (expireTime > node.timestamp) { 384d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (remove(node.object, true) == null) { 385d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen System.err.println("Error attempting to remove(" + node.object.toString() + 386d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen ") - cacheObject not found in cache!"); 387d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // remove from the ageList 388d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.remove(); 389d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 390d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 391d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Get the next node. 392d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node = ageList.getLast(); 393d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // If there are no more entries in the age list, return. 394d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (node == null) { 395d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return; 396d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 397d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 398d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 399d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 400d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 401d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Removes the least recently used elements if the cache size is greater than 402d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * or equal to the maximum allowed size until the cache is at least 10% empty. 403d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 404d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen protected synchronized void cullCache() { 405d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Check if a max cache size is defined. 406d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (maxCacheSize < 0) { 407d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return; 408d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 409d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 410d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // See if the cache is too big. If so, clean out cache until it's 10% free. 411d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (map.size() > maxCacheSize) { 412d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // First, delete any old entries to see how much memory that frees. 413d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen deleteExpiredEntries(); 414d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Next, delete the least recently used elements until 10% of the cache 415d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // has been freed. 416d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen int desiredSize = (int) (maxCacheSize * .90); 417d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen for (int i=map.size(); i>desiredSize; i--) { 418d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen // Get the key and invoke the remove method on it. 419d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (remove(lastAccessedList.getLast().object, true) == null) { 420d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen System.err.println("Error attempting to cullCache with remove(" + 421d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen lastAccessedList.getLast().object.toString() + ") - " + 422d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen "cacheObject not found in cache!"); 423d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen lastAccessedList.getLast().remove(); 424d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 425d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 426d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 427d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 428d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 429d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 430d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Wrapper for all objects put into cache. It's primary purpose is to maintain 431d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * references to the linked lists that maintain the creation time of the object 432d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * and the ordering of the most used objects. 433d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 434d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * This class is optimized for speed rather than strictly correct encapsulation. 435d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 436d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen private static class CacheObject<V> { 437d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 438d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 439d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Underlying object wrapped by the CacheObject. 440d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 441d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public V object; 442d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 443d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 444d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * A reference to the node in the cache order list. We keep the reference 445d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * here to avoid linear scans of the list. Every time the object is 446d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * accessed, the node is removed from its current spot in the list and 447d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * moved to the front. 448d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 449d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode lastAccessedListNode; 450d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 451d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 452d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * A reference to the node in the age order list. We keep the reference 453d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * here to avoid linear scans of the list. The reference is used if the 454d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * object has to be deleted from the list. 455d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 456d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode ageListNode; 457d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 458d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 459d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * A count of the number of times the object has been read from cache. 460d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 461d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public int readCount = 0; 462d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 463d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 464d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Creates a new cache object wrapper. 465d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 466d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param object the underlying Object to wrap. 467d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 468d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public CacheObject(V object) { 469d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.object = object; 470d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 471d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 472d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public boolean equals(Object o) { 473d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (this == o) { 474d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return true; 475d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 476d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (!(o instanceof CacheObject)) { 477d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return false; 478d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 479d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 480d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen final CacheObject<?> cacheObject = (CacheObject<?>) o; 481d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 482d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return object.equals(cacheObject.object); 483d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 484d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 485d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 486d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public int hashCode() { 487d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return object.hashCode(); 488d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 489d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 490d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 491d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 492d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Simple LinkedList implementation. The main feature is that list nodes 493d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * are public, which allows very fast delete operations when one has a 494d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * reference to the node that is to be deleted.<p> 495d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 496d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen private static class LinkedList { 497d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 498d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 499d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * The root of the list keeps a reference to both the first and last 500d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * elements of the list. 501d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 502d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen private LinkedListNode head = new LinkedListNode("head", null, null); 503d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 504d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 505d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Creates a new linked list. 506d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 507d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedList() { 508d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen head.next = head.previous = head; 509d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 510d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 511d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 512d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Returns the first linked list node in the list. 513d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 514d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @return the first element of the list. 515d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 516d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode getFirst() { 517d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode node = head.next; 518d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (node == head) { 519d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return null; 520d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 521d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return node; 522d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 523d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 524d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 525d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Returns the last linked list node in the list. 526d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 527d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @return the last element of the list. 528d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 529d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode getLast() { 530d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode node = head.previous; 531d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen if (node == head) { 532d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return null; 533d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 534d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return node; 535d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 536d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 537d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 538d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Adds a node to the beginning of the list. 539d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 540d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param node the node to add to the beginning of the list. 541d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @return the node 542d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 543d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode addFirst(LinkedListNode node) { 544d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.next = head.next; 545d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.previous = head; 546d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.previous.next = node; 547d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.next.previous = node; 548d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return node; 549d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 550d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 551d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 552d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Adds an object to the beginning of the list by automatically creating a 553d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * a new node and adding it to the beginning of the list. 554d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 555d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param object the object to add to the beginning of the list. 556d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @return the node created to wrap the object. 557d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 558d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode addFirst(Object object) { 559d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode node = new LinkedListNode(object, head.next, head); 560d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.previous.next = node; 561d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.next.previous = node; 562d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return node; 563d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 564d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 565d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 566d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Adds an object to the end of the list by automatically creating a 567d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * a new node and adding it to the end of the list. 568d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 569d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param object the object to add to the end of the list. 570d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @return the node created to wrap the object. 571d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 572d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode addLast(Object object) { 573d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode node = new LinkedListNode(object, head, head.previous); 574d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.previous.next = node; 575d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.next.previous = node; 576d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return node; 577d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 578d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 579d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 580d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Erases all elements in the list and re-initializes it. 581d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 582d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public void clear() { 583d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen //Remove all references in the list. 584d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode node = getLast(); 585d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen while (node != null) { 586d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node.remove(); 587d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node = getLast(); 588d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 589d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 590d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen //Re-initialize. 591d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen head.next = head.previous = head; 592d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 593d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 594d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 595d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Returns a String representation of the linked list with a comma 596d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * delimited list of all the elements in the list. 597d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 598d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @return a String representation of the LinkedList. 599d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 600d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public String toString() { 601d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode node = head.next; 602d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen StringBuilder buf = new StringBuilder(); 603d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen while (node != head) { 604d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen buf.append(node.toString()).append(", "); 605d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen node = node.next; 606d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 607d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return buf.toString(); 608d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 609d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 610d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 611d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 612d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Doubly linked node in a LinkedList. Most LinkedList implementations keep the 613d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * equivalent of this class private. We make it public so that references 614d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * to each node in the list can be maintained externally. 615d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 616d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Exposing this class lets us make remove operations very fast. Remove is 617d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * built into this class and only requires two reference reassignments. If 618d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * remove existed in the main LinkedList class, a linear scan would have to 619d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * be performed to find the correct node to delete. 620d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 621d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * The linked list implementation was specifically written for the Jive 622d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * cache system. While it can be used as a general purpose linked list, for 623d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * most applications, it is more suitable to use the linked list that is part 624d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * of the Java Collections package. 625d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 626d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen private static class LinkedListNode { 627d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 628d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode previous; 629d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode next; 630d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public Object object; 631d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 632d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 633d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * This class is further customized for the Jive cache system. It 634d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * maintains a timestamp of when a Cacheable object was first added to 635d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * cache. Timestamps are stored as long values and represent the number 636d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * of milliseconds passed since January 1, 1970 00:00:00.000 GMT.<p> 637d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 638d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * The creation timestamp is used in the case that the cache has a 639d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * maximum lifetime set. In that case, when 640d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * [current time] - [creation time] > [max lifetime], the object will be 641d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * deleted from cache. 642d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 643d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public long timestamp; 644d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 645d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 646d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Constructs a new linked list node. 647d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 648d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param object the Object that the node represents. 649d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param next a reference to the next LinkedListNode in the list. 650d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @param previous a reference to the previous LinkedListNode in the list. 651d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 652d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public LinkedListNode(Object object, LinkedListNode next, 653d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen LinkedListNode previous) 654d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen { 655d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.object = object; 656d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.next = next; 657d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen this.previous = previous; 658d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 659d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 660d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 661d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Removes this node from the linked list that it is a part of. 662d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 663d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public void remove() { 664d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen previous.next = next; 665d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen next.previous = previous; 666d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 667d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen 668d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen /** 669d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * Returns a String representation of the linked list node by calling the 670d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * toString method of the node's object. 671d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * 672d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen * @return a String representation of the LinkedListNode. 673d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen */ 674d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen public String toString() { 675d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen return object.toString(); 676d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 677d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen } 678d7955ce24d294fb2014c59d11fca184471056f44Shuyi Chen}