lrucache.java

来自「RESIN 3.2 最新源码」· Java 代码 · 共 798 行 · 第 1/2 页

/*
 * Copyright (c) 1998-2008 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 Software Foundation, Inc.
 *   59 Temple Place, Suite 330
 *   Boston, MA 02111-1307  USA
 *
 * @author Scott Ferguson
 */

package com.caucho.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.
 *
 * <p>Null keys are not allowed.  LruCache is synchronized.
 */
public class LruCache<K,V> {
  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
  private CacheItem []_entries;

  private boolean _isEnableListeners = true;
  
  // 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<K,V> _head1;
  // tail of the LRU list
  private CacheItem<K,V> _tail1;
  
  // number of items in the cache seen more than once
  private int _size2;

  // head of the LRU list
  private CacheItem<K,V> _head2;
  // tail of the LRU list
  private CacheItem<K,V> _tail2;

  // hit count statistics
  private volatile long _hitCount;
  // miss count statistics
  private volatile long _missCount;
  
  /**
   * Create the LRU cache with a specific capacity.
   *
   * @param initialCapacity minimum capacity of the cache
   */
  public LruCache(int initialCapacity)
  {
    int capacity;

    for (capacity = 16; capacity < 2 * initialCapacity; capacity *= 2) {
    }

    _entries = new CacheItem[capacity];
    _mask = capacity - 1;

    _capacity = initialCapacity;
    _capacity1 = _capacity / 2;
  }

  /**
   * Disable the listeners
   */
  public void setEnableListeners(boolean isEnable)
  {
    _isEnableListeners = isEnable;
  }

  /**
   * Returns the current number of entries in the cache.
   */
  public int size()
  {
    return _size1 + _size2;
  }

  /**
   * Returns the LRU cache capacity
   */
  public int getCapacity()
  {
    return _capacity;
  }

  /**
   * Clears the cache
   */
  public void clear()
  {
    if (_size1 == 0 && _size2 == 0)
      return;
    
    ArrayList<CacheListener> listeners = null;

    synchronized (this) {
      for (int i = _entries.length - 1; i >= 0; i--) {
        CacheItem<K,V> item = _entries[i];
        _entries[i] = null;

	if (_isEnableListeners) {
	  for (; item != null; item = item._nextHash) {
	    if (item._value instanceof CacheListener) {
	      if (listeners == null)
		listeners = new ArrayList<CacheListener>();
	      listeners.add((CacheListener) item._value);
	    }
	  }
        }
      }

      _size1 = 0;
      _head1 = null;
      _tail1 = null;
      _size2 = 0;
      _head2 = null;
      _tail2 = null;
    }

    for (int i = listeners != null ? listeners.size() - 1 : -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() & _mask;

    synchronized (this) {
      for (CacheItem<K,V> item = _entries[hash];
	   item != null;
	   item = item._nextHash) {
	if (item._key == okey || item._key.equals(okey)) {
	  updateLru(item);

	  _hitCount++;

	  return item._value;
	}
      }

      _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 (_isEnableListeners && 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;
    else
      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
   *
   * @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 (_capacity <= _size1 + _size2) {
      if (! removeTail())
	throw new IllegalStateException("unable to remove tail from cache");
    }

    int hash = okey.hashCode() & _mask;

    V oldValue = null;

    synchronized (this) {
      CacheItem<K,V> item = _entries[hash];
      
      for (;
	   item != null;
	   item = item._nextHash) {
	// matching item gets replaced
	if (item._key == okey || okey.equals(item._key)) {
	  updateLru(item);

	  oldValue = item._value;

	  if (replace)
	    item._value = value;
	  
	  if (value == oldValue)
	    oldValue = null;

	  break;
	}
      }

      if (item == null) {
	CacheItem<K,V> next = _entries[hash];
	
	item = new CacheItem<K,V>((K) okey, value);
	
	item._nextHash = next;
	if (next != null)
	  next._prevHash = item;
	
	_entries[hash] = item;
	_size1++;
	  
	item._nextLru = _head1;
	if (_head1 != null)
	  _head1._prevLru = item;
	else
	  _tail1 = item;
	_head1 = item;

	return null;
      }

      if (_isEnableListeners && replace
	  && oldValue instanceof SyncCacheListener)
	((SyncCacheListener) oldValue).syncRemoveEvent();
    }

    if (_isEnableListeners && replace && oldValue instanceof CacheListener)
      ((CacheListener) oldValue).removeEvent();

    return oldValue;
  }

  /**
   * Put item at the head of the used-twice lru list.
   * This is always called while synchronized.
   */
  private void updateLru(CacheItem<K,V> item)
  {
    CacheItem<K,V> prevLru = item._prevLru;
    CacheItem<K,V> nextLru = item._nextLru;

    if (item._hitCount++ == 1) {
      if (prevLru != null)
	prevLru._nextLru = nextLru;
      else
	_head1 = nextLru;

      if (nextLru != null)
	nextLru._prevLru = prevLru;
      else
	_tail1 = prevLru;

      item._prevLru = null;
      if (_head2 != null)
	_head2._prevLru = item;
      else
	_tail2 = item;
      
      item._nextLru = _head2;
      _head2 = item;

      _size1--;
      _size2++;
    }
    else {
      if (prevLru == null)
	return;
      
      prevLru._nextLru = nextLru;

      item._prevLru = null;
      item._nextLru = _head2;
      
      _head2._prevLru = item;
      _head2 = item;
      
      if (nextLru != null)
	nextLru._prevLru = prevLru;
      else
	_tail2 = prevLru;
    }
  }

  /**
   * Remove the last item in the LRU
   */
  public boolean removeTail()
  {
    CacheItem<K,V> tail;

    synchronized (this) {
      if (_capacity1 <= _size1)
	tail = _tail1;
      else if (_size2 > 0)
	tail = _tail2;
      else if (_size1 > 0)
	tail = _tail1;
      else
	return false;
    }
    
    remove(tail._key);
    
    return true;
  }

  /**
   * Remove the last item in the LRU.  In this case, remove from the
   * list with the longest length.
   *
   * For functions like Cache disk space, this is a better solution
   * than the struct LRU removal.
   */
  public boolean removeLongestTail()
  {
    CacheItem<K,V> tail;