/*
* Copyright (c) 1998-2004 Caucho Technology -- all rights reserved This file is
* part of Resin(R) Open Source Each copy or derived work must preserve the
* copyright notice and this notice unmodified. Resin Open Source is free
* software; you can redistribute it and/or modify it under the terms of the GNU
* General Public License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version. Resin Open
* Source 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, or any warranty of NON-INFRINGEMENT. See the GNU
* General Public License for more details. You should have received a copy of
* the GNU General Public License along with Resin Open Source; if not, write to
* the Free SoftwareFoundation, Inc. 59 Temple Place, Suite 330 Boston, MA
* 02111-1307 USA @author Scott Ferguson
*/
// originally: package com.caucho.util;
//package org.aitools.programd.util;
import java.util.ArrayList;
import java.util.Iterator;
/**
*
* Fixed length cache with a LRU replacement policy. If cache items implement
* CacheListener, they will be informed when they're removed from the cache.
*
*
* Null keys are not allowed. LRUCache is synchronized.
*
*
* @param the key
* @param the value
*/
public class LRUCache
{
private static final Integer NULL = new Integer(0);
/*
* hash table containing the entries. Its size is twice the capacity so it
* will always remain at least half empty
*/
protected CacheItem[] _entries;
/* maximum allowed entries */
private int _capacity;
/* size 1 capacity is half the actual capacity */
private int _capacity1;
/* mask for hash mapping */
private int _mask;
/* number of items in the cache seen once */
private int _size1;
/* head of the LRU list */
private CacheItem _head1;
/* tail of the LRU list */
private CacheItem _tail1;
/* number of items in the cache seen more than once */
private int _size2;
/* head of the LRU list */
private CacheItem _head2;
/* tail of the LRU list */
private CacheItem _tail2;
/* hit count statistics */
private volatile long _hitCount;
/* miss count statistics */
private volatile long _missCount;
/**
* Create the LRU cache with a specific capacity. Originally called
* "LruCache". Some minor changes (in coding style and formatting) made by
* Noel.
*
* @param initialCapacity minimum capacity of the cache
*/
@SuppressWarnings("unchecked")
public LRUCache(int initialCapacity)
{
int capacity;
for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2)
{
// Do nothing except this loop.
}
this._entries = new CacheItem[capacity];
this._mask = capacity - 1;
this._capacity = initialCapacity;
this._capacity1 = this._capacity / 2;
}
/**
* @return the current number of entries in the cache
*/
public int size()
{
return this._size1 + this._size2;
}
/**
* Clears the cache
*/
public void clear()
{
ArrayList listeners = null;
synchronized (this)
{
for (int i = this._entries.length - 1; i >= 0; i--)
{
CacheItem item = this._entries[i];
if (item != null)
{
if (item._value instanceof CacheListener)
{
if (listeners == null)
{
listeners = new ArrayList();
}
listeners.add((CacheListener) item._value);
}
}
this._entries[i] = null;
}
this._size1 = 0;
this._head1 = null;
this._tail1 = null;
this._size2 = 0;
this._head2 = null;
this._tail2 = null;
}
for (int i = listeners == null ? -1 : listeners.size() - 1; i >= 0; i--)
{
CacheListener listener = listeners.get(i);
listener.removeEvent();
}
}
/**
* Get an item from the cache and make it most recently used.
*
* @param key key to lookup the item
* @return the matching object in the cache
*/
public V get(K key)
{
Object okey = key;
if (okey == null)
okey = NULL;
int hash = okey.hashCode() & this._mask;
int count = this._size1 + this._size2 + 1;
synchronized (this)
{
for (; count >= 0; count--)
{
CacheItem item = this._entries[hash];
if (item == null)
{
this._missCount++;
return null;
}
if (item._key == key || item._key.equals(key))
{
updateLru(item);
this._hitCount++;
return item._value;
}
hash = (hash + 1) & this._mask;
}
this._missCount++;
}
return null;
}
/**
* Puts a new item in the cache. If the cache is full, remove the LRU item.
*
* @param key key to store data
* @param value value to be stored
* @return old value stored under the key
*/
public V put(K key, V value)
{
V oldValue = put(key, value, true);
if (oldValue instanceof CacheListener)
((CacheListener) oldValue).removeEvent();
return oldValue;
}
/**
* Puts a new item in the cache. If the cache is full, remove the LRU item.
*
* @param key key to store data
* @param value value to be stored
* @return the value actually stored
*/
public V putIfNew(K key, V value)
{
V oldValue = put(key, value, false);
if (oldValue != null)
{
return oldValue;
}
// otherwise...
return value;
}
/**
* Puts a new item in the cache. If the cache is full, remove the LRU item.
*
* @param key key to store data
* @param value value to be stored
* @param replace whether or not to replace the old value
* @return old value stored under the key
*/
private V put(K key, V value, boolean replace)
{
Object okey = key;
if (okey == null)
{
okey = NULL;
}
// remove LRU items until we're below capacity
while (this._capacity <= this._size1 + this._size2)
{
removeTail();
}
int hash = key.hashCode() & this._mask;
int count = this._size1 + this._size2 + 1;
V oldValue = null;
synchronized (this)
{
for (; count > 0; count--)
{
CacheItem item = this._entries[hash];
// No matching item, so create one
if (item == null)
{
item = new CacheItem(key, value);
this._entries[hash] = item;
this._size1++;
item._next = this._head1;
if (this._head1 != null)
{
this._head1._prev = item;
}
else
{
this._tail1 = item;
}
this._head1 = item;
return null;
}
// matching item gets replaced
if (item._key == okey || item._key.equals(okey))
{
updateLru(item);
oldValue = item._value;
if (replace)
{
item._value = value;
}
break;
}
hash = (hash + 1) & this._mask;
}
}
if (replace && oldValue instanceof CacheListener)
{
((CacheListener) oldValue).removeEvent();
}
return null;
}
/**
* Put item at the head of the used-twice lru list. This is always called
* while synchronized.
*
* @param item the item to put at the head of the list
*/
private void updateLru(CacheItem item)
{
CacheItem prev = item._prev;
CacheItem next = item._next;
if (item._isOnce)
{
item._isOnce = false;
if (prev != null)
{
prev._next = next;
}
else
{
this._head1 = next;
}
if (next != null)
{
next._prev = prev;
}
else
{
this._tail1 = prev;
}
item._prev = null;
if (this._head2 != null)
{
this._head2._prev = item;
}
else
{
this._tail2 = item;
}
item._next = this._head2;
this._head2 = item;
this._size1--;
this._size2++;
}
else
{
if (prev == null)
{
return;
}
prev._next = next;
item._prev = null;
item._next = this._head2;
this._head2._prev = item;
this._head2 = item;
if (next != null)
{
next._prev = prev;
}
else
{
this._tail2 = prev;
}
}
}
/**
* @return the last item in the LRU
*/
public boolean removeTail()
{
CacheItem tail;
if (this._capacity1 <= this._size1)
{
tail = this._tail1;
}
else
{
tail = this._tail2;
}
if (tail == null)
{
return false;
}
remove(tail._key);
return true;
}
/**
* Removes an item from the cache
*
* @param key the key to remove
* @return the value removed
*/
public V remove(K key)
{
Object okey = key;
if (okey == null)
{
okey = NULL;
}
int hash = key.hashCode() & this._mask;
int count = this._size1 + this._size2 + 1;
V value = null;
synchronized (this)
{
for (; count > 0; count--)
{
CacheItem item = this._entries[hash];
if (item == null)
{
return null;
}
if (item._key == okey || item._key.equals(okey))
{
this._entries[hash] = null;
CacheItem prev = item._prev;
CacheItem next = item._next;
if (item._isOnce)
{
this._size1--;
if (prev != null)
{
prev._next = next;
}
else
{
this._head1 = next;
}
if (next != null)
{
next._prev = prev;
}
else
{
this._tail1 = prev;
}
}
else
{
this._size2--;
if (prev != null)
{
prev._next = next;
}
else
{
this._head2 = next;
}
if (next != null)
{
next._prev = prev;
}
else
{
this._tail2 = prev;
}
}
value = item._value;
// Shift colliding entries down
for (int i = 1; i <= count; i++)
{
int nextHash = (hash + i) & this._mask;
CacheItem nextItem = this._entries[nextHash];
if (nextItem == null)
{
break;
}
this._entries[nextHash] = null;
refillEntry(nextItem);
}
break;
}
hash = (hash + 1) & this._mask;
}
}
if (count < 0)
{
throw new RuntimeException("internal cache error");
}
return value;
}
/**
* Put the item in the best location available in the hash table.
*
* @param item the item to put in the best location available
*/
private void refillEntry(CacheItem item)
{
int baseHash = item._key.hashCode();
for (int count = 0; count < this._size1 + this._size2 + 1; count++)
{
int hash = (baseHash + count) & this._mask;
if (this._entries[hash] == null)
{
this._entries[hash] = item;
return;
}
}
}
/**
* @return the keys stored in the cache
*/
public Iterator keys()
{
KeyIterator iter = new KeyIterator(this);
iter.init(this);
return iter;
}
/**
* @param oldIter the old iterator to use
* @return keys stored in the cache using an old iterator
*/
@SuppressWarnings("unchecked")
public Iterator keys(Iterator oldIter)
{
KeyIterator iter;
try
{
iter = (KeyIterator) oldIter;
}
catch (ClassCastException e)
{
throw new Exception("Passed a non-ValueIterator to values().", e);
}
iter.init(this);
return oldIter;
}
/**
* @return the values in the cache
*/
public Iterator values()
{
ValueIterator iter = new ValueIterator(this);
iter.init(this);
return iter;
}
/**
* @param oldIter the old iterator
* @return the values of the old iterator
*/
@SuppressWarnings("unchecked")
public Iterator values(Iterator oldIter)
{
ValueIterator iter;
try
{
iter = (ValueIterator) oldIter;
}
catch (ClassCastException e)
{
throw new Exception("Passed a non-ValueIterator to values().", e);
}
iter.init(this);
return oldIter;
}
/**
* @return the entries
*/
public Iterator> iterator()
{
return new EntryIterator(this);
}
/**
* @return the hit count.
*/
public long getHitCount()
{
return this._hitCount;
}
/**
* @return the miss count.
*/
public long getMissCount()
{
return this._missCount;
}
/**
* A cache item
*
* @param the key
* @param the value
*/
static class CacheItem
{
LRUCache.CacheItem _prev;
LRUCache.CacheItem _next;
K_ _key;
V_ _value;
int _index;
boolean _isOnce;
CacheItem(K_ key, V_ value)
{
this._key = key;
this._value = value;
this._isOnce = true;
}
}
/**
* Iterator of cache keys
*
* @param the key
* @param the value
*/
static class KeyIterator implements Iterator
{
private LRUCache _cache;
private int _i = -1;
KeyIterator(LRUCache cache)
{
this._cache = cache;
}
void init(LRUCache cache)
{
this._cache = cache;
this._i = -1;
}
/**
* @return the next entry in the cache
*/
public boolean hasNext()
{
CacheItem[] entries = this._cache._entries;
int length = entries.length;
for (this._i++; this._i < length; this._i++)
{
if (entries[this._i] != null)
{
this._i--;
return true;
}
}
return false;
}
/**
* @return the next value
*/
public K_ next()
{
CacheItem[] entries = this._cache._entries;
int length = entries.length;
for (this._i++; this._i < length; this._i++)
{
CacheItem entry = entries[this._i];
if (entry != null)
{
return entry._key;
}
}
return null;
}
/**
* @see java.util.Iterator#remove()
*/
public void remove()
{
throw new UnsupportedOperationException();
}
}
/**
* Iterator of cache values
*
* @param the key
* @param the value
*/
static class ValueIterator implements Iterator
{
private LRUCache _cache;
private int _i = -1;
ValueIterator(LRUCache cache)
{
init(cache);
}
void init(LRUCache cache)
{
this._cache = cache;
this._i = -1;
}
/**
* @return the next entry in the cache.
*/
public boolean hasNext()
{
CacheItem[] entries = this._cache._entries;
int length = entries.length;
int i = this._i + 1;
for (; i < length; i++)
{
if (entries[i] != null)
{
this._i = i - 1;
return true;
}
}
this._i = i;
return false;
}
/**
* @return the next value
*/
public V_ next()
{
CacheItem[] entries = this._cache._entries;
int length = entries.length;
int i = this._i + 1;
for (; i < length; i++)
{
CacheItem entry = entries[i];
if (entry != null)
{
this._i = i;
return entry._value;
}
}
this._i = i;
return null;
}
/**
* @see java.util.Iterator#remove()
*/
public void remove()
{
throw new UnsupportedOperationException();
}
}
/**
* Interface for entry iterator;
*
* @param the key
* @param the value
*/
public interface Entry
{
/**
* @return the key
*/
public K_ getKey();
/**
* @return the value
*/
public V_ getValue();
}
/**
* Iterator of cache values
*/
class EntryIterator implements Iterator>, Entry
{
private int _i = -1;
private LRUCache _cache;
/**
* Creates a new EntryIterator using the given cache.
*
* @param cache the cache to use
*/
public EntryIterator(LRUCache cache)
{
this._cache = cache;
}
/**
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext()
{
int i = this._i + 1;
CacheItem[] entries = this._cache._entries;
int length = entries.length;
for (; i < length && entries[i] == null; i++)
{
// Do nothing but this loop.
}
this._i = i - 1;
return i < length;
}
/**
* @return the next entry
* @see java.util.Iterator#next()
*/
public Entry next()
{
int i = this._i + 1;
CacheItem[] entries = this._cache._entries;
int length = entries.length;
for (; i < length && entries[i] == null; i++)
{
// Do nothing but this loop.
}
this._i = i;
if (this._i < length)
{
return this;
}
// otherwise...
return null;
}
/**
* @return the key
*/
public K getKey()
{
CacheItem[] entries = this._cache._entries;
if (this._i < this._cache._entries.length)
{
CacheItem entry = entries[this._i];
return entry != null ? entry._key : null;
}
return null;
}
/**
* @return the value
*/
public V getValue()
{
CacheItem[] entries = this._cache._entries;
if (this._i < this._cache._entries.length)
{
CacheItem entry = entries[this._i];
return entry != null ? entry._value : null;
}
return null;
}
/**
* @see java.util.Iterator#remove()
*/
public void remove()
{
CacheItem[] entries = this._cache._entries;
if (this._i < this._cache._entries.length)
{
CacheItem entry = entries[this._i];
if (entry != null)
{
LRUCache.this.remove(entry._key);
}
}
}
}
}
interface CacheListener
{
/**
* Notifies the cache entry that it's been removed from the cache.
*/
public void removeEvent();
}