TimedOutLRUCache.java

Go to the documentation of this file.

package org.gffs.cache;
 
/*
 * Copyright 2006 University of Virginia
 * 
 * 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.
 */
 
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
 
public class TimedOutLRUCache<KeyType, DataType>
{
  static Log _logger = LogFactory.getLog(TimedOutLRUCache.class);
 
  private HashMap<KeyType, RoleBasedCacheNode<KeyType, DataType>> _map;
  private LRUList<KeyType, DataType> _lruList;
  private TimeoutList<KeyType, DataType> _timeoutList;
 
  private int _maxElements;
  private long _defaultTimeoutMS;
  private Thread _activeTimeoutThread = null;
  private boolean _logCacheEjection = false;
  public String _cacheName = null; // the name for this cache.
 
  public TimedOutLRUCache(int maxElements, long defaultTimeoutMS, String cacheName)
  {
    if (maxElements < 1)
      throw new IllegalArgumentException("\"maxElements\" must be greater than 0.");
    _cacheName = cacheName;
    if (_cacheName == null)
      throw new IllegalArgumentException("must provide a non-null cache name");
 
    _maxElements = maxElements;
    _defaultTimeoutMS = defaultTimeoutMS;
    _map = new HashMap<KeyType, RoleBasedCacheNode<KeyType, DataType>>(_maxElements);
    _lruList = new LRUList<KeyType, DataType>();
    _timeoutList = new TimeoutList<KeyType, DataType>();
  }
 
  public int size()
  {
    return _map.size();
  }
 
  public void setCacheEjectionLogging(boolean logRemovals)
  {
    _logCacheEjection = logRemovals;
  }
 
  public void activelyTimeoutElements(boolean activelyTimeout)
  {
    synchronized (_map) {
      if (_activeTimeoutThread == null) {
        if (activelyTimeout)
          startActiveTimeout();
      } else {
        if (!activelyTimeout)
          stopActiveTimeout();
      }
    }
  }
 
  public String debugPrefix()
  {
    return _cacheName + ": ";
  }
 
  public void put(KeyType key, DataType data, long timeoutMS)
  {
    RoleBasedCacheNode<KeyType, DataType> newNode =
      new RoleBasedCacheNode<KeyType, DataType>(key, data, new Date(System.currentTimeMillis() + timeoutMS));
 
    synchronized (_map) {
      RoleBasedCacheNode<KeyType, DataType> oldNode = _map.remove(key);
      if (oldNode != null) {
        _lruList.remove(oldNode);
        _timeoutList.remove(oldNode);
      }
 
      if (_map.size() >= _maxElements)
        clearStale();
 
      while (_map.size() >= _maxElements) {
        RoleBasedCacheNode<KeyType, DataType> node = _lruList.removeFirst();
        if (_logCacheEjection && _logger.isDebugEnabled())
          _logger.debug(debugPrefix() + "overloaded cache: removing cached item with key: " + node.getKey());
        _timeoutList.remove(node);
        _map.remove(node.getKey());
      }
 
      _map.put(key, newNode);
      _lruList.insert(newNode);
      _timeoutList.insert(newNode);
 
      _map.notify();
    }
  }
 
  public void put(KeyType key, DataType data)
  {
    put(key, data, _defaultTimeoutMS);
  }
 
  public int getMaximumElements()
  {
    return _maxElements;
  }
 
  public boolean refresh(KeyType key)
  {
    synchronized (_map) {
      RoleBasedCacheNode<KeyType, DataType> node = _map.get(key);
      if (node == null)
        return false;
      _lruList.remove(node);
      node.setInvalidationDate(_defaultTimeoutMS);
      // move the node to the end of the LRU list, since we just accessed it.
      _lruList.insert(node);
      // also fix its position in the timeout list.
      _timeoutList.remove(node);
      _timeoutList.insert(node);
      return true;
    }
  }
 
  // hmmm: highly experimental memory analysis code here!
  // private final long CHECK_INTERVAL = 1000 * 60; // one minute interval between deep checks currently.
  private final long CHECK_INTERVAL = 1000 * 10;// hmmm: way too fast interval, being used for debugging.
 
