James Stauffer
From: Greg Nudelman [mailto:[EMAIL PROTECTED]
Sent: Tuesday, March 04, 2003 3:35 PM
To: jdjlist
Subject: [jdjlist] Re: Caching
Thanks a bunch Phillip! I'm looking carefully at this very nice implementation by the Turbine folks.
I've also come across an Enhydra LRU cache manager class that uses the linked list as a sort of the heap structure to keep track of least recently used objects. I was curious why they chose a linked list... I would think some kind of Java "heap" implementation will give the LRU element with the O(c) and will perform inserts with O(log2(n)). However, these guys keep the linked list pointers in the cache hash itself, along with the head and tail pointers, so every lookup and re-order operation becomes an O(c). Very nice LRU implementation.
Greg
/* * Enhydra Java Application Server Project * * The contents of this file are subject to the Enhydra Public License * Version 1.1 (the "License"); you may not use this file except in * compliance with the License. You may obtain a copy of the License on * the Enhydra web site ( http://www.enhydra.org/ ). * * Software distributed under the License is distributed on an "AS IS" * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See * the License for the specific terms governing rights and limitations * under the License. * * The Initial Developer of the Enhydra Application Server is Lutris * Technologies, Inc. The Enhydra Application Server and portions created * by Lutris Technologies, Inc. are Copyright Lutris Technologies, Inc. * All Rights Reserved. * * Contributor(s): * * $Id: LRUCache.java,v 1.7.12.1 2000/10/19 17:58:53 jasona Exp $ */
package com.lutris.util;
import java.util.Hashtable;
/**
* This class
implements a fixed size Least-Recently-Used cache.
* The cache has a maximum size specified when it is
created. When
* an item is added to
the cache, if the cache is already at the
* maximum size the least recently used item is deleted,
then the
* new item is added.
<P>
*
* The only two methods that count as "using" the object
(for the
* least-recently-used
algorithm) are <CODE>add()</CODE> and
* <CODE>get()</CODE>. <P>
*
* The items
cached are refered to by keys, just like a Hashtable.
*
* @author Andy John
* @version $Revision: 1.7.12.1 $
*/
public class LRUCache {
/*
* Maximum allowed size of the
cache.
*/
private int maxSize;
/*
* The current size of the cache.
*/
private int currentSize;
/*
* This hashtable stores all the items, and
does all the searching.
*/
private Hashtable cache;
/*
* A linked list of these structs defines
the ordering from
*
newest to oldest. The nodes are stored in the hashtable, so
* that constant-time access can locate a
node.
*/
private class Node {
Node prev, next;
Object key;
Object item;
int size;
}
/*
* The linked list. This is ONLY for
keeping an ordering. All
* searching is done via the hashtable. All acceses to this linked
* list are constant-time.
*/
private Node head, tail;
/**
* Create a new, empty cache.
*
* @param maxSize
* The maxmimum size of the items allowed
to be in the cache.
*
Since the size of an item defaults to 1, this is normally the
* number of items allowed in the
cache.
* When this limit
is reached, the "oldest" items are deleted to
* make room for the new item, so the total
size of the cache
* (the
sum of the sizes of all the items it contains)
* does not exceed the specified
limit.
*/
public LRUCache(int maxSize) {
this.maxSize = maxSize;
clear();
}
/**
* Returns the total size of the
items in the cache.
* If all the items were added with the default size of 1,
* this is the number of
items in the cache.
*
* @return
* The sum of the sizes of the items in the
cache.
*/
public synchronized int getSize() {
return currentSize;
}
/**
* Returns the maxmimum number of
items allowed in the cache.
*
* @return
* The maximum number of items allowed in
the cache.
*/
public synchronized int getMaxSize() {
return
maxSize;
}
/**
* Add an object to the cache, with a
default size of 1.
* If the cache is full, the oldest items will be deleted to make
room.
* The item
becomes the "newest" item.
*
* @param key
* The key used to refer to the
object when calling <CODE>get()</CODE>.
* @param item
* The item to add to the
cache.
*/
public synchronized void add(Object key, Object item)
{
add(key,
item , 1);
}
/**
* Add an object to the cache.
* If the cache is
full, the oldest items will be deleted to make room.
* The item becomes the "newest"
item.
*
* @param key
* The key used to refer to the
object when calling <CODE>get()</CODE>.
* @param item
* The item to add to the
cache.
* @param size
* How large is the object?
This counts against the maximim size
* specified when the cache was
created.
*/
public synchronized void add(Object key, Object item,
int size) {
// Throw out old one if reusing a key.
if
(cache.containsKey(key))
remove(key);
// Keep throwing out old items to make space. Stop if empty.
while (currentSize + size >
maxSize) {
if
(!deleteLRU())
break;
}
if
(currentSize + size > maxSize)
//
Just not enough room.
return;
Node
node = new Node();
node.key = key;
node.item =
item;
node.size = size;
cache.put(key, node);
insertNode(node);
currentSize += size;
}
/**
* Fetch an item from the cache.
Returns null if not found.
* The item becomes the "newest" item.
*
* @param key
* The key used to refer to the
object when <CODE>add()</CODE>
* was called.
* @return
* The item, or null if not
found.
*/
public synchronized Object get(Object key) {
Node node =
(Node)cache.get(key);
if (node == null)
return
null;
deleteNode(node);
insertNode(node); // Move to
the front of the list.
return node.item;
}
/**
* Remove an
item from the cache.
*
* @param key
* The key used to refer to the
object when <CODE>add()</CODE>
* was called.
* @return
* The item that was removed, or null
if not found.
*/
public synchronized Object
remove(Object key) {
Node node =
(Node)cache.remove(key);
if (node == null)
return
null;
deleteNode(node);
currentSize -=
node.size;
return node.item;
}
/**
* Does the cache contain the given
key?
*
* @param key
* The key used to refer to the
object when <CODE>add()</CODE>
* was called.
* @return
* true if the key was found.
*/
public synchronized boolean containsKey(Object key)
{
return
cache.containsKey(key);
}
/**
* Delete all the items from the
cache.
*/
public synchronized void clear() {
cache = new
Hashtable();
head = tail = null;
currentSize = 0;
}
/*
* Insert the node at the front of the
linked list.
* This only
does linked list management.
*/
private void insertNode(Node node)
{
node.next =
head;
node.prev = null;
if (head != null)
head.prev = node;
head = node;
if (tail == null)
tail =
node;
}
/*
* Delete the node from anywhere in the
linked list.
* This only
does linked list management.
*/
private void deleteNode(Node node)
{
if
(node.prev != null)
node.prev.next = node.next;
else
head =
node.next;
if
(node.next != null)
node.next.prev = node.prev;
else
tail =
node.prev;
}
/*
* Delete the least
recently used item. This is the one at the
* tail of the list. Returns true if an
item was deleted,
* or
false if the cache is empty.
*/
private boolean deleteLRU()
{
if (tail ==
null)
return
false;
currentSize -= tail.size;
cache.remove(tail.key);
deleteNode(tail);
return true;
}
/**
* Returns a string describing the contents
of the cache.
*/
public synchronized String toString()
{
StringBuffer buf = new StringBuffer();
buf.append("LRU ");
buf.append(currentSize);
buf.append("/");
buf.append(maxSize);
buf.append(" Order: ");
Node n =
head;
while
(n != null) {
buf.append(n.key);
if
(n.next != null)
buf.append(", ");
n =
n.next;
}
return
buf.toString();
}
}
-----Original Message-----
From: Phillip
DuLion [mailto:[EMAIL PROTECTED]]
Sent: Tuesday, March 04, 2003 11:25 AM
To:
jdjlist
Subject: [jdjlist] Re: Caching
While researching JCache, I did come across Apache JCS.
This seems to
be the most mature open source product
that I was able to find, which
doesn't say much.
There are no packages or binaries, and CVS is
required
to obtain the source code.
http://jakarta.apache.org/turbine/jcs/
Phillip.
--- Greg Nudelman <[EMAIL PROTECTED]> wrote:
> We're have a home-grown Java application and would like to
introduce
> some
> kind of
app-level cache manager. I'm interested if someone has made
> anything like that -- shareware/custom packages, a study
about the
> size of
>
objects in memory, anything like that.
>
> All suggestions welcome. Thanks!
>
> Greg
>
>
> ---
> You are currently subscribed to jdjlist as:
[EMAIL PROTECTED]
> To unsubscribe send a blank
email to
>
[EMAIL PROTECTED]
> http://www.sys-con.com/fusetalk
>
---
You are currently subscribed to
jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a
blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk ---
You are currently subscribed to jdjlist as: [EMAIL PROTECTED]
To unsubscribe send a blank email to [EMAIL PROTECTED]
http://www.sys-con.com/fusetalk
