com.sun.jini.outrigger
Class FastList<T extends FastList.Node>

java.lang.Object
  extended by com.sun.jini.outrigger.FastList<T>
Type Parameters:
T - Node type, required to extend FastList.Node so that the FastList can keep working data for each Node without using mapping or extra data structures.
All Implemented Interfaces:
Iterable<T>

 class FastList<T extends FastList.Node>
extends Object
implements Iterable<T>

Simplified list for rapid append, removal, and scanning from multiple threads. It is intended as a substitute for the previous FastList, but uses an Iterator rather than limiting a thread to a single scan at a time. This version is completely rewritten, based on java.util.concurrent.ConcurrentLinkedQueue. It provides two features in addition to those of ConcurrentLinkedQueue: 1. Fast logical removal of a Node from the middle of the list. The node is merely marked as removed. It will be physically removed during a reap, or any Iterator scan that reaches it after it is marked. 2. Guaranteed finite scans. If a node is added strictly after construction of an Iterator, it will not be shown by the Iterator. Concurrency: A FastList object can be freely accessed by multiple threads without synchronization. Within a thread, the implementation synchronizes on at most one node at a time. Conventionally, a caller who synchronizes on more than one node must do so in order of appearance in the list. While synchronized on the FastList object, a caller must not synchronize on any FastList node or call any FastList method. The Iterator returned by iterator() is not multi-thread safe. Callers must ensure it is accessed by at most one thread at a time, and that all actions on it in one thread happen-before any actions in a later thread.


Nested Class Summary
private  class FastList.FastListIteratorImpl
           
(package private) static class FastList.Node
          The type parameter for the FastList, T, must extend this type, and all nodes added to the list are of type T.
 
Field Summary
private  Queue<T> baseQueue
          The underlying queue.
private  java.util.concurrent.atomic.AtomicLong nextIndex
          The next index, a modified form of timestamp.
 
Constructor Summary
FastList()
           
 
Method Summary
 void add(T node)
          Add a node to the tail of the list.
 Iterator<T> iterator()
           
(package private)  Iterator<T> rawIterator()
          Iterator that includes all physically present items, regardless of when they were added or whether they have been logically removed.
 void reap()
          Scan the list, physically removing nodes that have already been logically removed.
 boolean remove(T node)
          Remove the node.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

nextIndex

private final java.util.concurrent.atomic.AtomicLong nextIndex
The next index, a modified form of timestamp. Each Node is assigned a strictly increasing index on being added to a FastList. Each Iterator scan stops (hasNext() false) when it reaches a Node that has an index at least as high as the value of nextIndex when the Iterator was created. This ensures finite scan lengths, even if nodes are being added continuously during the scan.


baseQueue

private final Queue<T extends FastList.Node> baseQueue
The underlying queue.

Constructor Detail

FastList

FastList()
Method Detail

add

public void add(T node)
Add a node to the tail of the list.

Parameters:
node - Each node can only be added once, regardless of removal.
Throws:
IllegalArgumentException - The node has been added to a list previously.

remove

public boolean remove(T node)
Remove the node.

Parameters:
node -
Returns:
true if this is the first remove call for this node, false if the node has already been removed.
Throws:
IllegalArgumentException - The node has not been added to this FastList.

reap

public void reap()
Scan the list, physically removing nodes that have already been logically removed.


iterator

public Iterator<T> iterator()
Specified by:
iterator in interface Iterable<T extends FastList.Node>

rawIterator

Iterator<T> rawIterator()
Iterator that includes all physically present items, regardless of when they were added or whether they have been logically removed. This method is intended for testing. For example, it can be used to verify that a reap() call does in fact physically remove the items it should remove.

Returns:


Copyright 2007-2010, multiple authors.
Licensed under the Apache License, Version 2.0, see the NOTICE file for attributions.