org.aitools.programd.util
Class LRUCache<K,V>

java.lang.Object
  extended by org.aitools.programd.util.LRUCache<K,V>
Type Parameters:
K - the key
V - the value

public class LRUCache<K,V>
extends java.lang.Object

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.


Nested Class Summary
(package private) static class LRUCache.CacheItem<K_,V_>
          A cache item
static interface LRUCache.Entry<K_,V_>
          Interface for entry iterator;
(package private)  class LRUCache.EntryIterator
          Iterator of cache values
(package private) static class LRUCache.KeyIterator<K_,V_>
          Iterator of cache keys
(package private) static class LRUCache.ValueIterator<K_,V_>
          Iterator of cache values
 
Field Summary
private  int _capacity
           
private  int _capacity1
           
protected  LRUCache.CacheItem<K,V>[] _entries
           
private  LRUCache.CacheItem<K,V> _head1
           
private  LRUCache.CacheItem<K,V> _head2
           
private  long _hitCount
           
private  int _mask
           
private  long _missCount
           
private  int _size1
           
private  int _size2
           
private  LRUCache.CacheItem<K,V> _tail1
           
private  LRUCache.CacheItem<K,V> _tail2
           
private static java.lang.Integer NULL
           
 
Constructor Summary
LRUCache(int initialCapacity)
          Create the LRU cache with a specific capacity.
 
Method Summary
 void clear()
          Clears the cache
 V get(K key)
          Get an item from the cache and make it most recently used.
 long getHitCount()
           
 long getMissCount()
           
 java.util.Iterator<LRUCache.Entry<K,V>> iterator()
           
 java.util.Iterator<K> keys()
           
 java.util.Iterator<K> keys(java.util.Iterator<K> oldIter)
           
 V put(K key, V value)
          Puts a new item in the cache.
private  V put(K key, V value, boolean replace)
          Puts a new item in the cache.
 V putIfNew(K key, V value)
          Puts a new item in the cache.
private  void refillEntry(LRUCache.CacheItem<K,V> item)
          Put the item in the best location available in the hash table.
 V remove(K key)
          Removes an item from the cache
 boolean removeTail()
           
 int size()
           
private  void updateLru(LRUCache.CacheItem<K,V> item)
          Put item at the head of the used-twice lru list.
 java.util.Iterator<V> values()
           
 java.util.Iterator<V> values(java.util.Iterator<V> oldIter)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

NULL

private static final java.lang.Integer NULL

_entries

protected LRUCache.CacheItem<K,V>[] _entries

_capacity

private int _capacity

_capacity1

private int _capacity1

_mask

private int _mask

_size1

private int _size1

_head1

private LRUCache.CacheItem<K,V> _head1

_tail1

private LRUCache.CacheItem<K,V> _tail1

_size2

private int _size2

_head2

private LRUCache.CacheItem<K,V> _head2

_tail2

private LRUCache.CacheItem<K,V> _tail2

_hitCount

private volatile long _hitCount

_missCount

private volatile long _missCount
Constructor Detail

LRUCache

public LRUCache(int initialCapacity)
Create the LRU cache with a specific capacity. Originally called "LruCache". Some minor changes (in coding style and formatting) made by Noel.

Parameters:
initialCapacity - minimum capacity of the cache
Method Detail

size

public int size()
Returns:
the current number of entries in the cache

clear

public void clear()
Clears the cache


get

public V get(K key)
Get an item from the cache and make it most recently used.

Parameters:
key - key to lookup the item
Returns:
the matching object in the cache

put

public V put(K key,
             V value)
Puts a new item in the cache. If the cache is full, remove the LRU item.

Parameters:
key - key to store data
value - value to be stored
Returns:
old value stored under the key

putIfNew

public V putIfNew(K key,
                  V value)
Puts a new item in the cache. If the cache is full, remove the LRU item.

Parameters:
key - key to store data
value - value to be stored
Returns:
the value actually stored

put

private V put(K key,
              V value,
              boolean replace)
Puts a new item in the cache. If the cache is full, remove the LRU item.

Parameters:
key - key to store data
value - value to be stored
replace - whether or not to replace the old value
Returns:
old value stored under the key

updateLru

private void updateLru(LRUCache.CacheItem<K,V> item)
Put item at the head of the used-twice lru list. This is always called while synchronized.

Parameters:
item - the item to put at the head of the list

removeTail

public boolean removeTail()
Returns:
the last item in the LRU

remove

public V remove(K key)
Removes an item from the cache

Parameters:
key - the key to remove
Returns:
the value removed

refillEntry

private void refillEntry(LRUCache.CacheItem<K,V> item)
Put the item in the best location available in the hash table.

Parameters:
item - the item to put in the best location available

keys

public java.util.Iterator<K> keys()
Returns:
the keys stored in the cache

keys

public java.util.Iterator<K> keys(java.util.Iterator<K> oldIter)
Parameters:
oldIter - the old iterator to use
Returns:
keys stored in the cache using an old iterator

values

public java.util.Iterator<V> values()
Returns:
the values in the cache

values

public java.util.Iterator<V> values(java.util.Iterator<V> oldIter)
Parameters:
oldIter - the old iterator
Returns:
the values of the old iterator

iterator

public java.util.Iterator<LRUCache.Entry<K,V>> iterator()
Returns:
the entries

getHitCount

public long getHitCount()
Returns:
the hit count.

getMissCount

public long getMissCount()
Returns:
the miss count.