lrucache.java

博克后台的开发,有很多使用的方法和例子可以提供给大家学习

/*
 * Class LRUCache
 * --------------
 *
 * $Author: liangwei $
 * $Revision: 1.1 $
 * $Name:  $
 *
 * Copyright 2001 Triple Kona Software, Inc.
 *
 * 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 (at your option) 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
 */
package com.common.util;

import java.util.Map;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.HashSet;

/**
 * This class implements a simple, thread-safe LRU cache.  The size of
 * the cache is specifed in terms of the number of objects that the
 * cache can hold.  In addition to an LRU algorithm, each entry in the
 * cache has a timeout value.  When the entry expires, it is evicted
 * from the cache.
 *
 * @author Dhiren Patel, Triple Kona Software, Inc.
 */
public class LruCache implements Map {

	/**
	 * Create a cache with the given timeout and with an infinite default timeout
	 * for entries; this will create a true LRU cache, i.e. the expiration will
	 * be based only on the last accessed time and not the lifespan of the
	 * entry.  The initial capacity of the cache will be zero.
	 * 
	 * LRU(Least Recently Used)最近最少用算法
	 * 
	 * @see LRUCache(long timeout, long lifespan, int initialCapacity, int maxCapacity)
	 * @see LRUCache(long timeout,long lifespan, int maxCapacity)
	 */
	public LruCache(long timeout, int maxCapacity) {
		this(timeout,Long.MAX_VALUE,0,maxCapacity);
	}


	/**
	 * timeout and lifespan in milliseconds. intial capacity = zero
	 *
	 * @see LRUCache(long timeout,int maxCapacity)
	 * @see LRUCache(long timeout, long lifespan, int initialCapacity, int maxCapacity)
	 */
	public LruCache(long timeout,long lifespan, int maxCapacity) {
		this(timeout,lifespan,0,maxCapacity);
	}

	/**
	 * Create an LRUCache with a given default timeout and lifespan
	 * for each entry.  If <code>lifespan < timeout</code> then
	 * this will be a timeout only cache, i.e. entries will be evicted from
	 * the cache when they have lived longer than <code>lifespan</code>.
	 * You can get a LRU only cache by setting lifespan to Long.MAX_VALUE.
	 *
	 * @see LRUCache(long timeout,int maxCapacity)
	 * @see LRUCache(long timeout,long lifespan, int maxCapacity)
	 */
	public LruCache(long timeout, long lifespan, int initialCapacity, int maxCapacity) {
		if(timeout < 0 )
			throw new IllegalArgumentException("timeout < 0");

		_timeout = timeout;

		if(lifespan < 0)
			throw new IllegalArgumentException("lifespan < 0");

		_lifespan = lifespan;

		if(initialCapacity < 0)
			throw new IllegalArgumentException("initialCapacity < 0");

		if(maxCapacity < 0)
			throw new IllegalArgumentException("maxCapacity < 0");

		_timeOrder = new TreeMap();
		_keyOrder = new HashMap(initialCapacity);
		_maxCapacity = maxCapacity;
		_entryPool = new ArrayList(initialCapacity);
	}

	/* Implement the Map method */

	public synchronized boolean containsKey(Object key) {
		return (get(key) != null);
	}

	public synchronized boolean containsValue(Object value) {
		// We have to enumerate all of the entries because
		// the value is actually contained in the cache entry.
		Iterator i = _timeOrder.values().iterator();
		while(i.hasNext()) {
			Entry ent = (Entry)i.next();
			if(ent.getValue().equals(value))
				return true;
		}
		return false;
	}

	/**
	 * Returns an <i>unmodifiable and unsynchronized</i>
	 * <code>Set</code> of the
	 * <code>Entry</code> elements in the cache.  Note
	 * that the underlying cache may change after this method
	 * returns.  This method may return some expired entries
	 * if they have not yet been removed from the cache.
	 */
	public synchronized Set entrySet() {
		Iterator entries = _timeOrder.entrySet().iterator();
		HashSet hs = new HashSet(_timeOrder.size());
		Map.Entry ent;
		while(entries.hasNext()) {
			ent = (Entry)((Map.Entry)entries.next()).getValue();
			hs.add(ent);
		}
		return Collections.unmodifiableSet(hs);
	}

