Dennis Reedy (JIRA) wrote:
Dennis Reedy created RIVER-417:
----------------------------------
Summary: com.sun.jini.outrigger.FastList fails to compile using
Java 7
Key: RIVER-417
URL: https://issues.apache.org/jira/browse/RIVER-417
Project: River
Issue Type: Bug
Reporter: Dennis Reedy
Inner class Node has private properties that are accessed by inner class
FastListIteratorImpl
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
Are you sure? Which version?
package com.sun.jini.outrigger;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.atomic.AtomicLong;
/**
* 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.
*
* @param <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.
*/
class FastList<T extends FastList.Node> implements Iterable<T> {
/**
* The type parameter for the FastList, T, must extend this type,
and all
* nodes added to the list are of type T.
*
* A node can be added to a list at most once. Any attempt to add it
again
* will result in an IllegalStateException.
*
*/
static class Node {
/**
* True if this node has been removed from its list. Protected by
* synchronization on the Node when an exact answer is needed,
but often
* checked without synchronization to skip work of the Node is
reported
* as removed. Transitions only from false to true.
*/
private volatile boolean removed;
/**
* This node does not need to be shown to scans with index
greater than
* or equal to this index.
*/
private volatile long index;
/**
* null until the node is added to a list, then a reference to
the list.
* Once added to a list, it cannot be added to another. It can
only be
* removed from the list to which it was added. Protected by
* synchronization on the node.
*/
private FastList<?> list;
/**
* Remove this node from its list.
*
* @return true if this node has never previously been removed,
false if
* it has already been removed.
*/
synchronized boolean remove() {
if (removed) {
return false;
}
removed = true;
return true;
}
synchronized void markOnList(FastList<?> list) {
setList(list);
}
/**
* Report whether the node has been removed. If the result is
true the
* node has definitely been removed. If it is false, the node
may still
* have been removed. To get a fully reliable result,
synchronize on the
* node.
*/
public boolean removed() {
return removed;
}
/**
* @return the index
*/
long getIndex() {
return index;
}
/**
* @param index the index to set
*/
void setIndex(long index) {
this.index = index;
}
/**
* @return the list
*/
FastList<?> getList() {
return list;
}
/**
* @param list the list to set
*/
void setList(FastList<?> list) {
this.list = list;
}
}
private class FastListIteratorImpl implements Iterator<T> {
/* The last node returned as a next() result, null
* if there is none, or it has already been removed.
*/
private T removable;
/* The node to be returned by the next call to next().*/
private T next;
/* Index of the first node added after this iterator's
construction. */
private final long index;
/* Iterator over the underlying ConcurrentLinkedQueue.*/
private final Iterator<T> baseIterator;
private FastListIteratorImpl() {
index = nextIndex.get();
baseIterator = baseQueue.iterator();
next = getNext();
}
public boolean hasNext() {
return next != null;
}
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
removable = next;
next = getNext();
return removable;
}
public void remove() {
if (removable != null) {
removable.remove();
removable = null;
} else {
throw new IllegalStateException();
}
}
/**
* Find the next eligible node, null if there is none. skip over
removed
* nodes, and stop on reaching a Node that was added after this scan
* started.
*
* @return The next eligible node, null if there is none.
*/
private T getNext() {
T result = null;
while (baseIterator.hasNext()) {
T node = baseIterator.next();
if (node.getIndex() >= index) {
/* Finished, no appropriate nodes.*/
break;
}
if (node.removed()) {
/* Tell the base list to drop it */
baseIterator.remove();
} else {
/* Found a node to return. */
result = node;
break;
}
}
return result;
}
}
/**
* 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.
*/
private final AtomicLong nextIndex = new AtomicLong(0);
/**
* The underlying queue.
*/
private final Queue<T> baseQueue = new ConcurrentLinkedQueue<T>();
/**
* Add a node to the tail of the list.
*
* @param node
* Each node can only be added once, regardless of removal.
* @throws IllegalArgumentException
* The node has been added to a list previously.
*/
public void add(T node) {
synchronized (node) {
if (node.getList() == null) {
node.setList(this);
} else {
throw new IllegalArgumentException("Attempt to reuse node "
+ node);
}
}
node.setIndex(nextIndex.getAndIncrement());
baseQueue.add(node);
}
/**
* Remove the node.
*
* @param node
* @return 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.
*/
public boolean remove(T node) {
synchronized (node) {
if (node.getList() != this) {
throw new IllegalArgumentException(
"Cannot remove a node from a list it is not on");
}
return node.remove();
}
}
/**
* Scan the list, physically removing nodes that have already been
logically
* removed.
*/
public void reap() {
long stopIndex = nextIndex.get();
Iterator<T> it = baseQueue.iterator();
while (it.hasNext()) {
T node = it.next();
if (node.getIndex() >= stopIndex) {
// Done enough
return;
}
if (node.removed()) {
it.remove();
}
}
}
/*
* The returned Iterator returns all elements that were
* added to the FastList, and not removed, before the iterator() call.
* It will return no elements that were added after the iterator() call
* returned. Elements that were added in parallel with the iterator()
* call may be returned, depending on exact timing.
*
* It makes reasonable efforts to avoid returning removed elements, but
* only a synchronized check can guaranteed up-to-date removal
information.
* (non-Javadoc)
* @see java.lang.Iterable#iterator()
*/
public Iterator<T> iterator() {
return new FastListIteratorImpl();
}
/**
* 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.
*
* @return
*/
Iterator<T> rawIterator() {
return baseQueue.iterator();
}
}
