lfumemorystore.java

简易java框架开源论坛系统,简 易java框架开源论坛系统

package com.easyjf.cache.store;
/**
 * 这里直接使用的Apache开源缓存ECache中的算法
 */
import com.easyjf.cache.*;

import org.apache.log4j.Logger;
import java.io.Serializable;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 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.
 */
public class LfuMemoryStore extends MemoryStore {
	private final static Logger logger = Logger.getLogger(LfuMemoryStore.class);
    /**
     * A sorted list of elements in the ascending order of the hits
     */
    private List sortedElementList;

    /**
     * Constructor for the LfuMemoryStore object
     */
    protected LfuMemoryStore(ICache cache) {
        super(cache);

        map = new HashMap();
        sortedElementList = new LinkedList();
    }

    /**
     * Puts an element into the cache
     */
    public synchronized void doPut(Element element) {
        if (isFull()) {
            removeLfuElement();
        }
        insertInSortedList(element);
    }


    /**
     * Allows subclasses to do any further processing when an element is found
     */
    protected void doGetOnFoundElement(Element element) {
        resortList(element);
    }


    /**
     * Clears any data structures and places it back to its state when it was first created
     */
    protected void clear() {
        map.clear();
        sortedElementList.clear();
    }

    /**
     * Removes an item from the cache.
     */
    public synchronized Element remove(Serializable key) {
        return remove(key, -1);
    }

    /**
     * Removes an element from the cache
     */
    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;
    }

    /**
     * Binary Search algorithm is used
     */
    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;
            }
        }
    }

    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");            
        }
    }

    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);
    }


    /**
     * Compares its two arguments for order.  Returns a negative integer,
     * zero, or a positive integer as the first argument is less than, equal
     * to, or greater than the second.<p>
     * <p/>
     *
     * @param element1 the first element to be compared.
     * @param element2 the second element to be compared.
     * @return a negative integer, zero, or a positive integer as the
     *         first argument is less than, equal to, or greater than the
     *         second.
     * @throws ClassCastException if the arguments' types prevent them from
     *                            being compared by this Comparator.
     */
    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;
    }

    /**
     * A comparator class compares two elements.
     */
    public class ElementComparator implements Comparator {
        /**
         * Compares two elements
         */
        public int compare(Object obj1, Object obj2) {
            return compareElements((Element) obj1, (Element) obj2);
        }
    }
}