lrucache.java

来自「jakarta-taglibs」· Java 代码 · 共 220 行

/*
 * Copyright 1999,2004 The Apache Software Foundation.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */ 
package org.apache.taglibs.cache;

import java.util.*;

/**
 * <p>A Map implementing a cache using an LRU cache-replacement algorithm.
 * Following the general Map contract, this class requires explicit,
 * outside synchronization in the event of concurrent access.</p>
 *
 * <p>Unlike similar LRU-based caches that implement Map (e.g., from Jakarta
 * Commons), this class has a hard <i>size</i> limit (in characters), not a
 * limit on the total number of elements.</p>
 *
 * <p>This class works like a Map for the methods it implements, but for
 * simplicity, it is not a full Map.  I'd rather implement the full Map
 * contract than just pay lip service to its methods.</p>
 *
 * @author Shawn Bayern
 */
public class LRUCache {

  //*********************************************************************
  // For testing...

  public static void main(String args[]) throws Exception {
    LRUCache m =
      new LRUCache(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
    String line;
    java.io.BufferedReader r =
      new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    while ((line = r.readLine()) != null) {
      m.put(line, line);
      Iterator i = m.keySet().iterator();
      System.out.println("  size = " + m.getCurrentSize());
      while (i.hasNext())
        System.out.println("  -> " + i.next());
    }
  }

  //*********************************************************************
  // The cache itself

  private Map cache = new HashMap();
  private LinkedList lruList = new LinkedList();
  private int currentSize = 0, maxSize;
  private int lifetime;


  //*********************************************************************
  // Plumbing

  /**
   * Stores data associated with each cache entry.
   */
  private class CacheEntry {
    private long expiration;
    private String value;
    private int size;

    public CacheEntry(String value) {
      this.value = value;
      this.size = value.length();
      if (lifetime > 0) {
        this.expiration = (new Date()).getTime() + lifetime;
      }
    }
    public String getValue() { return value; }
    public long getSize() { return size; }
    public boolean isExpired() { 
      if (lifetime <= 0)
        return false;
      return (expiration < (new Date()).getTime());
    }
  }


  //*********************************************************************
  // Public, Map-like methods

  public void clear() {
    cache = new HashMap();
    lruList = new LinkedList();
  }

  public String get(Object key) {
    // assert invariant
    if (currentSize > maxSize)
      throw new AssertionError("cache state corrupted");

    CacheEntry e = (CacheEntry) cache.get(key);
    if (e == null) {
      return null;
    } else if (e.isExpired()) {
      // if the item's expired, pretend it never existed
      cache.remove(key);
      lruList.remove(key);
      currentSize -= e.getSize();
      return null;
    } else {
      noteUsed(key);
      return ((CacheEntry) cache.get(key)).getValue();
    }
  }

  public Object put(Object key, Object value) {
    if (!(value instanceof String))
      throw new IllegalArgumentException(
        "this Map only accepts Strings as values");

    CacheEntry oldEntry = (CacheEntry) cache.get(key);
    if (oldEntry != null)
      currentSize -= oldEntry.getSize();
    CacheEntry e = new CacheEntry((String) value);
    currentSize += e.getSize();
    cache.put(key, e);
    noteUsed(key);

    if (currentSize > maxSize) {
      removeExpired();

      // now, if it's still necessary, remove legitimate but old entries
      while (currentSize > maxSize) {
	CacheEntry doomedEntry = (CacheEntry) cache.remove(lruList.getLast());
        lruList.removeLast();
        currentSize -= doomedEntry.getSize();
      }

      // assert invariant
      if (currentSize > maxSize)
        throw new AssertionError("cache state corrupted");
    }

    // return the old value as long as it wasn't expired
    if (oldEntry == null || oldEntry.isExpired())
      return null;
    else
      return oldEntry.getValue();
  }

  public Object remove(Object key) {
    lruList.remove(key);

    // return the old value as long as it wasn't expired
    CacheEntry oldEntry = (CacheEntry) cache.remove(key);
    if (oldEntry != null)
      currentSize -= oldEntry.getSize();
    if (oldEntry == null || oldEntry.isExpired())
      return null;
    else
      return oldEntry.getValue();
  }

  public Set keySet() {
    removeExpired();
    return cache.keySet();
  }

  //*********************************************************************
  // Other public methods

  public int getCurrentSize() {
    return currentSize;
  }

  //*********************************************************************
  // Constructor

  /**
   * Constructs an LRUCache that holds no more than <tt>size</tt> characters.
   * Each entry expires after <tt>expiration</tt> seconds, or never
   * expires if expiration less than or equal to 0.
   */
  public LRUCache(int size, int lifetime) {
    this.maxSize = size;
    this.lifetime = lifetime * 1000;
  }


  //*********************************************************************
  // Utility methods

  /** Record the fact that the given object was "most recently" used. */
  private void noteUsed(Object key) {
    lruList.remove(key);
    lruList.addFirst(key);
  }

  private void removeExpired() {
    // don't bother unless entries in this LRUCache expire
    if (lifetime >= 0) {
      // remove all expired entries
      Iterator i = cache.entrySet().iterator();
      while (i.hasNext()) {
	Map.Entry ent = (Map.Entry) i.next();
        CacheEntry testEntry = (CacheEntry) ent.getValue();
        if (testEntry.isExpired()) {
	  i.remove();
	  lruList.remove(ent.getKey());
	  currentSize -= testEntry.getSize();
	}
      }
    }
  }
}