Java/Development Class/Cache
Содержание
- 1 A Least Recently Used Cache
- 2 A LRU (Least Recently Used) cache replacement policy
- 3 A Map that is size-limited using an LRU algorithm
- 4 An LRU (Least Recently Used) cache replacement policy
- 5 A random cache replacement policy
- 6 A second chance FIFO (First In First Out) cache replacement policy
- 7 Async LRU List
- 8 FIFO First In First Out cache replacement policy
- 9 Generic LRU Cache
- 10 Implementation of a Least Recently Used cache policy
- 11 LRU Cache
A Least Recently Used Cache
<source lang="java">
/**
* Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.util.LinkedHashMap; import java.util.Map; /**
* A Least Recently Used Cache * * @version $Revision: 747062 $ */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private static final long serialVersionUID = -342098639681884413L; private int maxCacheSize = 10000; public LRUCache(int maximumCacheSize) { this(maximumCacheSize, maximumCacheSize, 0.75f, true); } /** * Constructs an empty LRUCache instance with the * specified initial capacity, maximumCacheSize,load factor and ordering mode. * * @param initialCapacity the initial capacity. * @param maximumCacheSize the max capacity. * @param loadFactor the load factor. * @param accessOrder the ordering mode - true for * access-order, false for insertion-order. * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is non positive. */ public LRUCache(int initialCapacity, int maximumCacheSize, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor, accessOrder); this.maxCacheSize = maximumCacheSize; } /** * Returns the maxCacheSize. */ public int getMaxCacheSize() { return maxCacheSize; } protected boolean removeEldestEntry(Map.Entry entry) { return size() > maxCacheSize; }
}
</source>
A LRU (Least Recently Used) cache replacement policy
<source lang="java">
/*
* $Id: CacheLRU.java,v 1.10 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
import java.util.*; /**
* This class is a GenericCache subclass implementing an LRU * (Least Recently Used) cache replacement policy. In other words, * values are added to the cache until it becomes full. Once the * cache is full, when a new value is added to the cache, it replaces * the least recently used value currently in the cache. This is probably * the best general purpose cache replacement policy. * * @version @version@ * @since 1.0 * @see GenericCache */
public final class CacheLRU extends GenericCache {
private int __head = 0, __tail = 0; private int[] __next, __prev; /** * Creates a CacheLRU instance with a given cache capacity.*
* @param capacity The capacity of the cache. */ public CacheLRU(int capacity) { super(capacity); int i; __next = new int[_cache.length]; __prev = new int[_cache.length]; for(i=0; i < __next.length; i++) __next[i] = __prev[i] = -1; } /** * Same as: *
* CacheLRU(GenericCache.DEFAULT_CAPACITY); *
*/ public CacheLRU(){ this(GenericCache.DEFAULT_CAPACITY); }
private void __moveToFront(int index) { int next, prev; if(__head != index) { next = __next[index]; prev = __prev[index]; // Only the head has a prev entry that is an invalid index so // we don"t check. __next[prev] = next; // Make sure index is valid. If it isn"t, we"re at the tail // and don"t set __prev[next]. if(next >= 0) __prev[next] = prev; else __tail = prev; __prev[index] = -1; __next[index] = __head; __prev[__head] = index; __head = index; } }
public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; entry = (GenericCacheEntry)obj; // Maintain LRU property __moveToFront(entry._index); return entry._value; } return null; }
/** * Adds a value to the cache. If the cache is full, when a new value * is added to the cache, it replaces the least recently used value * in the cache (i.e., LRU). * <p> * @param key The key referencing the value added to the cache. * @param value The value to add to the cache. */ public final synchronized void addElement(Object key, Object value) { Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; // Just replace the value, but move it to the front. entry = (GenericCacheEntry)obj; entry._value = value; entry._key = key; __moveToFront(entry._index); return; } // If we haven"t filled the cache yet, place in next available spot // and move to front. if(!isFull()) { if(_numEntries > 0) { __prev[_numEntries] = __tail; __next[_numEntries] = -1; __moveToFront(_numEntries); } ++_numEntries; } else { // We replace the tail of the list. _table.remove(_cache[__tail]._key); __moveToFront(__tail); } _cache[__head]._value = value; _cache[__head]._key = key; _table.put(key, _cache[__head]); }
}
/*
* $Id: GenericCache.java,v 1.8 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* This is the base class for all cache implementations provided in the * org.apache.oro.util package. To derive a subclass from GenericCache * only the ... methods * need be overridden. * Although 4 subclasses of GenericCache are provided with this * package, users may not derive subclasses from this class. * Rather, users should create their own implmentations of the * {@link Cache} interface. * * @version @version@ * @since 1.0 * @see Cache * @see CacheLRU * @see CacheFIFO * @see CacheFIFO2 * @see CacheRandom */ abstract class GenericCache implements Cache, java.io.Serializable { /** * The default capacity to be used by the GenericCache subclasses * provided with this package. Its value is 20. */ public static final int DEFAULT_CAPACITY = 20; int _numEntries; GenericCacheEntry[] _cache; HashMap _table; /** * The primary constructor for GenericCache. It has default * access so it will only be used within the package. It initializes * _table to a Hashtable of capacity equal to the capacity argument, * _cache to an array of size equal to the capacity argument, and * _numEntries to 0. * <p> * @param capacity The maximum capacity of the cache. */ GenericCache(int capacity) { _numEntries = 0; _table = new HashMap(capacity); _cache = new GenericCacheEntry[capacity]; while(--capacity >= 0) _cache[capacity] = new GenericCacheEntry(capacity); } public abstract void addElement(Object key, Object value); public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) return ((GenericCacheEntry)obj)._value; return null; } public final Iterator keys() { return _table.keySet().iterator(); } /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public final int size() { return _numEntries; } /** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public final int capacity() { return _cache.length; } public final boolean isFull() { return (_numEntries >= _cache.length); }
}
/*
* $Id: Cache.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* An interface defining the basic functions of a cache. * * @version @version@ * @since 1.0 */ interface Cache { public void addElement(Object key, Object value); public Object getElement(Object key); /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public int size();
/** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public int capacity();
}
/* * $Id: GenericCacheEntry.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/** * A structure used to store values in a GenericCache. It * is declared with default access to limit it to use only within the * package. * * @version @version@ * @since 1.0 */ final class GenericCacheEntry implements java.io.Serializable { /** The cache array index of the entry. */ int _index; /** The value stored at this entry. */ Object _value; /** The key used to store the value. */ Object _key; GenericCacheEntry(int index) { _index = index; _value = null; _key = null; } } </source>
A Map that is size-limited using an LRU algorithm
<source lang="java">
/**
* $Revision: 1456 $ * $Date: 2005-06-01 22:04:54 -0700 (Wed, 01 Jun 2005) $ * * Copyright 2003-2005 Jive Software. * * All rights reserved. Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.Collection; import java.util.Collections; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Set;
/**
* A specialized Map that is size-limited (using an LRU algorithm) and * has an optional expiration time for cache items. The Map is thread-safe.<p> * * The algorithm for cache is as follows: a HashMap is maintained for fast * object lookup. Two linked lists are maintained: one keeps objects in the * order they are accessed from cache, the other keeps objects in the order * they were originally added to cache. When objects are added to cache, they * are first wrapped by a CacheObject which maintains the following pieces* of information:
-
*
- A pointer to the node in the linked list that maintains accessed * order for the object. Keeping a reference to the node lets us avoid * linear scans of the linked list. *
- A pointer to the node in the linked list that maintains the age * of the object in cache. Keeping a reference to the node lets us avoid * linear scans of the linked list.
* <p/> * To get an object from cache, a hash lookup is performed to get a reference * to the CacheObject that wraps the real object we are looking for. * The object is subsequently moved to the front of the accessed linked list * and any necessary cache cleanups are performed. Cache deletion and expiration * is performed as needed. * * @author Matt Tucker */
public class Cache<K, V> implements Map<K, V> {
/** * The map the keys and values are stored in. */ protected Map<K, CacheObject<V>> map; /** * Linked list to maintain order that cache objects are accessed * in, most used to least used. */ protected LinkedList lastAccessedList; /** * Linked list to maintain time that cache objects were initially added * to the cache, most recently added to oldest added. */ protected LinkedList ageList; /** * Maximum number of items the cache will hold. */ protected int maxCacheSize; /** * Maximum length of time objects can exist in cache before expiring. */ protected long maxLifetime; /** * Maintain the number of cache hits and misses. A cache hit occurs every * time the get method is called and the cache contains the requested * object. A cache miss represents the opposite occurence.<p> * * Keeping track of cache hits and misses lets one measure how efficient * the cache is; the higher the percentage of hits, the more efficient. */ protected long cacheHits, cacheMisses = 0L; /** * Create a new cache and specify the maximum size of for the cache in * bytes, and the maximum lifetime of objects. * * @param maxSize the maximum number of objects the cache will hold. -1 * means the cache has no max size. * @param maxLifetime the maximum amount of time (in ms) objects can exist in * cache before being deleted. -1 means objects never expire. */ public Cache(int maxSize, long maxLifetime) { if (maxSize == 0) { throw new IllegalArgumentException("Max cache size cannot be 0."); } this.maxCacheSize = maxSize; this.maxLifetime = maxLifetime; // Our primary data structure is a hash map. The default capacity of 11 // is too small in almost all cases, so we set it bigger. map = new HashMap<K, CacheObject<V>>(103); lastAccessedList = new LinkedList(); ageList = new LinkedList(); } public synchronized V put(K key, V value) { V oldValue = null; // Delete an old entry if it exists. if (map.containsKey(key)) { oldValue = remove(key, true); } CacheObject<V> cacheObject = new CacheObject<V>(value); map.put(key, cacheObject); // Make an entry into the cache order list. // Store the cache order list entry so that we can get back to it // during later lookups. cacheObject.lastAccessedListNode = lastAccessedList.addFirst(key); // Add the object to the age list LinkedListNode ageNode = ageList.addFirst(key); ageNode.timestamp = System.currentTimeMillis(); cacheObject.ageListNode = ageNode; // If cache is too full, remove least used cache entries until it is not too full. cullCache(); return oldValue; } public synchronized V get(Object key) { // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); CacheObject<V> cacheObject = map.get(key); if (cacheObject == null) { // The object didn"t exist in cache, so increment cache misses. cacheMisses++; return null; } // Remove the object from it"s current place in the cache order list, // and re-insert it at the front of the list. cacheObject.lastAccessedListNode.remove(); lastAccessedList.addFirst(cacheObject.lastAccessedListNode); // The object exists in cache, so increment cache hits. Also, increment // the object"s read count. cacheHits++; cacheObject.readCount++; return cacheObject.object; } public synchronized V remove(Object key) { return remove(key, false); } /* * Remove operation with a flag so we can tell coherence if the remove was * caused by cache internal processing such as eviction or loading */ public synchronized V remove(Object key, boolean internal) { //noinspection SuspiciousMethodCalls CacheObject<V> cacheObject = map.remove(key); // If the object is not in cache, stop trying to remove it. if (cacheObject == null) { return null; } // Remove from the cache order list cacheObject.lastAccessedListNode.remove(); cacheObject.ageListNode.remove(); // Remove references to linked list nodes cacheObject.ageListNode = null; cacheObject.lastAccessedListNode = null; return cacheObject.object; } public synchronized void clear() { Object[] keys = map.keySet().toArray(); for (Object key : keys) { remove(key); } // Now, reset all containers. map.clear(); lastAccessedList.clear(); ageList.clear(); cacheHits = 0; cacheMisses = 0; } public synchronized int size() { // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); return map.size(); } public synchronized boolean isEmpty() { // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); return map.isEmpty(); } public synchronized Collection<V> values() { // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); return Collections.unmodifiableCollection(new AbstractCollection<V>() { Collection<CacheObject<V>> values = map.values(); public Iterator<V> iterator() { return new Iterator<V>() { Iterator<CacheObject<V>> it = values.iterator(); public boolean hasNext() { return it.hasNext(); } public V next() { return it.next().object; } public void remove() { it.remove(); } }; } public int size() { return values.size(); } }); } public synchronized boolean containsKey(Object key) { // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); return map.containsKey(key); } public void putAll(Map<? extends K, ? extends V> map) { for (Entry<? extends K, ? extends V> entry : map.entrySet()) { V value = entry.getValue(); // If the map is another DefaultCache instance than the // entry values will be CacheObject instances that need // to be converted to the normal object form. if (value instanceof CacheObject) { //noinspection unchecked value = ((CacheObject<V>) value).object; } put(entry.getKey(), value); } } public synchronized boolean containsValue(Object value) { // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); //noinspection unchecked CacheObject<V> cacheObject = new CacheObject<V>((V) value); return map.containsValue(cacheObject); } public synchronized Set<Map.Entry<K, V>> entrySet() { // Warning -- this method returns CacheObject instances and not Objects // in the same form they were put into cache. // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); return new AbstractSet<Map.Entry<K, V>>() { private final Set<Map.Entry<K, CacheObject<V>>> set = map.entrySet(); public Iterator<Entry<K, V>> iterator() { return new Iterator<Entry<K, V>>() { private final Iterator<Entry<K, CacheObject<V>>> it = set.iterator(); public boolean hasNext() { return it.hasNext(); } public Entry<K, V> next() { Map.Entry<K, CacheObject<V>> entry = it.next(); return new AbstractMapEntry<K, V>(entry.getKey(), entry.getValue().object) { @Override public V setValue(V value) { throw new UnsupportedOperationException("Cannot set"); } }; } public void remove() { it.remove(); } }; } public int size() { return set.size(); } }; } public synchronized Set<K> keySet() { // First, clear all entries that have been in cache longer than the // maximum defined age. deleteExpiredEntries(); return Collections.unmodifiableSet(map.keySet()); } public long getCacheHits() { return cacheHits; } public long getCacheMisses() { return cacheMisses; } public int getMaxCacheSize() { return maxCacheSize; } public synchronized void setMaxCacheSize(int maxCacheSize) { this.maxCacheSize = maxCacheSize; // It"s possible that the new max size is smaller than our current cache // size. If so, we need to delete infrequently used items. cullCache(); } public long getMaxLifetime() { return maxLifetime; } public void setMaxLifetime(long maxLifetime) { this.maxLifetime = maxLifetime; } /** * Clears all entries out of cache where the entries are older than the * maximum defined age. */ protected synchronized void deleteExpiredEntries() { // Check if expiration is turned on. if (maxLifetime <= 0) { return; } // Remove all old entries. To do this, we remove objects from the end // of the linked list until they are no longer too old. We get to avoid // any hash lookups or looking at any more objects than is strictly // neccessary. LinkedListNode node = ageList.getLast(); // If there are no entries in the age list, return. if (node == null) { return; } // Determine the expireTime, which is the moment in time that elements // should expire from cache. Then, we can do an easy check to see // if the expire time is greater than the expire time. long expireTime = System.currentTimeMillis() - maxLifetime; while (expireTime > node.timestamp) { if (remove(node.object, true) == null) { System.err.println("Error attempting to remove(" + node.object.toString() + ") - cacheObject not found in cache!"); // remove from the ageList node.remove(); } // Get the next node. node = ageList.getLast(); // If there are no more entries in the age list, return. if (node == null) { return; } } } /** * Removes the least recently used elements if the cache size is greater than * or equal to the maximum allowed size until the cache is at least 10% empty. */ protected synchronized void cullCache() { // Check if a max cache size is defined. if (maxCacheSize < 0) { return; } // See if the cache is too big. If so, clean out cache until it"s 10% free. if (map.size() > maxCacheSize) { // First, delete any old entries to see how much memory that frees. deleteExpiredEntries(); // Next, delete the least recently used elements until 10% of the cache // has been freed. int desiredSize = (int) (maxCacheSize * .90); for (int i=map.size(); i>desiredSize; i--) { // Get the key and invoke the remove method on it. if (remove(lastAccessedList.getLast().object, true) == null) { System.err.println("Error attempting to cullCache with remove(" + lastAccessedList.getLast().object.toString() + ") - " + "cacheObject not found in cache!"); lastAccessedList.getLast().remove(); } } } } /** * Wrapper for all objects put into cache. It"s primary purpose is to maintain * references to the linked lists that maintain the creation time of the object * and the ordering of the most used objects. * * This class is optimized for speed rather than strictly correct encapsulation. */ private static class CacheObject<V> { /** * Underlying object wrapped by the CacheObject. */ public V object; /** * A reference to the node in the cache order list. We keep the reference * here to avoid linear scans of the list. Every time the object is * accessed, the node is removed from its current spot in the list and * moved to the front. */ public LinkedListNode lastAccessedListNode; /** * A reference to the node in the age order list. We keep the reference * here to avoid linear scans of the list. The reference is used if the * object has to be deleted from the list. */ public LinkedListNode ageListNode; /** * A count of the number of times the object has been read from cache. */ public int readCount = 0; /** * Creates a new cache object wrapper. * * @param object the underlying Object to wrap. */ public CacheObject(V object) { this.object = object; } public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof CacheObject)) { return false; } final CacheObject cacheObject = (CacheObject) o; return object.equals(cacheObject.object); } public int hashCode() { return object.hashCode(); } } /** * Simple LinkedList implementation. The main feature is that list nodes * are public, which allows very fast delete operations when one has a * reference to the node that is to be deleted.<p> */ private static class LinkedList { /** * The root of the list keeps a reference to both the first and last * elements of the list. */ private LinkedListNode head = new LinkedListNode("head", null, null); /** * Creates a new linked list. */ public LinkedList() { head.next = head.previous = head; } /** * Returns the first linked list node in the list. * * @return the first element of the list. */ public LinkedListNode getFirst() { LinkedListNode node = head.next; if (node == head) { return null; } return node; } /** * Returns the last linked list node in the list. * * @return the last element of the list. */ public LinkedListNode getLast() { LinkedListNode node = head.previous; if (node == head) { return null; } return node; } /** * Adds a node to the beginning of the list. * * @param node the node to add to the beginning of the list. * @return the node */ public LinkedListNode addFirst(LinkedListNode node) { node.next = head.next; node.previous = head; node.previous.next = node; node.next.previous = node; return node; } /** * Adds an object to the beginning of the list by automatically creating a * a new node and adding it to the beginning of the list. * * @param object the object to add to the beginning of the list. * @return the node created to wrap the object. */ public LinkedListNode addFirst(Object object) { LinkedListNode node = new LinkedListNode(object, head.next, head); node.previous.next = node; node.next.previous = node; return node; } /** * Adds an object to the end of the list by automatically creating a * a new node and adding it to the end of the list. * * @param object the object to add to the end of the list. * @return the node created to wrap the object. */ public LinkedListNode addLast(Object object) { LinkedListNode node = new LinkedListNode(object, head, head.previous); node.previous.next = node; node.next.previous = node; return node; } /** * Erases all elements in the list and re-initializes it. */ public void clear() { //Remove all references in the list. LinkedListNode node = getLast(); while (node != null) { node.remove(); node = getLast(); } //Re-initialize. head.next = head.previous = head; } /** * Returns a String representation of the linked list with a comma * delimited list of all the elements in the list. * * @return a String representation of the LinkedList. */ public String toString() { LinkedListNode node = head.next; StringBuilder buf = new StringBuilder(); while (node != head) { buf.append(node.toString()).append(", "); node = node.next; } return buf.toString(); } } /** * Doubly linked node in a LinkedList. Most LinkedList implementations keep the * equivalent of this class private. We make it public so that references * to each node in the list can be maintained externally. * * Exposing this class lets us make remove operations very fast. Remove is * built into this class and only requires two reference reassignments. If * remove existed in the main LinkedList class, a linear scan would have to * be performed to find the correct node to delete. * * The linked list implementation was specifically written for the Jive * cache system. While it can be used as a general purpose linked list, for * most applications, it is more suitable to use the linked list that is part * of the Java Collections package. */ private static class LinkedListNode { public LinkedListNode previous; public LinkedListNode next; public Object object; /** * This class is further customized for the Jive cache system. It * maintains a timestamp of when a Cacheable object was first added to * cache. Timestamps are stored as long values and represent the number * of milliseconds passed since January 1, 1970 00:00:00.000 GMT.<p> * * The creation timestamp is used in the case that the cache has a * maximum lifetime set. In that case, when * [current time] - [creation time] > [max lifetime], the object will be * deleted from cache. */ public long timestamp; /** * Constructs a new linked list node. * * @param object the Object that the node represents. * @param next a reference to the next LinkedListNode in the list. * @param previous a reference to the previous LinkedListNode in the list. */ public LinkedListNode(Object object, LinkedListNode next, LinkedListNode previous) { this.object = object; this.next = next; this.previous = previous; } /** * Removes this node from the linked list that it is a part of. */ public void remove() { previous.next = next; next.previous = previous; } /** * Returns a String representation of the linked list node by calling the * toString method of the node"s object. * * @return a String representation of the LinkedListNode. */ public String toString() { return object.toString(); } }
} //GenericsNote: Converted. /*
* Copyright 2003-2004 The Apache Software Foundation * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
/**
* Abstract Pair class to assist with creating correct Map Entry implementations. * * @author James Strachan * @author Michael A. Smith * @author Neil O"Toole * @author Matt Hall, John Watkinson, Stephen Colebourne * @version $Revision: 1.1 $ $Date: 2005/10/11 17:05:32 $ * @since Commons Collections 3.0 */ abstract class AbstractMapEntry <K,V> extends AbstractKeyValue<K, V> implements Map.Entry<K, V> { /** * Constructs a new entry with the given key and given value. * * @param key the key for the entry, may be null * @param value the value for the entry, may be null */ protected AbstractMapEntry(K key, V value) { super(key, value); } // Map.Entry interface //------------------------------------------------------------------------- /** * Sets the value stored in this Map Entry. * <p/> * This Map Entry is not connected to a Map, so only the local data is changed. * * @param value the new value * @return the previous value */ public V setValue(V value) { V answer = this.value; this.value = value; return answer; } /** * Compares this Map Entry with another Map Entry. * <p/> * Implemented per API documentation of {@link java.util.Map.Entry#equals(Object)} * * @param obj the object to compare to * @return true if equal key and value */ public boolean equals(Object obj) { if (obj == this) { return true; } if (obj instanceof Map.Entry == false) { return false; } Map.Entry other = (Map.Entry) obj; return (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) && (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue())); } /** * Gets a hashCode compatible with the equals method. * <p/> * Implemented per API documentation of {@link java.util.Map.Entry#hashCode()} * * @return a suitable hash code */ public int hashCode() { return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()); }
} //GenericsNote: Converted.
/* * Copyright 2003-2004 The Apache Software Foundation * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
/** * Abstract pair class to assist with creating KeyValue and MapEntry implementations. * * @author James Strachan * @author Michael A. Smith * @author Neil O"Toole * @author Matt Hall, John Watkinson, Stephen Colebourne * @version $Revision: 1.1 $ $Date: 2005/10/11 17:05:32 $ * @since Commons Collections 3.0 */ abstract class AbstractKeyValue <K,V> implements KeyValue<K, V> { /** * The key */ protected K key; /** * The value */ protected V value; /** * Constructs a new pair with the specified key and given value. * * @param key the key for the entry, may be null * @param value the value for the entry, may be null */ protected AbstractKeyValue(K key, V value) { super(); this.key = key; this.value = value; } /** * Gets the key from the pair. * * @return the key */ public K getKey() { return key; } /** * Gets the value from the pair. * * @return the value */ public V getValue() { return value; } /** * Gets a debugging String view of the pair. * * @return a String view of the entry */ public String toString() { return new StringBuilder().append(getKey()).append("=").append(getValue()).toString(); } }
//GenericsNote: Converted.
/* * Copyright 2003-2004 The Apache Software Foundation * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /** * Defines a simple key value pair. * <p/> * A Map Entry has considerable additional semantics over and above a simple * key-value pair. This interface defines the minimum key value, with just the * two get methods. * * @author Matt Hall, John Watkinson, Stephen Colebourne * @version $Revision: 1.1 $ $Date: 2005/10/11 17:05:19 $ * @since Commons Collections 3.0 */ interface KeyValue <K,V> { /** * Gets the key from the pair. * * @return the key */ K getKey(); /** * Gets the value from the pair. * * @return the value */ V getValue(); } </source>
An LRU (Least Recently Used) cache replacement policy
<source lang="java">
/*
* $Id: CacheLRU.java,v 1.10 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
import java.util.*; /**
* This class is a GenericCache subclass implementing an LRU * (Least Recently Used) cache replacement policy. In other words, * values are added to the cache until it becomes full. Once the * cache is full, when a new value is added to the cache, it replaces * the least recently used value currently in the cache. This is probably * the best general purpose cache replacement policy. * * @version @version@ * @since 1.0 * @see GenericCache */
public final class CacheLRU extends GenericCache {
private int __head = 0, __tail = 0; private int[] __next, __prev; /** * Creates a CacheLRU instance with a given cache capacity. * <p> * @param capacity The capacity of the cache. */ public CacheLRU(int capacity) { super(capacity); int i; __next = new int[_cache.length]; __prev = new int[_cache.length]; for(i=0; i < __next.length; i++) __next[i] = __prev[i] = -1; }
/** * Same as:*
* CacheLRU(GenericCache.DEFAULT_CAPACITY); *
*/ public CacheLRU(){ this(GenericCache.DEFAULT_CAPACITY); }
private void __moveToFront(int index) { int next, prev; if(__head != index) { next = __next[index]; prev = __prev[index]; // Only the head has a prev entry that is an invalid index so // we don"t check. __next[prev] = next; // Make sure index is valid. If it isn"t, we"re at the tail // and don"t set __prev[next]. if(next >= 0) __prev[next] = prev; else __tail = prev; __prev[index] = -1; __next[index] = __head; __prev[__head] = index; __head = index; } }
public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; entry = (GenericCacheEntry)obj; // Maintain LRU property __moveToFront(entry._index); return entry._value; } return null; }
/** * Adds a value to the cache. If the cache is full, when a new value * is added to the cache, it replaces the least recently used value * in the cache (i.e., LRU). * <p> * @param key The key referencing the value added to the cache. * @param value The value to add to the cache. */ public final synchronized void addElement(Object key, Object value) { Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; // Just replace the value, but move it to the front. entry = (GenericCacheEntry)obj; entry._value = value; entry._key = key; __moveToFront(entry._index); return; } // If we haven"t filled the cache yet, place in next available spot // and move to front. if(!isFull()) { if(_numEntries > 0) { __prev[_numEntries] = __tail; __next[_numEntries] = -1; __moveToFront(_numEntries); } ++_numEntries; } else { // We replace the tail of the list. _table.remove(_cache[__tail]._key); __moveToFront(__tail); } _cache[__head]._value = value; _cache[__head]._key = key; _table.put(key, _cache[__head]); }
}
/*
* $Id: GenericCache.java,v 1.8 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* This is the base class for all cache implementations provided in the * org.apache.oro.util package. To derive a subclass from GenericCache * only the ... methods * need be overridden. * Although 4 subclasses of GenericCache are provided with this * package, users may not derive subclasses from this class. * Rather, users should create their own implmentations of the * {@link Cache} interface. * * @version @version@ * @since 1.0 * @see Cache * @see CacheLRU * @see CacheFIFO * @see CacheFIFO2 * @see CacheRandom */ abstract class GenericCache implements Cache, java.io.Serializable { /** * The default capacity to be used by the GenericCache subclasses * provided with this package. Its value is 20. */ public static final int DEFAULT_CAPACITY = 20; int _numEntries; GenericCacheEntry[] _cache; HashMap _table; /** * The primary constructor for GenericCache. It has default * access so it will only be used within the package. It initializes * _table to a Hashtable of capacity equal to the capacity argument, * _cache to an array of size equal to the capacity argument, and * _numEntries to 0. * <p> * @param capacity The maximum capacity of the cache. */ GenericCache(int capacity) { _numEntries = 0; _table = new HashMap(capacity); _cache = new GenericCacheEntry[capacity]; while(--capacity >= 0) _cache[capacity] = new GenericCacheEntry(capacity); } public abstract void addElement(Object key, Object value); public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) return ((GenericCacheEntry)obj)._value; return null; } public final Iterator keys() { return _table.keySet().iterator(); } /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public final int size() { return _numEntries; } /** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public final int capacity() { return _cache.length; } public final boolean isFull() { return (_numEntries >= _cache.length); }
}
/* * $Id: Cache.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/** * An interface defining the basic functions of a cache. * * @version @version@ * @since 1.0 */ interface Cache { public void addElement(Object key, Object value); public Object getElement(Object key); /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public int size();
/** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public int capacity(); } /* * $Id: GenericCacheEntry.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/** * A structure used to store values in a GenericCache. It * is declared with default access to limit it to use only within the * package. * * @version @version@ * @since 1.0 */ final class GenericCacheEntry implements java.io.Serializable { /** The cache array index of the entry. */ int _index; /** The value stored at this entry. */ Object _value; /** The key used to store the value. */ Object _key; GenericCacheEntry(int index) { _index = index; _value = null; _key = null; } } </source>
A random cache replacement policy
<source lang="java">
/*
* $Id: CacheRandom.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
import java.util.*; /**
* This class is a GenericCache subclass implementing a random * cache replacement policy. In other words, * values are added to the cache until it becomes full. Once the * cache is full, when a new value is added to the cache, it replaces * a randomly selected value in the cache. * * @version @version@ * @since 1.0 * @see GenericCache */
public final class CacheRandom extends GenericCache {
private Random __random; /** * Creates a CacheRandom instance with a given cache capacity. * <p> * @param capacity The capacity of the cache. */ public CacheRandom(int capacity) { super(capacity); __random = new Random(System.currentTimeMillis()); } /** * Same as:*
* CacheRandom(GenericCache.DEFAULT_CAPACITY); *
*/ public CacheRandom(){ this(GenericCache.DEFAULT_CAPACITY); } /** * Adds a value to the cache. If the cache is full, when a new value * is added to the cache, it replaces the first of the current values * in the cache to have been added (i.e., Random). * <p> * @param key The key referencing the value added to the cache. * @param value The value to add to the cache. */ public final synchronized void addElement(Object key, Object value) { int index; Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; // Just replace the value. entry = (GenericCacheEntry)obj; entry._value = value; entry._key = key; return; } // Expression is not in cache. // If we haven"t filled the cache yet, put it at the end. if(!isFull()) { index = _numEntries; ++_numEntries; } else { // Otherwise, replace a random entry. index = (int)(_cache.length*__random.nextFloat()); _table.remove(_cache[index]._key); } _cache[index]._value = value; _cache[index]._key = key; _table.put(key, _cache[index]); }
}
/*
* $Id: GenericCache.java,v 1.8 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* This is the base class for all cache implementations provided in the * org.apache.oro.util package. To derive a subclass from GenericCache * only the ... methods * need be overridden. * Although 4 subclasses of GenericCache are provided with this * package, users may not derive subclasses from this class. * Rather, users should create their own implmentations of the * {@link Cache} interface. * * @version @version@ * @since 1.0 * @see Cache * @see CacheLRU * @see CacheFIFO * @see CacheFIFO2 * @see CacheRandom */ abstract class GenericCache implements Cache, java.io.Serializable { /** * The default capacity to be used by the GenericCache subclasses * provided with this package. Its value is 20. */ public static final int DEFAULT_CAPACITY = 20; int _numEntries; GenericCacheEntry[] _cache; HashMap _table; /** * The primary constructor for GenericCache. It has default * access so it will only be used within the package. It initializes * _table to a Hashtable of capacity equal to the capacity argument, * _cache to an array of size equal to the capacity argument, and * _numEntries to 0. * <p> * @param capacity The maximum capacity of the cache. */ GenericCache(int capacity) { _numEntries = 0; _table = new HashMap(capacity); _cache = new GenericCacheEntry[capacity]; while(--capacity >= 0) _cache[capacity] = new GenericCacheEntry(capacity); } public abstract void addElement(Object key, Object value); public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) return ((GenericCacheEntry)obj)._value; return null; } public final Iterator keys() { return _table.keySet().iterator(); } /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public final int size() { return _numEntries; } /** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public final int capacity() { return _cache.length; } public final boolean isFull() { return (_numEntries >= _cache.length); }
}
/*
* $Id: Cache.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* An interface defining the basic functions of a cache. * * @version @version@ * @since 1.0 */ interface Cache { public void addElement(Object key, Object value); public Object getElement(Object key); /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public int size();
/** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public int capacity();
}
/* * $Id: GenericCacheEntry.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/** * A structure used to store values in a GenericCache. It * is declared with default access to limit it to use only within the * package. * * @version @version@ * @since 1.0 */ final class GenericCacheEntry implements java.io.Serializable { /** The cache array index of the entry. */ int _index; /** The value stored at this entry. */ Object _value; /** The key used to store the value. */ Object _key; GenericCacheEntry(int index) { _index = index; _value = null; _key = null; } } </source>
A second chance FIFO (First In First Out) cache replacement policy
<source lang="java">
/*
* $Id: CacheFIFO2.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
import java.util.*; /**
* This class is a GenericCache subclass implementing a second * chance FIFO (First In First Out) cache replacement policy. In other * words, values are added to the cache until the cache becomes full. * Once the cache is full, when a new value is added to the cache, it * replaces the first of the current values in the cache to have been * added, unless that value has been used recently (generally * between the last cache replacement and now). * If the value to be replaced has been used, it is given * a second chance, and the next value in the cache is tested for * replacement in the same manner. If all the values are given a * second chance, then the original pattern selected for replacement is * replaced. * * @version @version@ * @since 1.0 * @see GenericCache */
public final class CacheFIFO2 extends GenericCache {
private int __current = 0; private boolean[] __tryAgain; /** * Creates a CacheFIFO2 instance with a given cache capacity. * <p> * @param capacity The capacity of the cache. */ public CacheFIFO2(int capacity) { super(capacity); __tryAgain = new boolean[_cache.length]; }
/** * Same as:*
* CacheFIFO2(GenericCache.DEFAULT_CAPACITY); *
*/ public CacheFIFO2(){ this(GenericCache.DEFAULT_CAPACITY); }
public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; entry = (GenericCacheEntry)obj; __tryAgain[entry._index] = true; return entry._value; } return null; }
/** * Adds a value to the cache. If the cache is full, when a new value * is added to the cache, it replaces the first of the current values * in the cache to have been added (i.e., FIFO2). * <p> * @param key The key referencing the value added to the cache. * @param value The value to add to the cache. */ public final synchronized void addElement(Object key, Object value) { int index; Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; // Just replace the value. Technically this upsets the FIFO2 ordering, // but it"s expedient. entry = (GenericCacheEntry)obj; entry._value = value; entry._key = key; // Set the try again value to compensate. __tryAgain[entry._index] = true; return; } // If we haven"t filled the cache yet, put it at the end. if(!isFull()) { index = _numEntries; ++_numEntries; } else { // Otherwise, find the next slot that doesn"t have a second chance. index = __current; while(__tryAgain[index]) { __tryAgain[index] = false; if(++index >= __tryAgain.length) index = 0; } __current = index + 1; if(__current >= _cache.length) __current = 0; _table.remove(_cache[index]._key); } _cache[index]._value = value; _cache[index]._key = key; _table.put(key, _cache[index]); }
}
/*
* $Id: GenericCache.java,v 1.8 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* This is the base class for all cache implementations provided in the * org.apache.oro.util package. To derive a subclass from GenericCache * only the ... methods * need be overridden. * Although 4 subclasses of GenericCache are provided with this * package, users may not derive subclasses from this class. * Rather, users should create their own implmentations of the * {@link Cache} interface. * * @version @version@ * @since 1.0 * @see Cache * @see CacheLRU * @see CacheFIFO * @see CacheFIFO2 * @see CacheRandom */ abstract class GenericCache implements Cache, java.io.Serializable { /** * The default capacity to be used by the GenericCache subclasses * provided with this package. Its value is 20. */ public static final int DEFAULT_CAPACITY = 20; int _numEntries; GenericCacheEntry[] _cache; HashMap _table; /** * The primary constructor for GenericCache. It has default * access so it will only be used within the package. It initializes * _table to a Hashtable of capacity equal to the capacity argument, * _cache to an array of size equal to the capacity argument, and * _numEntries to 0. * <p> * @param capacity The maximum capacity of the cache. */ GenericCache(int capacity) { _numEntries = 0; _table = new HashMap(capacity); _cache = new GenericCacheEntry[capacity]; while(--capacity >= 0) _cache[capacity] = new GenericCacheEntry(capacity); } public abstract void addElement(Object key, Object value); public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) return ((GenericCacheEntry)obj)._value; return null; } public final Iterator keys() { return _table.keySet().iterator(); } /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public final int size() { return _numEntries; } /** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public final int capacity() { return _cache.length; } public final boolean isFull() { return (_numEntries >= _cache.length); }
}
/* * $Id: Cache.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/** * An interface defining the basic functions of a cache. * * @version @version@ * @since 1.0 */ interface Cache { public void addElement(Object key, Object value); public Object getElement(Object key); /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public int size();
/** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public int capacity(); } /* * $Id: GenericCacheEntry.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/** * A structure used to store values in a GenericCache. It * is declared with default access to limit it to use only within the * package. * * @version @version@ * @since 1.0 */ final class GenericCacheEntry implements java.io.Serializable { /** The cache array index of the entry. */ int _index; /** The value stored at this entry. */ Object _value; /** The key used to store the value. */ Object _key; GenericCacheEntry(int index) { _index = index; _value = null; _key = null; } } </source>
Async LRU List
<source lang="java">
// LRUList.java // $Id: LRUList.java,v 1.7 2000/08/16 21:37:58 ylafon Exp $ // (c) COPYRIGHT MIT and INRIA, 1996. // Please first read the full copyright statement in file COPYRIGHT.html // AsyncLRUList.java // $Id: AsyncLRUList.java,v 1.10 1998/01/22 14:24:58 bmahe Exp $ // (c) COPYRIGHT MIT and INRIA, 1996. // Please first read the full copyright statement in file COPYRIGHT.html
// All locks allocated from left to right public class AsyncLRUList extends LRUList {
public final synchronized void toHead(LRUAble node) { _remove(node) ; if ( head.next != null ) { node.setNext(head.next) ; head.next.setPrev(node) ; node.setPrev(head) ; head.next = node ; } else { node.setNext(head.next) ; // head.next.setPrev(node) ; node.setPrev(head) ; head.next = node ; } } public final synchronized void toTail(LRUAble node) { _remove(node) ; if ( tail.prev != null ) { node.setPrev(tail.prev) ; tail.prev.setNext(node) ; node.setNext(tail) ; tail.prev = node ; } else { node.setPrev(tail.prev) ; // tail.prev.setNext(node) ; node.setNext(tail) ; tail.prev = node ; } } private final synchronized void _remove(LRUAble node) { LRUAble itsPrev = node.getPrev() ; if(itsPrev==null) return ; LRUAble itsNext = node.getNext() ; node.setNext(null); node.setPrev(null); itsPrev.setNext(itsNext) ; if ( itsNext == null ) return; itsNext.setPrev(itsPrev) ; } public final synchronized LRUAble remove(LRUAble node) { _remove(node) ; node.setNext((LRUAble) null) ; node.setPrev((LRUAble) null) ; return node ; } public final synchronized LRUAble getTail() { if ( tail.prev == null ) return null; LRUAble prev = tail.prev ; return (prev == head) ? null : prev; } public final synchronized LRUAble getHead() { LRUAble next = head.next; return (next == tail) ? null : next; } public final synchronized LRUAble removeTail() { return (tail.prev != head) ? remove(tail.prev) : null; } public final synchronized LRUAble getNext(LRUAble node) { LRUAble next = node.getNext(); return ((next == tail) || (next == head)) ? null : next; } public final synchronized LRUAble getPrev(LRUAble node) { LRUAble prev = node.getPrev(); return ((prev == tail) || (prev == head)) ? null : prev; }
}
abstract class LRUList { protected LRUNode head ; protected LRUNode tail ; public LRUList() { this.head = new LRUNode() ; this.tail = new LRUNode() ; head.prev = null ; head.next = tail ; tail.prev = head ; tail.next = null ; } /** * Moves node to front of list. It can be a new node, or it can be * an existing node. * @param node the node */ public abstract void toHead(LRUAble node) ; /** * Moves node to back of list. It can be a new node, or it can be * an existing node. * @param node the node */ public abstract void toTail(LRUAble node) ; /** * Removes node if it"s in list. * Does nothing if it"s not. * When a node is removed, both its links are set to null. * @param node The node to remove * @return the same node */ public abstract LRUAble remove(LRUAble node) ; /** * Obtain the backmost node. * @return the backmost node, or null if list is empty */ public abstract LRUAble getTail() ; /** * Obtain the frontmost node. * @return the frontmost node, or null if list is empty */ public abstract LRUAble getHead() ; /** * Obtain the backmost node, and remove it from list too. * @return the backmost node, or null if list is empty */ public abstract LRUAble removeTail() ; /** * Get the next node of this list. * @return The next node, or null if this one was * last. */ abstract public LRUAble getNext(LRUAble node) ; /** * Get the previous node of this list. * @return The previous node, or null if this one was * last. */ abstract public LRUAble getPrev(LRUAble node) ;
} //LRUNode.java //$Id: LRUNode.java,v 1.4 2003/02/14 16:14:56 ylafon Exp $ //(c) COPYRIGHT MIT and INRIA, 1996. //Please first read the full copyright statement in file COPYRIGHT.html class LRUNode implements LRUAble {
protected LRUAble prev ; protected LRUAble next ; public LRUNode() {
this.prev = null ; this.next = null ;
} public LRUNode(LRUAble prev,LRUAble next) {
this.prev = prev ; this.next = next ;
} public LRUAble getNext() {
return next ;
} public LRUAble getPrev() {
return prev;
} public void setPrev(LRUAble prev) {
this.prev = prev ;
} public void setNext(LRUAble next) {
this.next = next ;
}
} //LRUAble.java //$Id: LRUAble.java,v 1.3 1998/01/22 14:25:09 bmahe Exp $ //(c) COPYRIGHT MIT and INRIA, 1997. //Please first read the full copyright statement in file COPYRIGHT.html interface LRUAble {
public LRUAble getNext() ; public LRUAble getPrev() ; public void setNext(LRUAble next) ; public void setPrev(LRUAble prev) ;
}
</source>
FIFO First In First Out cache replacement policy
<source lang="java">
import java.util.*; /**
* This class is a GenericCache subclass implementing a second * chance FIFO (First In First Out) cache replacement policy. In other * words, values are added to the cache until the cache becomes full. * Once the cache is full, when a new value is added to the cache, it * replaces the first of the current values in the cache to have been * added, unless that value has been used recently (generally * between the last cache replacement and now). * If the value to be replaced has been used, it is given * a second chance, and the next value in the cache is tested for * replacement in the same manner. If all the values are given a * second chance, then the original pattern selected for replacement is * replaced. * * @version @version@ * @since 1.0 * @see GenericCache */
public final class CacheFIFO2 extends GenericCache {
private int __current = 0; private boolean[] __tryAgain; /** * Creates a CacheFIFO2 instance with a given cache capacity. * <p> * @param capacity The capacity of the cache. */ public CacheFIFO2(int capacity) { super(capacity); __tryAgain = new boolean[_cache.length]; }
/** * Same as:*
* CacheFIFO2(GenericCache.DEFAULT_CAPACITY); *
*/ public CacheFIFO2(){ this(GenericCache.DEFAULT_CAPACITY); }
public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; entry = (GenericCacheEntry)obj; __tryAgain[entry._index] = true; return entry._value; } return null; }
/** * Adds a value to the cache. If the cache is full, when a new value * is added to the cache, it replaces the first of the current values * in the cache to have been added (i.e., FIFO2). * <p> * @param key The key referencing the value added to the cache. * @param value The value to add to the cache. */ public final synchronized void addElement(Object key, Object value) { int index; Object obj; obj = _table.get(key); if(obj != null) { GenericCacheEntry entry; // Just replace the value. Technically this upsets the FIFO2 ordering, // but it"s expedient. entry = (GenericCacheEntry)obj; entry._value = value; entry._key = key; // Set the try again value to compensate. __tryAgain[entry._index] = true; return; } // If we haven"t filled the cache yet, put it at the end. if(!isFull()) { index = _numEntries; ++_numEntries; } else { // Otherwise, find the next slot that doesn"t have a second chance. index = __current; while(__tryAgain[index]) { __tryAgain[index] = false; if(++index >= __tryAgain.length) index = 0; } __current = index + 1; if(__current >= _cache.length) __current = 0; _table.remove(_cache[index]._key); } _cache[index]._value = value; _cache[index]._key = key; _table.put(key, _cache[index]); }
} /*
* $Id: GenericCache.java,v 1.8 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* This is the base class for all cache implementations provided in the * org.apache.oro.util package. To derive a subclass from GenericCache * only the ... methods * need be overridden. * Although 4 subclasses of GenericCache are provided with this * package, users may not derive subclasses from this class. * Rather, users should create their own implmentations of the * {@link Cache} interface. * * @version @version@ * @since 1.0 * @see Cache * @see CacheLRU * @see CacheFIFO * @see CacheFIFO2 * @see CacheRandom */ abstract class GenericCache implements Cache, java.io.Serializable { /** * The default capacity to be used by the GenericCache subclasses * provided with this package. Its value is 20. */ public static final int DEFAULT_CAPACITY = 20; int _numEntries; GenericCacheEntry[] _cache; HashMap _table; /** * The primary constructor for GenericCache. It has default * access so it will only be used within the package. It initializes * _table to a Hashtable of capacity equal to the capacity argument, * _cache to an array of size equal to the capacity argument, and * _numEntries to 0. * <p> * @param capacity The maximum capacity of the cache. */ GenericCache(int capacity) { _numEntries = 0; _table = new HashMap(capacity); _cache = new GenericCacheEntry[capacity]; while(--capacity >= 0) _cache[capacity] = new GenericCacheEntry(capacity); } public abstract void addElement(Object key, Object value); public synchronized Object getElement(Object key) { Object obj; obj = _table.get(key); if(obj != null) return ((GenericCacheEntry)obj)._value; return null; } public final Iterator keys() { return _table.keySet().iterator(); } /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public final int size() { return _numEntries; } /** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public final int capacity() { return _cache.length; } public final boolean isFull() { return (_numEntries >= _cache.length); }
}
/*
* $Id: Cache.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/**
* An interface defining the basic functions of a cache. * * @version @version@ * @since 1.0 */ interface Cache { public void addElement(Object key, Object value); public Object getElement(Object key); /** * Returns the number of elements in the cache, not to be confused with * the {@link #capacity()} which returns the number * of elements that can be held in the cache at one time. * <p> * @return The current size of the cache (i.e., the number of elements * currently cached). */ public int size();
/** * Returns the maximum number of elements that can be cached at one time. * <p> * @return The maximum number of elements that can be cached at one time. */ public int capacity();
}
/* * $Id: GenericCacheEntry.java,v 1.7 2003/11/07 20:16:25 dfs Exp $ * * * The Apache Software License, Version 1.1 * * Copyright (c) 2000 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" * must not be used to endorse or promote products derived from this * software without prior written permission. For written * permission, please contact apache@apache.org. * * 5. Products derived from this software may not be called "Apache" * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their * name, without prior written permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS"" AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. */
/** * A structure used to store values in a GenericCache. It * is declared with default access to limit it to use only within the * package. * * @version @version@ * @since 1.0 */ final class GenericCacheEntry implements java.io.Serializable { /** The cache array index of the entry. */ int _index; /** The value stored at this entry. */ Object _value; /** The key used to store the value. */ Object _key; GenericCacheEntry(int index) { _index = index; _value = null; _key = null; } } </source>
Generic LRU Cache
<source lang="java">
/*
* Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */
import java.util.Hashtable; /**
* This class implements a Generic LRU Cache * * * @author Ignacio J. Ortega * */
public class LRUCache {
class CacheNode { CacheNode prev; CacheNode next; Object value; Object key; CacheNode() { } }
public LRUCache(int i) { currentSize = 0; cacheSize = i; nodes = new Hashtable(i); } public Object get(Object key) { CacheNode node = (CacheNode)nodes.get(key); if(node != null) { moveToHead(node); return node.value; } else { return null; } } public void put(Object key, Object value) { CacheNode node = (CacheNode)nodes.get(key); if(node == null) { if(currentSize >= cacheSize) { if(last != null) nodes.remove(last.key); removeLast(); } else { currentSize++; } node = new CacheNode(); } node.value = value; node.key = key; moveToHead(node); nodes.put(key, node); } public Object remove(Object key) { CacheNode node = (CacheNode)nodes.get(key); if (node != null) { if (node.prev != null) { node.prev.next = node.next; } if (node.next != null) { node.next.prev = node.prev; } if (last == node) last = node.prev; if (first == node) first = node.next; } return node; } public void clear() { first = null; last = null; } private void removeLast() { if(last != null) { if(last.prev != null) last.prev.next = null; else first = null; last = last.prev; } } private void moveToHead(CacheNode node) { if(node == first) return; if(node.prev != null) node.prev.next = node.next; if(node.next != null) node.next.prev = node.prev; if(last == node) last = node.prev; if(first != null) { node.next = first; first.prev = node; } first = node; node.prev = null; if(last == null) last = first; } private int cacheSize; private Hashtable nodes; private int currentSize; private CacheNode first; private CacheNode last;
}
</source>
Implementation of a Least Recently Used cache policy
<source lang="java">
/*
* JBoss, Home of Professional Open Source * Copyright 2005, JBoss Inc., and individual contributors as indicated * by the @authors tag. See the copyright.txt in the distribution for a * full listing of individual contributors. * * This is free software; you can redistribute it and/or modify it * under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this software; if not, write to the Free * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA * 02110-1301 USA, or see the FSF site: http://www.fsf.org. */
/*
* JBoss, Home of Professional Open Source * Copyright 2005, JBoss Inc., and individual contributors as indicated * by the @authors tag. See the copyright.txt in the distribution for a * full listing of individual contributors. * * This is free software; you can redistribute it and/or modify it * under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this software; if not, write to the Free * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA * 02110-1301 USA, or see the FSF site: http://www.fsf.org. */
import java.util.HashMap; import java.util.Map; /**
* Implementation of a Least Recently Used cache policy. * * @author * @version $Revision: 2787 $ */
interface CachePolicy {
/** * Returns the object paired with the specified key if it"s present in the * cache, otherwise must return null.
* Implementations of this method must have complexity of order O(1). * Differently from {@link #peek} this method not only return whether the * object is present in the cache or not, but also applies the implemented * policy that will "refresh" the cached object in the cache, because this * cached object was really requested. * * @param key * the key paired with the object * @return the object * @see #peek */ Object get(Object key); /** * Returns the object paired with the specified key if it"s present in the * cache, otherwise must return null.
* Implementations of this method must have complexity of order O(1). This * method should not apply the implemented caching policy to the object paired * with the given key, so that a client can query if an object is cached * without "refresh" its cache status. Real requests for the object must be * done using {@link #get}. * * @param key * the key paired with the object * @see #get * @return the object */ Object peek(Object key); /** * Inserts the specified object into the cache following the implemented * policy.
* Implementations of this method must have complexity of order O(1). * * @param key * the key paired with the object * @param object * the object to cache * @see #remove */ void insert(Object key, Object object); /** * Remove the cached object paired with the specified key.
* Implementations of this method must have complexity of order O(1). * * @param key * the key paired with the object * @see #insert */ void remove(Object key); /** * Flushes the cached objects from the cache. */ void flush(); /** * @return the size of the cache */ int size(); void create() throws Exception; void start() throws Exception; void stop(); void destroy();
}
</source>
LRU Cache
<source lang="java">
/*
* XAPool: Open Source XA JDBC Pool * Copyright (C) 2003 Objectweb.org * Initial Developer: Lutris Technologies Inc. * Contact: xapool-public@lists.debian-sf.objectweb.org * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 * USA */
import java.util.Hashtable; import java.util.LinkedList; import java.util.ArrayList; import java.util.List; import java.util.Iterator; import java.util.Enumeration; /**
* Simple implementation of a cache, using Least Recently Used algorithm * for discarding members when the cache fills up */
public class LRUCache {
/** The cache */ private Hashtable cache = new Hashtable(); /** The linked list to keep track of least/most recently used */ private LinkedList lru = new LinkedList(); /** The maximum size of the cache */ private int maxSize;
/** * Constructor */ public LRUCache(int maxSize) { this.maxSize = maxSize; } public int LRUSize() { return lru.size(); } public int cacheSize() { return cache.size(); } /** * Puts a new object in the cache. If the cache is full, it removes * the least recently used object. The new object becomes the most * recently used object. */ public void put(Object key, Object value) { List removed = new ArrayList(); synchronized (this) { // make room if needed while (cache.size() + 1 > maxSize) { removed.add(removeLRU()); } // remove the key from the list if it"s in the cache already Object cacheValue = cache.get(key); if (cacheValue != null) { if (cacheValue != value) removed.add(cacheValue); lru.remove(key); } // the last item in the list is the most recently used lru.addLast(key); // put it in the actual cache cache.put(key, value); } cleanupAll(removed); } /** * Gets an object from the cache. This object is set to be the * most recenty used */ public synchronized Object get(Object key) { // check for existence in cache if (!cache.containsKey(key)) { return null; } // set to most recently used lru.remove(key); lru.addLast(key); // return the object return cache.get(key); } /** * Removes the object from the cache and the lru list */ public synchronized Object remove(Object key) { // check for existence in cache if (!cache.containsKey(key)) { return null; } // remove from lru list lru.remove(key); // remove from cache Object obj = cache.remove(key); return obj; } private synchronized Object removeLRU() { Object obj = cache.remove(lru.getFirst()); lru.removeFirst(); return obj; } /** * Resize the cache */ public void resize(int newSize) { if (newSize <= 0) { return; } List removed = new ArrayList(); synchronized (this) { maxSize = newSize; while (cache.size() > maxSize) { removed.add(removeLRU()); } } cleanupAll(removed); } private void cleanupAll(List removed) { Iterator it = removed.iterator(); while (it.hasNext()) { cleanupObject(it.next()); } } /** * Override this method to do special cleanup on an object, * such as closing a statement or a connection */ protected void cleanupObject(Object o) {} public void cleanupAll() { for (Enumeration enumeration = cache.keys();enumeration.hasMoreElements();) { Object o = remove(enumeration.nextElement()); cleanupObject(o); } }
}
</source>