Mega Code Archive
Async LRU List
<![CDATA[
// LRUList.java
// $Id: LRUList.java,v 1.7 2000/08/16 21:37:58 ylafon Exp $
// (c) COPYRIGHT MIT and INRIA, 1996.
// Please first read the full copyright statement in file COPYRIGHT.html
// AsyncLRUList.java
// $Id: AsyncLRUList.java,v 1.10 1998/01/22 14:24:58 bmahe Exp $
// (c) COPYRIGHT MIT and INRIA, 1996.
// Please first read the full copyright statement in file COPYRIGHT.html
// All locks allocated from left to right
public class AsyncLRUList extends LRUList {
public final synchronized void toHead(LRUAble node) {
_remove(node) ;
if ( head.next != null ) {
node.setNext(head.next) ;
head.next.setPrev(node) ;
node.setPrev(head) ;
head.next = node ;
} else {
node.setNext(head.next) ;
// head.next.setPrev(node) ;
node.setPrev(head) ;
head.next = node ;
}
}
public final synchronized void toTail(LRUAble node) {
_remove(node) ;
if ( tail.prev != null ) {
node.setPrev(tail.prev) ;
tail.prev.setNext(node) ;
node.setNext(tail) ;
tail.prev = node ;
} else {
node.setPrev(tail.prev) ;
// tail.prev.setNext(node) ;
node.setNext(tail) ;
tail.prev = node ;
}
}
private final synchronized void _remove(LRUAble node) {
LRUAble itsPrev = node.getPrev() ;
if(itsPrev==null)
return ;
LRUAble itsNext = node.getNext() ;
node.setNext(null);
node.setPrev(null);
itsPrev.setNext(itsNext) ;
if ( itsNext == null )
return;
itsNext.setPrev(itsPrev) ;
}
public final synchronized LRUAble remove(LRUAble node) {
_remove(node) ;
node.setNext((LRUAble) null) ;
node.setPrev((LRUAble) null) ;
return node ;
}
public final synchronized LRUAble getTail() {
if ( tail.prev == null )
return null;
LRUAble prev = tail.prev ;
return (prev == head) ? null : prev;
}
public final synchronized LRUAble getHead() {
LRUAble next = head.next;
return (next == tail) ? null : next;
}
public final synchronized LRUAble removeTail() {
return (tail.prev != head) ? remove(tail.prev) : null;
}
public final synchronized LRUAble getNext(LRUAble node) {
LRUAble next = node.getNext();
return ((next == tail) || (next == head)) ? null : next;
}
public final synchronized LRUAble getPrev(LRUAble node) {
LRUAble prev = node.getPrev();
return ((prev == tail) || (prev == head)) ? null : prev;
}
}
abstract class LRUList {
protected LRUNode head ;
protected LRUNode tail ;
public LRUList()
{
this.head = new LRUNode() ;
this.tail = new LRUNode() ;
head.prev = null ;
head.next = tail ;
tail.prev = head ;
tail.next = null ;
}
/**
* Moves node to front of list. It can be a new node, or it can be
* an existing node.
* @param node the node
*/
public abstract void toHead(LRUAble node) ;
/**
* Moves node to back of list. It can be a new node, or it can be
* an existing node.
* @param node the node
*/
public abstract void toTail(LRUAble node) ;
/**
* Removes node if it's in list.
* Does nothing if it's not.
* When a node is removed, both its links are set to null.
* @param node The node to remove
* @return the same node
*/
public abstract LRUAble remove(LRUAble node) ;
/**
* Obtain the backmost node.
* @return the backmost node, or null if list is empty
*/
public abstract LRUAble getTail() ;
/**
* Obtain the frontmost node.
* @return the frontmost node, or null if list is empty
*/
public abstract LRUAble getHead() ;
/**
* Obtain the backmost node, and remove it from list too.
* @return the backmost node, or null if list is empty
*/
public abstract LRUAble removeTail() ;
/**
* Get the next node of this list.
* @return The next node, or <strong>null</strong> if this one was
* last.
*/
abstract public LRUAble getNext(LRUAble node) ;
/**
* Get the previous node of this list.
* @return The previous node, or <strong>null</strong> if this one was
* last.
*/
abstract public LRUAble getPrev(LRUAble node) ;
}
//LRUNode.java
//$Id: LRUNode.java,v 1.4 2003/02/14 16:14:56 ylafon Exp $
//(c) COPYRIGHT MIT and INRIA, 1996.
//Please first read the full copyright statement in file COPYRIGHT.html
class LRUNode implements LRUAble {
protected LRUAble prev ;
protected LRUAble next ;
public LRUNode() {
this.prev = null ;
this.next = null ;
}
public LRUNode(LRUAble prev,LRUAble next) {
this.prev = prev ;
this.next = next ;
}
public LRUAble getNext() {
return next ;
}
public LRUAble getPrev() {
return prev;
}
public void setPrev(LRUAble prev) {
this.prev = prev ;
}
public void setNext(LRUAble next) {
this.next = next ;
}
}
//LRUAble.java
//$Id: LRUAble.java,v 1.3 1998/01/22 14:25:09 bmahe Exp $
//(c) COPYRIGHT MIT and INRIA, 1997.
//Please first read the full copyright statement in file COPYRIGHT.html
interface LRUAble {
public LRUAble getNext() ;
public LRUAble getPrev() ;
public void setNext(LRUAble next) ;
public void setPrev(LRUAble prev) ;
}
]]>