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>
