/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
*
* The contents of this file are subject to the terms of either the GNU
* General Public License Version 2 only ("GPL") or the Common Development
* and Distribution License("CDDL") (collectively, the "License"). You
* may not use this file except in compliance with the License. You can obtain
* a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html
* or glassfish/bootstrap/legal/LICENSE.txt. See the License for the specific
* language governing permissions and limitations under the License.
*
* When distributing the software, include this License Header Notice in each
* file and include the License file at glassfish/bootstrap/legal/LICENSE.txt.
* Sun designates this particular file as subject to the "Classpath" exception
* as provided by Sun in the GPL Version 2 section of the License file that
* accompanied this code. If applicable, add the following below the License
* Header, with the fields enclosed by brackets [] replaced by your own
* identifying information: "Portions Copyrighted [year]
* [name of copyright owner]"
*
* Contributor(s):
*
* If you wish your version of this file to be governed by only the CDDL or
* only the GPL Version 2, indicate your decision by adding "[Contributor]
* elects to include this software in this distribution under the [CDDL or GPL
* Version 2] license." If you don't indicate a single choice of license, a
* recipient has the option to distribute your version of this file under
* either the CDDL, the GPL Version 2 or to extend the choice of license to
* its licensees as provided above. However, if you add GPL Version 2 code
* and therefore, elected the GPL Version 2 license, then the option applies
* only if the new code is made subject to such option by the copyright
* holder.
*/
/**
* Copyright 2000-2001 by iPlanet/Sun Microsystems, Inc.,
* 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
* All rights reserved.
*/
package com.sun.appserv.util.cache;
import java.util.ArrayList;
import java.util.Map;
import java.util.Properties;
import java.util.ResourceBundle;
/**
* LRUCache
* in-memory bounded cache with an LRU list
*/
public class LruCache extends BaseCache {
// the item never expires
public static final long NO_TIMEOUT = -1;
// LRU list
protected LruCacheItem head;
protected LruCacheItem tail;
// the number of times the cache was trimmed
protected int trimCount;
protected int listSize;
protected long timeout = NO_TIMEOUT;
protected int defaultMaxEntries = Constants.DEFAULT_MAX_ENTRIES;
protected boolean isUnbounded = false;
/**
* default constructor
*/
public LruCache() { }
/**
* constructor with specified max entries.
* @param defaultMaxEntries specifies the default max entries
* to use when the maxEntries is <= 0.
*/
public LruCache(int defaultMaxEntries) {
this.defaultMaxEntries = defaultMaxEntries;
}
/**
* initialize the cache
* @param maxEntries maximum number of entries expected in the cache
* @param loadFactor the load factor
* @param timeout to be used to trim the expired entries
* @param props opaque list of properties for a given cache implementation
* @throws a generic Exception if the initialization failed
*/
public void init(int maxEntries, long timeout, float loadFactor, Properties props) {
// if the max entries is <= 0 then set the default max entries
if (maxEntries <= 0) {
maxEntries = defaultMaxEntries;
// mark this cache unbounded
isUnbounded = true;
}
setTimeout(timeout);
super.init(maxEntries, loadFactor, props);
}
/**
* sets the timeout value
* @param timeout to be used to trim the expired entries
*/
public void setTimeout(long timeout) {
// accept a positive timeout
if (timeout > 0)
this.timeout = timeout;
}
/**
* create new item
* @param hashCode for the entry
* @param key <code>Object</code> key
* @param value <code>Object</code> value
* @param size size in bytes of the item
*
* subclasses may override to provide their own CacheItem extensions
* e.g. one that permits persistence.
*/
protected CacheItem createItem(int hashCode, Object key,
Object value, int size) {
return new LruCacheItem(hashCode, key, value, size);
}
/**
* trim one item from the LRU list
* @param currentTime of this operation
* @return the item trimmed from cache
*
* list synchronization is handled by the caller
*/
protected CacheItem trimLru(long currentTime) {
LruCacheItem trimItem = tail;
if (tail != head) {
tail = trimItem.lPrev;
if(tail == null) {
//TODO:: print out a warning message here
tail = head = null;
} else {
tail.lNext = null;
trimItem.lPrev = null;
}
} else {
tail = head = null;
}
if (trimItem != null) {
trimItem.isTrimmed = true;
trimItem.lPrev = null;
trimCount++;
listSize--;
}
return trimItem;
}
/**
/**
* this item is just added to the cache
* @param item <code>CacheItem</code> that was created
* @return a overflow item; may be null
*
* this function checks if adding the new item results in a overflow;
* if so, it returns the item to be removed.
*
* Cache bucket is already synchronized by the caller
*/
protected CacheItem itemAdded(CacheItem item) {
boolean updateThreshold = false;
CacheItem overflow = null;
LruCacheItem lc = (LruCacheItem) item;
// set the timestamp
lc.lastAccessed = System.currentTimeMillis();
// update the LRU
synchronized (this) {
if (head != null) {
head.lPrev = lc;
lc.lNext = head;
lc.lPrev = null;
head = lc;
}
else {
head = tail = lc;
lc.lPrev = lc.lNext = null;
}
listSize++;
if (isThresholdReached()) {
if (!isUnbounded)
overflow = trimLru(lc.lastAccessed);
else
updateThreshold = true;
}
}
// update the base cache threshold if needed
if (updateThreshold)
super.handleOverflow();
return overflow;
}
/**
* this item is accessed
* @param item <code>CacheItem</code> accessed
*
* Cache bucket is already synchronized by the caller
*/
protected void itemAccessed(CacheItem item) {
LruCacheItem lc = (LruCacheItem) item;
synchronized (this) {
// if the item is already trimmed from the LRU list, nothing to do.
if (lc.isTrimmed)
return;
// update the timestamp
lc.lastAccessed = System.currentTimeMillis();
LruCacheItem prev = lc.lPrev;
LruCacheItem next = lc.lNext;
// update the LRU list
if (prev != null) {
// put the item at the head of LRU list
lc.lPrev = null;
lc.lNext = head;
head.lPrev = lc;
head = lc;
// patch up the previous neighbors
prev.lNext = next;
if (next != null)
next.lPrev = prev;
else
tail = prev;
}
}
}
/**
* item value has been refreshed
* @param item <code>CacheItem</code> that was refreshed
* @param oldSize size of the previous value that was refreshed
* Cache bucket is already synchronized by the caller
*/
protected void itemRefreshed(CacheItem item, int oldSize) {
itemAccessed(item);
}
/**
* item value has been removed from the cache
* @param item <code>CacheItem</code> that was just removed
*
* Cache bucket is already synchronized by the caller
*/
protected void itemRemoved(CacheItem item) {
LruCacheItem l = (LruCacheItem) item;
// remove the item from the LRU list
synchronized (this) {
LruCacheItem prev = l.lPrev;
LruCacheItem next = l.lNext;
// if the item is already trimmed from the LRU list, nothing to do.
if (l.isTrimmed)
return;
// patch up the neighbors and make sure head/tail are correct
if (prev != null)
prev.lNext = next;
else
head = next;
if (next != null)
next.lPrev = prev;
else
tail = prev;
l.lPrev = l.lNext = null;
listSize--;
}
}
/**
* trim the expired entries from the cache.
* @param maxCount maximum number of invalid entries to trim
* specify Integer.MAX_VALUE to trim all invalid entries
* This call is to be scheduled by a thread managed by the container.
*
* NOTE: this algorithm assumes that all the entries in the cache have
* identical timeout (otherwise traversing from tail won't be right).
*/
public void trimExpiredEntries(int maxCount) {
int count = 0;
LruCacheItem item;
long currentTime = System.currentTimeMillis();
ArrayList list = new ArrayList();
synchronized (this) {
// traverse LRU list till we reach a valid item; remove them at once
for (item = tail; item != null && count < maxCount;
item = item.lPrev) {
if (timeout != NO_TIMEOUT &&
(item.lastAccessed + timeout) <= currentTime) {
item.isTrimmed = true;
list.add(item);
count++;
} else
break;
}
// if there was at least one invalid item then item != tail.
if (item != tail) {
if (item != null)
item.lNext = null;
else
head = null;
tail = item;
}
listSize -= count;
trimCount += count;
}
// trim the items from the BaseCache from the old tail backwards
for (int index=list.size()-1; index >= 0; index--) {
trimItem((LruCacheItem) list.get(index));
}
}
/**
* get generic stats from subclasses
*/
/**
* get the desired statistic counter
* @param key to corresponding stat
* @return an Object corresponding to the stat
* See also: Constant.java for the key
*/
public Object getStatByName(String key) {
Object stat = super.getStatByName(key);
if (stat == null && key != null) {
if (key.equals(Constants.STAT_LRUCACHE_LIST_LENGTH))
stat = Integer.valueOf(listSize);
else if (key.equals(Constants.STAT_LRUCACHE_TRIM_COUNT))
stat = Integer.valueOf(trimCount);
}
return stat;
}
public Map getStats() {
Map stats = super.getStats();
stats.put(Constants.STAT_LRUCACHE_LIST_LENGTH,
Integer.valueOf(listSize));
stats.put(Constants.STAT_LRUCACHE_TRIM_COUNT,
Integer.valueOf(trimCount));
return stats;
}
/** default CacheItem class implementation ***/
protected static class LruCacheItem extends CacheItem {
// double linked LRU list
protected LruCacheItem lNext;
protected LruCacheItem lPrev;
protected boolean isTrimmed;
protected long lastAccessed;
protected LruCacheItem(int hashCode, Object key, Object value, int size) {
super(hashCode, key, value, size);
}
}
}
|
