nucleus/common/common-util/src/main/java/com/sun/appserv/util/cache/LruCache.java - glassfish - Git at Google

 /*
  * Copyright (c) 1997, 2018 Oracle and/or its affiliates. All rights reserved.
  *
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Public License v. 2.0, which is available at
  * http://www.eclipse.org/legal/epl-2.0.
  *
  * This Source Code may also be made available under the following Secondary
  * Licenses when the conditions for such availability set forth in the
  * Eclipse Public License v. 2.0 are satisfied: GNU General Public License,
  * version 2 with the GNU Classpath Exception, which is available at
  * https://www.gnu.org/software/classpath/license.html.
  *
  * SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
  */

 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) {

         if(tail == null)
             return null;

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

             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;
         if(! (item instanceof LruCacheItem))
             return 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) {
         if(head == null)
             return;
         if(item == null)
             return;
         if(! (item instanceof LruCacheItem))
             return;
         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) {
         if(! (item instanceof LruCacheItem))
             return;
         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);
         }

         /**
          * Return the next item
          */
          public LruCacheItem getLNext() {
              return lNext;
          }

         /**
          * Reset the next item reference
          */
          public void setLNext(LruCacheItem item) {
              lNext = item;
          }

         /**
          * Return the previous item
          */
          public LruCacheItem getLPrev() {
              return lPrev;
          }

         /**
          * Reset the previous item reference
          */
          public void setLPrev(LruCacheItem item) {
              lPrev = item;
          }

         /**
          * Return <code>true</code> if this item is trimmed
          */
          public boolean isTrimmed() {
              return isTrimmed;
          }

         /**
          * Set the trimmed flag
          */
          public void setTrimmed(boolean value) {
              isTrimmed = value;
          }

         /**
          * Return the last accessed timestamp
          */
          public long getLastAccessed() {
              return lastAccessed;
          }

         /**
          * Reset the last accessed timestamp
          */
          public void setLastAccessed(long l) {
              lastAccessed = l;
          }
     }
 }
	/*
	* Copyright (c) 1997, 2018 Oracle and/or its affiliates. All rights reserved.
	*
	* This program and the accompanying materials are made available under the
	* terms of the Eclipse Public License v. 2.0, which is available at
	* http://www.eclipse.org/legal/epl-2.0.
	*
	* This Source Code may also be made available under the following Secondary
	* Licenses when the conditions for such availability set forth in the
	* Eclipse Public License v. 2.0 are satisfied: GNU General Public License,
	* version 2 with the GNU Classpath Exception, which is available at
	* https://www.gnu.org/software/classpath/license.html.
	*
	* SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
	*/

	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) {

	if(tail == null)
	return null;

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

	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;
	if(! (item instanceof LruCacheItem))
	return 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) {
	if(head == null)
	return;
	if(item == null)
	return;
	if(! (item instanceof LruCacheItem))
	return;
	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) {
	if(! (item instanceof LruCacheItem))
	return;
	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);
	}

	/**
	* Return the next item
	*/
	public LruCacheItem getLNext() {
	return lNext;
	}

	/**
	* Reset the next item reference
	*/
	public void setLNext(LruCacheItem item) {
	lNext = item;
	}

	/**
	* Return the previous item
	*/
	public LruCacheItem getLPrev() {
	return lPrev;
	}

	/**
	* Reset the previous item reference
	*/
	public void setLPrev(LruCacheItem item) {
	lPrev = item;
	}

	/**
	* Return <code>true</code> if this item is trimmed
	*/
	public boolean isTrimmed() {
	return isTrimmed;
	}

	/**
	* Set the trimmed flag
	*/
	public void setTrimmed(boolean value) {
	isTrimmed = value;
	}

	/**
	* Return the last accessed timestamp
	*/
	public long getLastAccessed() {
	return lastAccessed;
	}

	/**
	* Reset the last accessed timestamp
	*/
	public void setLastAccessed(long l) {
	lastAccessed = l;
	}
	}
	}