  private Date _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL);
 
  public DataType get(KeyType key)
  {
    Date now = new Date();
 
    if (now.after(_nextDeepSizeCheck)) {
 
      /*
       * hmmm: size check code below, not right yet.
       * 
       * would be nice to break that output into k, m, g, etc.
       * 
       * trying the deep footprint on 'this' is giving unrealistic very small sizes.
       * 
       * also the deep size check is dying with a stack overflow during the large rns directory test, so we cannot use it yet.
       */
      // if (_logger.isDebugEnabled()) {
      // long sizeUsed = MemoryFootprint.getDeepFootprint(_map) + MemoryFootprint.getDeepFootprint(_lruList)
      // + MemoryFootprint.getDeepFootprint(_timeoutList);
      // _logger.debug(SizeOf.humanReadable(sizeUsed) + " consumed by "+ _cacheName);
      // }
 
      _nextDeepSizeCheck = new Date((new Date().getTime()) + CHECK_INTERVAL);
    }
 
    synchronized (_map) {
      RoleBasedCacheNode<KeyType, DataType> node = _map.get(key);
      if (node == null)
        return null;
      _lruList.remove(node);
      if (node.getInvalidationDate().before(now)) {
        // this entry has become stale.
        if (_logCacheEjection && _logger.isDebugEnabled())
          _logger.debug(debugPrefix() + "timed-out entry in get: removing cached item with key: " + node.getKey());
        _map.remove(key);
        _timeoutList.remove(node);
        return null;
      }
      // move the node to the end of the LRU list, since we just accessed it.
      _lruList.insert(node);
      return node.getData();
    }
  }
 
  public List<DataType> getAll()
  {
    ArrayList<DataType> toReturn = new ArrayList<DataType>();
    synchronized (_map) {
      for (KeyType key : _map.keySet()) {
        toReturn.add(_map.get(key).getData());
      }
    }
    return toReturn;
  }
 
  public List<DataType> getAllReferenced(List<KeyType> references)
  {
    ArrayList<DataType> toReturn = new ArrayList<DataType>();
    synchronized (_map) {
      for (KeyType key : references) {
        if (_map.containsKey(key)) {
          toReturn.add(_map.get(key).getData());
        } else {
          _logger.error(debugPrefix() + "failed to locate referenced object in cache: " + key);
        }
      }
    }
    return toReturn;
  }
 
  public void clearStale()
  {
    Date now = new Date();
 
    synchronized (_map) {
      while (true) {
        RoleBasedCacheNode<KeyType, DataType> node = _timeoutList.peekFirst();
        if (node == null)
          break;
 
        if (node.getInvalidationDate().compareTo(now) <= 0) {
          if (_logCacheEjection && _logger.isDebugEnabled())
            _logger.debug(debugPrefix() + "removing timed-out node: " + node.getKey());
          _map.remove(node.getKey());
          _timeoutList.removeFirst();
          _lruList.remove(node);
        } else {
          break;
        }
      }
    }
  }
 
  public void remove(KeyType key)
  {
    synchronized (_map) {
      RoleBasedCacheNode<KeyType, DataType> node = _map.remove(key);
      if (node != null) {
        _lruList.remove(node);
        _timeoutList.remove(node);
      }
    }
  }
 
  public Set<KeyType> keySet()
  {
    synchronized (_map) {
      return new HashSet<KeyType>(_map.keySet());
    }
  }
 
  public void clear()
  {
    synchronized (_map) {
      _map.clear();
      _lruList.clear();
      _timeoutList.clear();
    }
  }
 
  public void startActiveTimeout()
  {
    _activeTimeoutThread = new Thread(new ActiveTimeoutWorker(), "Active Cache Timeout Thread");
    _activeTimeoutThread.setDaemon(true);
    _activeTimeoutThread.start();
  }
 
  public void stopActiveTimeout()
  {
    Thread tmp = _activeTimeoutThread;
    _activeTimeoutThread = null;
    synchronized (_map) {
      _map.notify();
    }
 
    try {
      tmp.join();
    } catch (InterruptedException cause) {
    }
  }
 
  private class ActiveTimeoutWorker implements Runnable
  {
    public void run()
    {
      synchronized (_map) {
        while (_activeTimeoutThread != null) {
          try {
            clearStale();
            RoleBasedCacheNode<KeyType, DataType> firstNode = _timeoutList.peekFirst();
            if (firstNode == null) {
              _map.wait();
            } else {
              Date nextStale = firstNode.getInvalidationDate();
              long timeout = nextStale.getTime() - System.currentTimeMillis();
              if (timeout > 0) {
                _map.wait(timeout);
              }
            }
          } catch (InterruptedException ie) {
          }
        }
      }
    }
  }
}