lfumemorystore.java

EasyDBO是一个超轻量级对象-关系映射（Object/Relation Mapping

package com.easyjf.cache.store;

import com.easyjf.cache.*;

import org.apache.log4j.*;

/**
 * 这里直接使用的Apache开源缓存ECache中的算法
 */
import java.io.*;

import java.util.*;

/**
 * Least Frequently Used (LFU) implementation of the memory store.
 * 
 * @author <a href="[e-mail]">Surya Suravarapu</a>
 * @version $Id: LfuMemoryStore.java,v 1.11 2005/10/15 17:32:30 gregluck Exp $
 *          Warning: Testing of this store reveals some problems with it. Do not
 *          use. It may be removed.
 */
/**
 * 
 * 
 * <p>
 * Title:
 * </p>
 * 
 * <p>
 * Description: 该算法直接借鉴Apache EhCache的缓存算法
 * </p>
 * 
 * <p>
 * Copyright: Copyright (c) 2006
 * </p>
 * 
 * <p>
 * Company:
 * </p>
 * 
 * @author not attributable
 * @version 1.0
 */
public class LfuMemoryStore extends MemoryStore {
	private final static Logger logger = Logger.getLogger(LfuMemoryStore.class);

	// ~--- fields -------------------------------------------------------------

	/**
	 * A sorted list of elements in the ascending order of the hits
	 */
	private List sortedElementList;

	// ~--- constructors -------------------------------------------------------

	/**
	 * 
	 * @param cache
	 *            ICache
	 */
	protected LfuMemoryStore(ICache cache) {
		super(cache);
		map = new HashMap();
		sortedElementList = new LinkedList();
	}

	// ~--- methods ------------------------------------------------------------

	/**
	 */
	protected void clear() {
		map.clear();
		sortedElementList.clear();
	}

	/**
	 * 
	 * @param element1
	 *            Element
	 * @param element2
	 *            Element
	 * @return int
	 * @throws ClassCastException
	 */
	public int compareElements(Element element1, Element element2)
			throws ClassCastException {
		long count1 = element1.getHitCount();
		long count2 = element2.getHitCount();

		if (count1 < count2) {
			return -1;
		} else if (count1 > count2) {
			return 1;
		}

		return 0;
	}

	/**
	 * 
	 * @param element
	 *            Element
	 */
	protected void doGetOnFoundElement(Element element) {
		resortList(element);
	}

	/**
	 * 
	 * @param element
	 *            Element
	 */
	public synchronized void doPut(Element element) {
		if (isFull()) {
			//logger.info("缓存已满！"+map.size());
			removeLfuElement();
		}

		insertInSortedList(element);
	}

	/**
	 * 
	 * @param element
	 *            Element
	 */
	private void insertInSortedList(Element element) {

		// If the list is empty just add the element in the list, nothing to
		// sort
		if (sortedElementList.size() == 0) {
			sortedElementList.add(element);

			return;
		}

		int low = 0;
		int high = sortedElementList.size() - 1;
		boolean less = false;
		boolean more = false;

		while (low <= high) {
			int mid = low + high / 2;
			int compareResult = compareElements(element,
					(Element) sortedElementList.get(mid));

			if (compareResult < 0) {
				less = true;

				if (low == high) {
					more = true;
				}

				if (more) {
					sortedElementList.add(mid + 1, element);

					break;
				}

				high = mid - 1;
			} else if (compareResult > 0) {
				more = true;

				if (low == high) {
					less = true;
				}

				if (less) {
					sortedElementList.add(mid - 1, element);

					break;
				}

				low = mid + 1;
			} else if (compareResult == 0) {
				sortedElementList.add(mid, element);

				break;
			}
		}
	}

	/**
	 * 
	 * @param key
	 *            Serializable
	 * @return Element
	 */
	public synchronized Element remove(Serializable key) {
		return remove(key, -1);
	}

	/**
	 * 
	 * @param key
	 *            Object
	 * @param index
	 *            int
	 * @return Element
	 */
	private synchronized Element remove(Object key, int index) {
		Element element = (Element) map.remove(key);
		int i = index;

		if (index == -1) {
			i = sortedElementList.indexOf(element);
		}

		if (i != -1) {

			// Also remove the entry from the node list
			sortedElementList.remove(i);
		} else {
			logger.info(cache.getName() + "Cache: The element with key " + key
					+ " is not found in the memory store");
		}

		if (element != null) {
			logger.info(cache.getName() + "Cache: The element with key " + key
					+ " is removed from the memory store");
		}

		return element;
	}

	/**
	 * 
	 */
	private void removeLfuElement() {
		if (sortedElementList.size() == 0) {
			return;
		}

		logger.info("缓存已经满了. 按LFU规则删除一个元素...");

		// First element of the sorted list is the candidate for the removal
		Element element = (Element) sortedElementList.get(0);

		// If the element is expired remove
		if (cache.isExpired(element)) {
			remove(element.getKey(), 0);
			return;
		}

		remove(element.getKey(), 0);
	}

	/**
	 * 
	 * @param element
	 *            Element
	 */
	private void resortList(Element element) {
		int index = sortedElementList.indexOf(element);

		if (index != -1) {
			int size = sortedElementList.size();

			for (int i = index; i < size; i++) {
				if (i + 1 < size) {
					Element nextElement = (Element) sortedElementList
							.get(i + 1);

					if (compareElements(element, nextElement) > 0) {
						sortedElementList.set(i + 1, element);
						sortedElementList.set(i, nextElement);
					}
				}
			}
		} else {
			logger.info("Element with key " + element.getKey() + " not found");
		}
	}

	// ~--- inner classes ------------------------------------------------------

	/**
	 * 
	 * <p>
	 * Title:
	 * </p>
	 * 
	 * <p>
	 * Description:
	 * </p>
	 * 
	 * <p>
	 * Copyright: Copyright (c) 2006
	 * </p>
	 * 
	 * <p>
	 * Company:
	 * </p>
	 * 
	 * @author not attributable
	 * @version 1.0
	 */
	public class ElementComparator implements Comparator {

		/**
		 * 
		 * @param obj1
		 *            Object
		 * @param obj2
		 *            Object
		 * @return int
		 */
		public int compare(Object obj1, Object obj2) {
			return compareElements((Element) obj1, (Element) obj2);
		}
	}
}