	public synchronized boolean equals(Object o) {
		LruCache c = (LruCache)o;
		return _timeOrder.equals(c._timeOrder) && _keyOrder.equals(c._keyOrder);
	}

	public synchronized int hashCode() {
		return _timeOrder.hashCode() ^ _keyOrder.hashCode();
	}

	public boolean isEmpty() {
		return _timeOrder.isEmpty();
	}

	/**
	 * Returns an <i>unmodifiable</i> <code>Set</code> of the
	 * keys elements in the cache.
	 */
	public synchronized Set keySet() {
		return Collections.unmodifiableSet(_keyOrder.keySet());
	}

	public synchronized Object get(Object key) {

		//System.out.println("Getting " + key);
		Entry ent = (Entry)_keyOrder.get(key);

		if(ent == null) {
			//System.out.println("Trying to get() null entry for key " + key);
			return null;
		}

		// If the entry is expired, update() will remove
		// it and return false.  We do _not_ return the value
		// in this case because the caller may then assume
		// that the value is in the cache, even though it
		// has been removed.
		if( !update(ent) )
			return null;
		else
			return ent.getValue();
	}

	/**
	 * Put a mapping in the cache with the default
	 * expiration time and lifespan.
	 */
	public synchronized Object put(Object key, Object val) {
		return put(key,val,_timeout);
	}

	/**
	 * Put a mapping in the cache using the given expiration
	 * time and the default lifespan (passed into the
	 * constructor).
	 */
	public synchronized Object put(Object key, Object val,
				long expirationTime) {
		while(_keyOrder.size() >= _maxCapacity) {
			remove(((Entry)_timeOrder.lastKey()).getKey());
		}

		Entry ent = getEntryFromPool(key,val,expirationTime,_lifespan);

		Entry retVal = add(ent);

		if(retVal != null)
			return retVal.getValue();

		return retVal;
	}

	private synchronized Entry add(Entry ent) {
		_keyOrder.put(ent.getKey(),ent);
		return (Entry)_timeOrder.put(ent,ent);
	}

	/**
	 * This will put all of the elements of <code>t</code>
	 * into the cache in a <i>linear</i> fashion.
	 */
	public synchronized void putAll(Map t) {
		Iterator i = t.keySet().iterator();
		Object key;
		while(i.hasNext()) {
			key = i.next();
			put(key,t.get(key));
		}
	}

	public synchronized Object remove(Object key) {
		//System.out.println("Removing " + key);
		Entry ent = (Entry)_keyOrder.remove(key);
		if(ent == null)
			return null;

		_timeOrder.remove(ent);
		Object retVal = ent.getValue();
		returnEntryToPool(ent);
		return retVal;
	}


	public synchronized int size() {
		return _keyOrder.size();
	}

	/**
	 * Returns an <i>unmodifiable</i> <code>Collection</code>
	 * of the values held in the cache.
	 */
	public synchronized Collection values() {
		return Collections.unmodifiableCollection(_timeOrder.values());
	}

	public synchronized void prune() {

		Iterator vals = _timeOrder.values().iterator();

		Entry ent = null;

		while(vals.hasNext()) {
			ent = (Entry)vals.next();
			if(ent.expired()) {
				remove(ent.getKey());
			}
		}
	}

	public synchronized void clear() {
		_keyOrder.clear();
		_timeOrder.clear();
	}

	public synchronized boolean contains(Object key) {
		if(_keyOrder.get(key) != null)
			return true;

		return false;
	}

	public long getTimeout() {
		return _timeout;
	}

	public void setTimeout(long millis) {
		_timeout = millis;
	}

	public int getMaxCapacity() {
		return _maxCapacity;
	}

	public void setMaxCapacity(int max) {