Author: pats
Date: Tue Jan 25 04:03:48 2011
New Revision: 1063132
URL: http://svn.apache.org/viewvc?rev=1063132&view=rev
Log:
Reimplement outrigger's FastList, based on java.util.ConcurrentLinkedQueue.
Modify its users to reflect the switch from explicit link-chasing to Iterator.
Modified:
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/EntryHolder.java
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/FastList.java
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/WatchersForTemplateClass.java
Modified:
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/EntryHolder.java
URL:
http://svn.apache.org/viewvc/incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/EntryHolder.java?rev=1063132&r1=1063131&r2=1063132&view=diff
==============================================================================
---
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/EntryHolder.java
(original)
+++
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/EntryHolder.java
Tue Jan 25 04:03:48 2011
@@ -18,6 +18,7 @@
package com.sun.jini.outrigger;
import java.util.Hashtable;
+import java.util.Iterator;
import java.util.Set;
import java.util.WeakHashMap;
import java.util.logging.Level;
@@ -38,7 +39,7 @@ import net.jini.core.transaction.server.
*/
class EntryHolder implements TransactionConstants {
/** The list that holds the handles */
- private final FastList contents = new FastList();
+ private final FastList<EntryHandle> contents = new FastList<EntryHandle>();
/**
* The map of cookies to handles, shared with the
@@ -114,44 +115,44 @@ class EntryHolder implements Transaction
* @see #attemptCapture
*/
EntryHandle hasMatch(EntryRep tmpl, TransactableMgr txn, boolean takeIt,
- Set conflictSet, Set lockedEntrySet,
- WeakHashMap provisionallyRemovedEntrySet)
- throws CannotJoinException
- {
- matchingLogger.entering("EntryHolder", "hasMatch");
-
- EntryHandle handle = (EntryHandle) contents.head();
- if (handle == null)
- return null; // Nothing here
-
- final EntryHandleTmplDesc desc =
- EntryHandle.descFor(tmpl, handle.rep().numFields());
- final long startTime = System.currentTimeMillis();
-
- for (;handle != null; handle = (EntryHandle) handle.next()) {
- if (handle.removed())
- continue;
-
- // Quick reject -- see the if handle mask is incompatible
- if ((handle.hash() & desc.mask) != desc.hash)
- continue;
+ Set conflictSet, Set lockedEntrySet,
+ WeakHashMap provisionallyRemovedEntrySet)
+ throws CannotJoinException {
+ matchingLogger.entering("EntryHolder", "hasMatch");
+ EntryHandleTmplDesc desc = null;
+ long startTime = 0;
+
+ for (EntryHandle handle : contents) {
+
+ if (startTime == 0) {
+ // First time through
+ desc = EntryHandle.descFor(tmpl, handle.rep().numFields());
+ startTime = System.currentTimeMillis();
+ }
+
+ if (handle.removed())
+ continue;
+
+ // Quick reject -- see the if handle mask is incompatible
+ if ((handle.hash() & desc.mask) != desc.hash)
+ continue;
+
+ final EntryRep rep = handle.rep();
+
+ if (!tmpl.matches(rep))
+ continue;
+
+ final boolean available = confirmAvailabilityWithTxn(rep, handle,
+ txn, takeIt, startTime, conflictSet, lockedEntrySet,
+ provisionallyRemovedEntrySet);
+
+ if (available)
+ return handle;
+ }
- final EntryRep rep = handle.rep();
-
- if (!tmpl.matches(rep))
- continue;
-
- final boolean available =
- confirmAvailabilityWithTxn(rep, handle, txn,
- takeIt, startTime, conflictSet, lockedEntrySet,
- provisionallyRemovedEntrySet);
-
- if (available)
- return handle;
- }
-
- return null;
+ return null;
}
+
/**
* Debug method: Dump out the state of this holder, printing out
@@ -160,9 +161,7 @@ class EntryHolder implements Transaction
void dump(String name) {
try {
System.out.println(name);
- for (EntryHandle handle = (EntryHandle) contents.head();
- handle != null;
- handle = (EntryHandle) handle.next())
+ for (EntryHandle handle : contents)
{
EntryRep rep = handle.rep();
System.out.println(" " + rep + ", " + rep.entry());
@@ -495,6 +494,18 @@ class EntryHolder implements Transaction
}
/**
+ * Get the head of the contents list
+ * @return The head of the contents list, if it exists.
+ * null if the list is empty.
+ */
+ private EntryHandle getContentsHead(){
+ for(EntryHandle head : contents){
+ return head;
+ }
+ return null;
+ }
+
+ /**
* Add new new entry to the holder. Assumes the lock
* on the handle is held if there is a possibility
* of concurrent access.
@@ -530,7 +541,7 @@ class EntryHolder implements Transaction
* exposing it to others (even though shareWith will
* not change handle's state materially).
*/
- final EntryHandle head = (EntryHandle) contents.head();
+ final EntryHandle head = getContentsHead();
if (head != null && head != handle)
rep.shareWith(head.rep());
@@ -547,7 +558,7 @@ class EntryHolder implements Transaction
* empty.
*/
String[] supertypes() {
- final EntryHandle head = (EntryHandle)contents.head();
+ final EntryHandle head = getContentsHead();
if (head == null)
return null;
return head.rep().superclasses();
@@ -565,56 +576,36 @@ class EntryHolder implements Transaction
* The class that implements <code>RepEnum</code> for this class.
*/
private class SimpleRepEnum implements RepEnum {
- /** The last node we saw */
- private EntryHandle handle;
+ private Iterator<EntryHandle> contentsIterator;
private TransactableMgr mgr;
private long startTime;
- int count = 0;
-
- SimpleRepEnum(TransactableMgr mgr) {
- this.mgr = mgr;
- handle = (EntryHandle) contents.head();
- startTime = System.currentTimeMillis();
- }
-
- // inherit doc comment from superclass
- public EntryRep nextRep() {
- iteratorLogger.entering("SimpleRepEnum", "nextRep");
-
- /* Since we might be accessing our iteration from a
- * different thread than the one that began the traversal,
- * we need to inform the FastList that this thread should
- * be allowed to assume that traversal without throwing
- * an exception. FastList must therefore update its data
- * structures to accommodate the traversal from this new
- * thread. [It would be better if did this once per a thread...]
- */
-
- if (handle != null)
- handle.restart();
- /* Skip over handles which are either removed or unable
- * to perform a READ operation.
- */
-
- while (handle != null &&
- (!handle.canPerform(mgr, TransactableMgr.READ) ||
- isExpired(startTime, handle) ||
- handle.removed()
- ))
- {
- handle = (EntryHandle) handle.next();
- iteratorLogger.log(Level.FINEST,
- "advanced current handle to {0}", handle);
- }
+ SimpleRepEnum(TransactableMgr mgr) {
+ this.mgr = mgr;
+ startTime = System.currentTimeMillis();
+ contentsIterator = contents.iterator();
+ }
+
+ // inherit doc comment from superclass
+ public EntryRep nextRep() {
+ iteratorLogger.entering("SimpleRepEnum", "nextRep");
+ while (contentsIterator.hasNext()) {
+ EntryHandle handle = contentsIterator.next();
+ iteratorLogger.log(Level.FINEST,
+ "advanced current handle to {0}", handle);
+ /*
+ * Skip over handles which are either removed or unable to
+ * perform a READ operation.
+ */
+ if (handle.canPerform(mgr, TransactableMgr.READ)
+ && !isExpired(startTime, handle) && !handle.removed())
{
+ return handle.rep();
+ }
- if (handle == null)
- return null;
+ }
- EntryHandle h = handle;
- handle = (EntryHandle) h.next();
- return h.rep();
- }
+ return null;
+ }
}
@@ -661,7 +652,7 @@ class EntryHolder implements Transaction
final private boolean takeThem;
/** <code>EntryHandleTmplDesc</code> for the templates */
- final private EntryHandleTmplDesc[] descs;
+ private EntryHandleTmplDesc[] descs;
/** Time used to weed out expired entries, ok if old */
@@ -671,7 +662,7 @@ class EntryHolder implements Transaction
* Current position in parent <code>EntryHolder</code>'s
* <code>contents</code>
*/
- private EntryHandle handle;
+ private Iterator<EntryHandle> contentsIterator;
/**
* Create a new <code>ContinuingQuery</code> object.
@@ -695,19 +686,7 @@ class EntryHolder implements Transaction
this.txn = txn;
this.takeThem = takeThem;
this.now = now;
- handle = (EntryHandle)contents.head();
-
- if (handle == null) {
- // nothing to search - first next will return null
- descs = null; // keep compiler happy
- return;
- }
-
- descs = new EntryHandleTmplDesc[tmpls.length];
- for (int i=0; i<tmpls.length; i++) {
- descs[i] = EntryHandle.descFor(this.tmpls[i],
- handle.rep().numFields());
- }
+ contentsIterator = contents.iterator();
}
/**
@@ -722,11 +701,10 @@ class EntryHolder implements Transaction
* expired entries, ok if old
*/
void restart(long now) {
- if (handle == null)
+ if (!contentsIterator.hasNext())
return;
this.now = now;
- handle.restart();
}
/**
@@ -772,11 +750,19 @@ class EntryHolder implements Transaction
throws CannotJoinException
{
matchingLogger.entering("ContinuingQuery", "next");
- if (handle == null)
- return null; // done
- for (; handle != null; handle = (EntryHandle)handle.next()) {
- if (handleMatch()) {
+
+ while (contentsIterator.hasNext()) {
+ EntryHandle handle = contentsIterator.next();
+ if(descs == null){
+ // first time
+ descs = new EntryHandleTmplDesc[tmpls.length];
+ for (int i=0; i<tmpls.length; i++) {
+ descs[i] = EntryHandle.descFor(tmpls[i],
+
handle.rep().numFields());
+ }
+ }
+ if (handleMatch(handle)) {
final boolean available =
confirmAvailabilityWithTxn(handle.rep(), handle, txn,
@@ -784,10 +770,7 @@ class EntryHolder implements Transaction
provisionallyRemovedEntrySet);
if (available) {
- // Don't want to return this guy twice.
- final EntryHandle rslt = handle;
- handle = (EntryHandle)handle.next();
- return rslt;
+ return handle;
}
}
}
@@ -799,7 +782,7 @@ class EntryHolder implements Transaction
* Returns <code>true</code> if handle has not been removed
* and matches one or more of the templates
*/
- private boolean handleMatch() {
+ private boolean handleMatch(EntryHandle handle) {
if (handle.removed())
return false;
@@ -868,10 +851,7 @@ class EntryHolder implements Transaction
// removed ("reaped") from the collection.
long now = System.currentTimeMillis();
- for (EntryHandle handle = (EntryHandle) contents.head();
- handle != null;
- handle = (EntryHandle) handle.next())
- {
+ for(EntryHandle handle : contents){
// Don't try to remove things twice
if (handle.removed()) {
continue;
Modified:
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/FastList.java
URL:
http://svn.apache.org/viewvc/incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/FastList.java?rev=1063132&r1=1063131&r2=1063132&view=diff
==============================================================================
---
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/FastList.java
(original)
+++
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/FastList.java
Tue Jan 25 04:03:48 2011
@@ -1,929 +1,188 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
package com.sun.jini.outrigger;
-import java.util.Map;
-import java.util.WeakHashMap;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Queue;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.atomic.AtomicLong;
+
/**
- * This class provides a low-synchronization list of objects. It is
- * designed to allow proper traversal of the list while objects are
- * being added and/or removed, and to allow simultaneous adds and
- * removals. Traversals must be done in a single thread; no fair handing
- * off a <code>Node</code> pointer to another thread to continue the
- * traversal! A single thread cannot perform two or more simultaneous
- * traversals, even if traversing different lists.
- * <p>
- * All this means that users of the list will occasionally see a
- * removed node in the list, because it may be marked removed after it
- * has been reached while traversing the list. This will be rare, but
- * it is up to the user of the list to skip over nodes that have been
- * removed if necessary, and to handle or avoid attempted re-removal of
- * a node. This is why <code>remove</code> returns a boolean -- if the
- * node has already been removed by the time the attempt to remove it
- * happens, <code>remove</code> will return <code>false</code>. This
- * is done synchronizing on the node itself. A typical piece of code
- * to remove would look like this:
- *
- * <pre>
- * public synchronized Value findMatch(Value matchFor) {
- * for (Value val = list.head(); val != null; val = val.next()) {
- * if (matchFor.matches(val)) {
- * if (!list.remove(n)) // oh, well -- someone got to it first
- * continue; // keep looking
- * return val; // it's ours to take!
- * }
- * }
- * return null;
- * }
- * </pre>
- *
- * This code assumes that getting a removed node will be rare enough
- * that there is no point in testing for it until a match is found.
- * If testing for a match was expensive, one might
- * <code>synchronize</code> on the node object and test it for being
- * removed and then try for matching, thus preventing any other
- * thread from attempting a match at the same time. In any case, the
- * <code>remove</code> test is itself atomic -- either it succeeds, or
- * it fails because someone got there first.
- *
- * <p>
- * <i>The Java(TM) Language Specification<i> details a memory model based on
- * local and global memories, apparently intended as a model for
- * multiprocessor caches. The specified memory model should be
- * supplemented by William Pugh's
- * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/";>work</a>
- * on the Java
- * programming language memory model and JSR 133.
- * <p>
- * In particular, the <code>volatile</code> keyword offers no practical
- * guarantees. The lock and unlock operations underlying the
- * <code>synchronized</code> language construct are the primary mechanisms
- * for communicating between threads. A lock operation forces stale values
- * to be flushed from the locking thread's cache: any values subsequently
- * read by the thread are either read from main memory or are cached values
- * no older than the time the lock was acquired. An unlock operation forces
- * dirty cache entries to be written to main memory: any values written by
- * the thread up to then must be force-written to main memory before the
- * unlock can complete.
- * <p>
- * In every other respect, access to shared memory by threads is
- * arbitrary. Updates can happen at any time and in any order. In
- * particular, if one thread initializes a new Node and adds it to the end
- * of the list, it's possible for a different thread to see the pointer to
- * the new Node but read uninitialized (stale) values for the fields of the
- * new Node (including, ominously, the instance's <code>vptr</code>),
- * because writes can be seen in a different order by another thread. Even
- * on a uniprocessor, compiler optimizations can cause similar surprises.
- * <p>
- * The removal of a node is decoupled from the unlinking of that node from
- * the list. The <code>next</code> method unlinks some nodes that have been
- * removed; with reaping, the number of nodes which remain in a list for a
- * long time will be less than the number of threads in the VM.
- * <p>
- * No node can be a member of more than one list. Nodes which have been
- * added to a list can never be added to another list, even if they are
- * removed from the first list.
- * <p>
- * Never synchronize on an instance of this class - it could lead to
- * deadlock. (See the paragraph on locking order below for explanation.)
- * <p>
- * You can synchronize on an instance of a <code>Node</code> subclass
- * provided that the synchronizing thread does not already hold a lock on
- * another <code>Node</code> instance taken from the same
- * <code>FastList</code>. Note, many of the methods on <code>FastList</code>
- * synchronize on <code>Node</code>s in the
- * list, thus you should not call one of these methods if you
- * already hold a lock on a <code>Node</code> in the list. Similarly
- * for methods on <code>Node</code>.
- * <p>
- * The remainder of this comment discusses the internal structure
- * and assumptions of this class.
- * <p>
- * The design is to have a list of <code>FastList.Node</code> nodes,
- * each of which has a <code>next</code> reference, a <code>removed</code>
- * flag, and a <code>guardSet</code> (indicating which traversals
- * depend on a future synchronization on that node).
- * <p>
- * There is a special sublist which is important to assuring the integrity
- * of this data structure. The chain of nodes starting at <code>head</code>
- * and continuing to the <code>tail</code> via <code>Node.next</code>
- * references is called the <dfn>main sequence</dfn>. The fundamental
- * constraints on the main sequence are: <ul>
- * <li> The <code>tail</code> is always reachable from the <code>head</code>.
- * <li> Every <code>Node</code> for which <code>removed==false</code> is
- * an element of the main sequence.
- * <li> Every <code>Node</code> for which
- * <code>guardSet.isEmpty()==false</code> is an element of the main sequence
- * (regardless of <code>removed</code>).
- * <li> <code>tail.next==null</code> whenever <code>tail != null</code>.
- * <li> <code>tail==null</code> if and only if <code>head==null</code>.
- * </ul>
- * <p>
- * Note that removed non-guard nodes can still be in the main sequence:
- * they do not have to be unlinked immediately.
- * <p>
- * We say <q><var>Y</var> is <dfn>reachable</dfn> from <var>X</var></q>
- * when <var>X</var> equals <var>Y</var> or when <var>Y</var> is
- * reachable from <code><var>X</var>.next</code>.
- * <p>
- * New nodes are added at the tail, requiring synchronization on the list.
- * A node is said to be <dfn>removed<dfn> if its <code>removed</code>
- * field is <code>true</code>. Such a node may still exist and be
- * part of the main sequence. Removed nodes will eventually be unlinked
- * from their neighbors, if the <code>reap</code> method is called
- * occasionally.
- * <p>
- * Any element can become removed (by the <code>remove</code> method),
- * but once that happens, that element can never revert to being unremoved.
- * This means that the <code>removed</code> field can be read without
- * synchronization: a <code>true</code> value indicates that the node has
- * been removed; a <code>false</code> value is inconclusive.
- * This in turn means that a removed element cannot be added to a
- * <code>FastList</code>, because some other threads may read a stale cached
- * value for its <code>removed</code> field. (It may be possible, one day,
- * to liberate removed nodes from this restriction, given the guarantees of
- * guarded traversal.)
- * <p>
- * The list can be traversed without much synchronization.
- * When a traversal begins, a node near the end of the main sequence is
- * specially marked (<i>guarded</i>) in order that the traversal will
- * stop and synchronize when it reaches that node. When the guard node is
- * reached, and there are more nodes in the list to traverse, the
- * procedure is repeated: the (new) last node in the list
- * is marked, and traversal continues. This procedure ends when the
- * traversal reaches its guard node but finds out that it is still the
- * last node in the list. In this way, much of the list can be traversed
- * without synchronization.
- * <p>
- * It is possible for a traversal to find itself on an orphaned branch
- * (one from which the <code>tail</code> is not reachable). This can
- * happen when the <code>restart</code> method is called by a different
- * thread. Even a node on an orphaned branch is still useful for
- * traversal: every unremoved node which was inserted after the orphaned
- * node but before the traversal originally began is still reachable
- * from the orphaned node.
- * <p>
- * Because every traversal has a guard, a list with at least
- * one node can not become empty by traversal alone, even if the node
- * is removed. The <code>reap</code> method can remove such nodes.
- * <p>
- * Main-sequence nodes are stored in FIFO order.
- * <p>
- * Synchronized locks are acquired in accordance with the following
- * partial order, in order to avoid deadlocks.
- * <ul><li>Earlier nodes precede later nodes (i.e. where a thread holds
- * the lock on a node <var>X</var>, it must not wait for a lock on any
- * node <var>Y</var> unless <var>Y</var> is reachable from
- * <var>X</var>).</li>
- * <li>Every node precedes the list (i.e. where a thread holds the lock on
- * the <code>FastList</code> itself, it must not wait for a lock on any node
- * which has been added to that list).</li></ul>
- * <p>
- * Each node contain a field (<code>guardSet</code>) which
- * indicates how many different threads are using the node as a guard node.
- * If the field's value is <code>null</code>, the number is zero and the node
- * is not a guard node. If the field's value is nonnull, the value is a
- * <code>WeakHashMap</code> whose <code>keySet</code> is the set of threads
- * using the node as a guard node. If that <code>keySet</code> is empty,
- * the node is not a guard node.
- * <p>
- * There is a global table (actually a ThreadLocal) called
- * <code>DynamicGuard</code> which is used to
- * retrieve the guard node for the current thread. The number of entries
- * in a guard node's <code>guardSet</code> generally corresponds to the
- * number of times that node appears in the global table (the
- * <code>guardSet</code> size temporarily becomes greater
- * than the number of table entries, but it can never be less).
- * The list need not be synchronized while the global table is being accessed.
- * <p>
- * Unsynchronized access may be made to the <code>guardSet</code>,
- * <code>removed</code>, and <code>next</code> fields. In the case of
- * <code>next</code>, the field may be modified so as to unlink any removed
- * non-guard nodes. This action does not invalidate the main-sequence
- * invariant, and can only be done by a thread which is holding a lock on
- * the node being unlinked.
- * <p>
- * In the case of <code>guardSet</code> and <code>removed</code>, the fields
- * are read as an optimization. If the values read from the fields might
- * be stale, then synchronization is done and the old values are not
- * relied on. The value of <code>guardSet</code> is read without
- * synchronization to see if it's null or not, as part of a check to detect
- * the traversing thread's guard node. The unsynchronized value of
- * <code>removed</code> is untrusted when it's <code>false</code>; however,
- * a <code>true</code> value is trustworthy, since such a value could only
- * be read after the node is irrevocably marked removed.
- *
- * @author Sun Microsystems, Inc.
- *
+ * 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.
+ *
+ * @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> {
-class FastList {
-
- /**
- * A single node in a <code>FastList</code>.
- */
- static abstract class Node {
- /** The next youngest Node in the list.
- * If this node is the last in the list, this field is null.
- * Otherwise, it's a pointer to the next Node that was added
- * to the list (and not unlinked in the meantime).
- * <p>
- * This field may be changed only while synchronized on
- * <code>this</code>, or when unlinking a node from the middle
- * of the list. This field may be read without
- * synchronization if the reading thread has a guard node which
- * is not <code>this</code>.
- */
- private volatile Node next;
-
- /** True only if this node has been removed.
- * Every node starts out unremoved. Once this field becomes
- * true, it can never become false again. You must be
- * synchronized on this before you can modify this field.
- * You can read this field without synchronization if you don't
- * mind reading an old <code>false</code> instead of a more
- * recent <code>true</code>.
- */
- private boolean removed;
-
- /** The list containing this node.
- * Every node in a list has the same value for this field.
- * This field must not be changed after the node is added to
- * a list. The field can be read without synchronization
- * provided that the reading thread has first synchronized on
- * something since <code>this</code> node was added to its list
- * (that is, during a traversal).
- */
- private FastList list;
-
- /** Set of threads for which this is a guard.
- * This is a weak map from Thread to nulls, and the key set is
- * the important set of threads. The values are unimportant.
- * You must be synchronized on this node to access the map.
- * This field may be <code>null</code>, which is semantically
- * equivalent to the empty set.
- * <p>
- * This field is read without synchronization in <code>next</code>.
- * That method is searching for a particular node where the value
- * of this field is known to be continuously nonnull since the last
- * synchronization by the reading thread, so it is safe.
- * <p>
- * Note to maintainer: it may be better to use a reference count
- * and rely on the user to use a finally-clause to effect the
- * necessary decrement. In that case, head() should verify that
- * any previous traversal has been properly terminated.
- */
- private transient volatile WeakHashMap guardSet;
-
- /** Default constructor. This is called by subclasses. */
- protected Node() {
- this.removed = false;
- this.guardSet = null;
- this.list = null; // will be filled in by FastList.add()
- this.next = null;
- }
/**
- * Traverse to the next node. Note that between the time that the
- * next node is returned and the time you look at it someone may
- * have removed it. Returns <code>null</code> if there are no more
- * nodes.
- * <p>
- * Although this method attempts to skip removed nodes, callers
- * <em>must not</em> assume that removed nodes have been skipped.
- * Use the {@link #removed() removed} method to tell when a node
- * returned by this method is in fact removed, and
- * <code>synchronize</code> on the node if you want to prevent
- * anyone else from removing the node while you are in the
- * synchronized block.
- * <p>
- * Do not call this method twice on the same node unless each call is
- * part of a separate traversal; a traversal starts with a call to
- * <code>List.head</code>).
- * <p>
- * Note this method should not be called by threads that
- * hold locks on <code>Node</code>s that appear in the list
- * after this <code>Node</code>.
- */
- public Node next() {
-
- this.list.checkPanic(); // abort if malfunctioned
-
- // Ensure the list has a guard and it is for THIS list
- Node traversalGuard = (Node)FastList.DynamicGuard.get();
- if (traversalGuard == null)
- this.list.panic("Unguarded FastList traversal - 345");
- else if (traversalGuard.list != this.list)
- this.list.panic("Illegal traversal of 2 FastLists");
-
- /* When this thread last synchronized, Node.guardSet on
- * the thread's guard node was nonempty because the
- * traversing thread was added to guardSet by newGuardFor.
- * Since then, it cannot have been emptied, and therefore
- * cannot have been replaced with null. Therefore the
- * guard node must appear to have a nonnull Node.guardSet
- * field, even if accessed without locking. This means we
- * can safely conclude, without locking, that a Node whose
- * guardSet field is null is not the guard node for the
- * current thread.
- */
- if (this.guardSet != null) {
- /* This may or may not be the guard node; lock it
- * so we can be sure that reading `next' is safe:
+ * The type parameter for the FastList must extend this type, and
+ * all nodes added to the list are of that parameter type.
+ *
+ * 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.
*/
- synchronized (this) {
- if (this.guardSet != null && traversalGuard == this) {
- /* This is the guard node for the current
- * thread; drop it and return null.
- * (We don't need to find nodes added
- * after the traversal was started)
- */
- FastList.DynamicGuard.set(null);
- traversalGuard.unguard(Thread.currentThread());
- return null;
-
- /* If we did want nodes that were added
- * since the traversal started we
- * want to try and get a new guard node
- * with code like this :
- *
- * if (this.next != null) {
- * if (!this.list.newGuardFor(this)) {
- * // If it returned false, newGuardFor()
- * // has already cleaned up--we just return
- * return null; // traversal is over
- * } else {
- * // We can extend the traversal : proceed!
- * }
- * } else {
- * // We're at the end of the list. Clean up.
- * FastList.DynamicGuard.set(null);
- * traversalGuard.unguard(
- * Thread.currentThread());
- * return null;
- * }
- */
- }
- }
- }
-
- // At this point, there is a guard node reachable from this.next.
-
- /* This loop repeatedly looks at this.next to see if there's a
- * possibility of unlinking the next node. It stops at the
- * first sign of trouble (a guard node, an unremoved node, or
- * a concurrency conflict):
- */
- Node n = this.next;
- while (true) {
- if (n == null) {
- // We're on an orphaned branch. Remove our guard.
- traversalGuard = (Node)FastList.DynamicGuard.get();
- if (traversalGuard != null) {
- FastList.DynamicGuard.set(null);
- traversalGuard.unguard(Thread.currentThread());
- }
- return null;
- }
-
- // We can only unlink a removed node which is not a guard:
- if (n.guardSet != null || !n.removed)
- break;
-
- /* Lock n and see if we can find an excuse to unlink it.
- * While n is locked, no other thread can change this.next.
+ private volatile boolean removed;
+ /**
+ * This node does not need to be shown to scans
+ * with index greater than or equal to this index.
*/
- synchronized (n) {
- // Break if this.next changed.
- if (this.next != n)
- break;
- // Verify that n is not a guard:
- if (n.guardSet != null && !n.guardSet.isEmpty()) {
- break;
- }
- // reduce empty set to null
- n.guardSet = null;
- }
- /* n is removed and not a guard, so it's a candidate
- * for removal. If we got this far, then we have a
- * guard node. Therefore, n is not the last node in
- * the main sequence (although it may be the last node
- * on an orphaned branch).
+ private volatile long index;
+ @SuppressWarnings("unchecked")
+ 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.
*/
- this.next = n = n.next;
- }
-
- return n;
- }
-
- /**
- * Resume a traversal abandoned by another thread.
- * This is used by remote iterators. When a traversal was
- * started (and abandoned) by thread A, and a thread B wants
- * to continue the traversal from where A left off, then B
- * must call this method on the most recent <code>Node</code>
- * traversed by thread A. After this method returns normally,
- * B can call the <code>next</code> method on the same
- * <code>Node</code> to continue the traversal.
- * <p>
- * Note this method should not be called by threads that
- * hold locks on <code>Node</code>s that appear in the list
- * after this <code>Node</code>.
- */
- public synchronized void restart() {
+ private synchronized boolean remove() {
+ if (removed) {
+ return false;
+ }
+ removed = true;
+ return true;
+ }
- this.list.checkPanic(); // abort if malfunctioned.
+ @SuppressWarnings("unchecked")
+ synchronized void markOnList(FastList list) {
+ this.list = list;
+ }
- /* If the current thread still has a guard from an earlier
- * abandoned traversal, then clean up that guard.
- */
- Node oldguard = (Node)FastList.DynamicGuard.get();
- if (oldguard != null) {
- FastList.DynamicGuard.set(null);
- oldguard.unguard(Thread.currentThread());
- }
-
- /* There must be a synchronized block here before calling
- * newGuardFor, because newGuardFor reads FastList.tail
- * without synchronization. That's why this whole method
- * is synchronized.
- */
-
- /* Attempt to get a guard. If newGuardFor returns false, no
- * guard has been allocated, but that isn't a problem because
- * it also means that this node is on an orphaned branch where
- * a guard node is not necessary.
- */
- this.list.newGuardFor(null);
+ /**
+ * 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 <code>true</code> if the object has been removed
- * from the list. If called while synchronized on
- * <code>this</code>, this will return true if the object has
- * been removed and false otherwise.
- */
- public boolean removed() {
-
- this.list.checkPanic(); // abort if malfunctioned.
- return removed;
+ interface FastListIterator<T> extends Iterator<T> {
+ boolean lastRemoveSucceeded();
}
- /**
- * Remove the node from the list. This will be unsuccessful if the
- * node was removed by someone else after you got your hands on
- * it. This must be synchronized because the test to check if it
- * is already removed and the following decision to remove it if it
- * hasn't been removed must be unitary.
- */
- private boolean remove() {
- synchronized (this) {
- if (removed)
- return false; // beaten to it
+ private class FastListIteratorImpl implements Iterator<T> {
+ private T removable;
+ private T next;
+ private final long index;
+ private final Iterator<T> baseIterator;
- removed = true; // mark first, unlink later
- }
+ private FastListIteratorImpl(long index) {
+ this.index = index;
+ baseIterator = baseQueue.iterator();
+ next = getNext();
+ }
- this.list.reapable();
- return true;
- }
+ public boolean hasNext() {
+ return next != null;
+ }
- /** Remove a thread from guardSet. The indicated thread is
- * removed from the guardSet of the node, and the guardSet is
- * reduced to <code>null</code> if it's empty.
- * @param traverser the Thread to use as a key
- */
- private synchronized void unguard(Thread traverser) {
- if (this.guardSet == null)
- return;
-
- this.guardSet.remove(traverser);
- if (this.guardSet.isEmpty())
- this.guardSet = null;
- }
+ public T next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
- final Node dump(java.io.PrintWriter out) { //DEBUG
- if (this.removed) //DEBUG
- out.print('!'); //DEBUG
- out.print(toString()); //DEBUG
- Map g = this.guardSet; //DEBUG
- if (g != null) //DEBUG
- out.print("[g=" + g.size() + "]"); //DEBUG
- return this.next; //DEBUG
- } //DEBUG
- } // end class Node
-
- /** The guard node for the calling thread's traversal, if any.
- * The value is <tt>null</tt> for a thread which is not traversing
- * anything, and is a <code>Node</code> for other threads. No
- * thread can be involved in two concurrent traversals. This field
- * can be accessed without synchronization since it's thread-local.
- */
- private static final ThreadLocal DynamicGuard = new ThreadLocal();
-
- /** Flag to indicate that removed elements exist in the list and
- * that reaping is not necessarily a waste of time. This is set
- * in <code>remove</code> and cleared in <code>reap</code>.
- */
- private boolean reapable;
-
- /** The pointer to the last element in the list. */
- private Node tail; // synchronize on list to read or write
-
- /** The pointer to the first element in the list. */
- private Node head; // synchronize on list to read or write
-
- /** An Error that indicated a fundamental malfunction in the list. */
- private transient Error firstPanic = null;
-
- /**
- * Create an new empty list.
- */
- public FastList() {
- this.reapable = false;
- this.tail = null;
- this.head = null;
- this.firstPanic = null;
- }
-
- /**
- * Add a given node to the end of the list. Note, this method
- * generally attempts to lock <code>Node</code>s in the list and
- * should not be called from a thread that holds a lock on a node
- * already in the list - it is ok if the calling thread holds the
- * lock on <code>node</code>.
- */
- public void add(Node node) {
-
- this.checkPanic(); // abort if malfunctioned.
- if (node.removed) {
- throw new IllegalArgumentException(
- "FastList.add cannot accept a removed node");
- }
- if (node.list != null) {
- throw new IllegalArgumentException(
- "FastList.add cannot accept a node from another FastList");
- }
+ removable = next;
+ next = getNext();
+ return removable;
+ }
- node.list = this;
+ public void remove() {
+ if (removable != null) {
+ removable.remove();
+ removable = null;
+ } else {
+ throw new IllegalStateException();
+ }
+ }
- while (true) {
- Node t = this.tail;
- if (t == null) {
- // List appears to be empty - lock list and insert first node
- synchronized (this) {
- if (this.tail != null) {
- //System.err.print('$'); //DBG
- continue; // try again
- }
- this.tail = node;
- this.head = node;
- }
- } else {
- /* List is not empty - lock tail & list and insert the
- * node at the end.
+ /**
+ * Find the next eligible node, null if there is none.
+ * skip over removed nodes, and
+ * @return
*/
- synchronized (t) {
- if (t != this.tail) { // optimization
- //System.err.print('#'); //DBG
- continue; // try again
- }
- synchronized (this) {
- if (t != this.tail) {
- //System.err.print('&'); //DBG
- continue; // try again
+ private T getNext(){
+ T node = null;
+ while(baseIterator.hasNext()){
+ node = baseIterator.next();
+ if(node.removed()){
+ /* Tell the base list to drop it */
+ baseIterator.remove();
+ }
+ if(node.index >= index){
+ /* Seen all the relevant nodes. */
+ node = null;
+ break;
+ }
+ if(!node.removed()){
+ /* Got a keeper. */
+ break;
+ }
}
- t.next = node;
- this.tail = node;
- }
+ return node;
}
- }
- return;
}
- }
- /**
- * Allocate a new guard node for a traversing thread.
- * This method selects a guard node on the main sequence, as close as
- * practically possible to the tail. Returns true iff a guard was
- * allocated, and false if the list appeared to contain no elements
- * after the oldGuard. This routine must acquire a new guard at
- * the same time as or before releasing the old one, in order to
- * guarantee that the new guard will be reachable from the old.
- * <p>
- * Because this method reads <code>FastList.tail</code> without
- * synchronization, the guard could be stale. It's important that
- * it not be too stale, or else nodes added before the traversal
- * began might not appear in the traversal. For this reason, the
- * caller must have recently acquired a lock (i.e. synchronized on
- * any object). The guard allocated by this method will have been the
- * tail at least once since that lock was acquired.
- * <p>
- * Note: the oldGuard will always be dropped as the guard node for
- * this thread. Further, should this method return <code>false</code>
- * the DynamicGuard will be set to <code>null</code>.
- */
- private boolean newGuardFor(Node oldGuard) {
-
- /* tGood becomes true when it's determined that a given node
- * is good enough to be a guard node. "Good enough" means
- * that it's reachable from the head, and that it was the tail
- * at least once since this method was entered.
- */
- Thread current = Thread.currentThread();
+ private final AtomicLong index = new AtomicLong(Long.MIN_VALUE);
+ private final Queue<T> baseQueue = new ConcurrentLinkedQueue<T>();
- while (true) {
- boolean tGood = false; // is tGood a useable guard?
- boolean noMoreElements = false; // is oldGuard the tail node?
- Node t = this.tail;
-
- /* A new guard is not necessary for an empty list.
- * Further, an empty list has no guard nodes (or indeed
- * any nodes) so there is no need to call unguard() on
- * anything -- even the parameter "oldGuard".
- */
- if (t == null)
- return false;
-
- /* Optimistically presume that t will be good enough, and add
- * to its guardSet. If the optimism isn't justified, then the
- * addition will be undone later. If t is on the main sequence
- * and after oldGuard, then it's OK for use as a new guard.
- * This is because traversals must be guaranteed to hit the
- * guard node, and the easiest way to do that is to ensure
- * that the guard node is on the main sequence.
- */
- synchronized (t) {
- if ( (t.guardSet != null && !t.guardSet.isEmpty())
- || !t.removed())
- {
- if (t != oldGuard) // can't use same guard again
- tGood = true;
- }
- // Make sure t can't be unlinked after we release the lock.
- if (t.guardSet == null)
- t.guardSet = new WeakHashMap();
- t.guardSet.put(current, null);
- }
-
- /* If t isn't good enough, then we have to try the real tail. If
- * the tail isn't good enough, then we're at the end of the list,
- * and no guard is required.
- */
- if (!tGood) {
- synchronized (this) {
- if (this.tail == t) {
- if (t != oldGuard) { // t is reachable from oldGuard
- tGood = true;
- } else { // oldGuard == this.tail
- noMoreElements = true;
+ /**
+ * 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.list == null) {
+ node.list = this;
+ } else {
+ throw new IllegalArgumentException("Attempt to
reuse node "
+ + node);
}
- }
}
- }
-
- if (tGood) {
- DynamicGuard.set(t);
- if (oldGuard != null)
- oldGuard.unguard(current);
- return true;
- }
-
- //System.err.print('*'); //DBG
-
- // Undo the optimistic work if it turns out t isn't good enough.
- t.unguard(current);
-
- if (noMoreElements) {
- DynamicGuard.set(null);
- if (oldGuard != null && oldGuard != t)
- oldGuard.unguard(current);
- return false;
- }
+ node.index = index.getAndIncrement();
+ baseQueue.add(node);
}
- }
-
- /**
- * Return the start of the list. Returns null if the list is
- * empty. Note, this method generally attempts to lock
- * <code>Node</code>s in the list and should not be called from a
- * thread that holds a lock on a node already in the list.
- */
- public Node head() {
-
- this.checkPanic(); // Abort if malfunctioned.
- /* If the current thread still has a guard from an earlier abandoned
- * traversal, then clean up that guard.
- */
- Node oldguard = (Node)DynamicGuard.get();
- if (oldguard != null) {
- DynamicGuard.set(null);
- oldguard.unguard(Thread.currentThread());
- }
-
- Node h;
- Node t;
-
- synchronized (this) {
- h = this.head;
- t = this.tail;
- if (h == null)
- return null; // nothing in list
+
+ public boolean remove(T node){
+ if(node.list != this){
+ throw new IllegalArgumentException("Cannot remove a
node from a list it is not on");
+ }
+ return node.remove();
}
- // There must be a synchronized block here before calling
- // newGuardFor, because newGuardFor reads FastList.tail
- // without synchronization.
-
- // Every traversal needs a guard.
- if (!newGuardFor(null))
- return null; // nothing in list, suddenly
-
- // Make an attempt to unlink removed non-guard nodes from the head
- while (h.removed()) {
- synchronized (h) {
- /*
- * We stop if we find any node that is a guard node. Of
- * course, eventually we'll reach the node which is OUR
- * guard node and at that point we'll break from this loop.
- */
- if (h.guardSet != null && !h.guardSet.isEmpty())
- break; // can't unlink guard nodes
-
- synchronized (this) {
- if (h != this.head)
- return this.head; // someone else just did it
- this.head = h = h.next;
+ public void reap() {
+ Iterator<T> it = baseQueue.iterator();
+ while(it.hasNext()){
+ T node = it.next();
+ if(node.removed()){
+ it.remove();
+ }
}
- }
- }
-
- return h;
- }
-
- /**
- * Remove the given node from this list.
- */
- public boolean remove(Node node) {
-
- this.checkPanic(); // Abort if malfunctioned.
- return node.remove();
- }
-
- /** Remember that there's something for the reaper to do.
- */
- private void reapable() {
- this.reapable = true;
- }
-
- /**
- * Perform a normal traversal to help clear out some removed
- * nodes. It also moves the tail. Note, this method generally
- * attempts to lock <code>Node</code>s in the list and should not
- * be called from a thread that holds a lock on a node already in
- * the list.
- */
- public void reap() {
-
- if (!this.reapable)
- return;
-
- this.reapable = false;
- // reapable could be concurrently set to true, which is OK.
-
- reapCnt++;
-
- // Normal traversal (unlinks some nodes as a side effect).
- Node last = null;
- Node secondLast = null;
- for (Node n = this.head(); n != null; n = n.next()) {
- secondLast = last;
- last = n;
}
-
- // Clear out the last node only if it's removed and not a guard
- if (last == null || !last.removed || last.guardSet != null)
- return;
- if (secondLast == null) {
- // probably the only one in the list
- synchronized (last) {
- if (last.next != null)
- return; // changed while waiting
- if (last.guardSet != null && !last.guardSet.isEmpty())
- return; // last became a guard while we waited
- synchronized (this) {
- if (last != this.tail || last != this.head)
- return; // a node was added while we waited
- // remove the only node from the list
- this.head = this.tail = null;
- }
- }
- } else {
- /* Move the tail to secondLast. We can only do this if
- * secondLast is on the main sequence and last is both
- * removed and not a guard.
- */
- if (secondLast.removed && secondLast.guardSet == null)
- return; // not sure secondLast is on main sequence
- synchronized (secondLast) {
- if (secondLast.removed) {
- if (secondLast.guardSet == null)
- return; // not sure secondLast is on main sequence
- if (secondLast.guardSet.isEmpty()) {
- secondLast.guardSet = null;
- return; // ditto
- }
- }
- // We're sure now that secondLast is on the main sequence.
- synchronized (last) {
- if (secondLast.next != last)
- return; // last has already been unlinked
- if (last.next != null)
- return; // a node was added while we waited
- if (last.guardSet != null && !last.guardSet.isEmpty())
- return; // last is a guard
- // We tested last.removed and it must still be true now.
- synchronized (this) {
- if (last != this.tail)
- return; // shouldn't happen
- // Unlink last (secondLast is the new tail):
- secondLast.next = null;
- this.tail = secondLast;
- }
- }
- }
- }
- } // end reap
-
- int reapCnt = 0; //DEBUG
- public final int reapCnt() { return reapCnt; } //DEBUG
-
-
- public void dump(java.io.PrintWriter out) { //DEBUG
- Node n = this.head; //DEBUG
- while (n != null) { //DEBUG
- if (this.tail == n) //DEBUG
- out.print("[tail]"); //DEBUG
- n = n.dump(out); //DEBUG
- out.print(' '); //DEBUG
- } //DEBUG
- out.print("null"); //DEBUG
- } //DEBUG
-
- /** Shut down the list due to an error. The argument is used to
- * construct an Error which is thrown. The FastList then becomes
- * unusable because every public method calls checkPanic which
- * then throws another exception.
- *
- * @param condition identifying string which will help debugging
- */
- private void panic(String condition)
- throws Error
- {
- InternalError err = new InternalError(condition);
-
- // Record only the first panic so that subsequent ones don't confuse:
- if (firstPanic == null) {
- synchronized (this) {
- if (firstPanic == null)
- firstPanic = err;
- }
+ public Iterator<T> iterator(){
+ return new FastListIteratorImpl(index.get());
}
- throw err;
- }
-
- /** Abort if the list has been shut down. This does nothing in
- * normal operation. If the list has undergone a panic, then this
- * throws an exception which says so.
- */
- private void checkPanic()
- throws Error
- {
- if (firstPanic == null)
- return;
- throw new InternalError("FastList panicked; original error was:" +
- firstPanic);
- }
-
}
Modified:
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/WatchersForTemplateClass.java
URL:
http://svn.apache.org/viewvc/incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/WatchersForTemplateClass.java?rev=1063132&r1=1063131&r2=1063132&view=diff
==============================================================================
---
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/WatchersForTemplateClass.java
(original)
+++
incubator/river/jtsk/skunk/patsOutrigger/src/com/sun/jini/outrigger/WatchersForTemplateClass.java
Tue Jan 25 04:03:48 2011
@@ -28,7 +28,7 @@ import java.util.Set;
*/
class WatchersForTemplateClass {
/** All the templates we know about */
- private final FastList contents = new FastList();
+ private final FastList<TemplateHandle> contents = new
FastList<TemplateHandle>();
/** The object we are inside of */
private final TransitionWatchers owner;
@@ -65,8 +65,7 @@ class WatchersForTemplateClass {
* if we have more than one with the same template. It
* is bad if we add the watcher to a removed handle.
*/
- TemplateHandle handle = (TemplateHandle)contents.head();
- for (; handle != null; handle = (TemplateHandle)handle.next()) {
+ for(TemplateHandle handle : contents) {
if (template.equals(handle.rep())) {
synchronized (handle) {
if (!handle.removed()) {
@@ -90,7 +89,7 @@ class WatchersForTemplateClass {
* template, create one, add the watcher to it, and it
* to contents.
*/
- handle = new TemplateHandle(template, this);
+ TemplateHandle handle = new TemplateHandle(template, this);
/* We need the sync both to prevent concurrent modification
* of handle (since we add it to contents first), and to
@@ -134,9 +133,7 @@ class WatchersForTemplateClass {
* the changed entry and if they do ask them to
* put the appropriate watchers in the set.
*/
- for (TemplateHandle handle = (TemplateHandle)contents.head();
- handle != null;
- handle = (TemplateHandle)handle.next())
+ for (TemplateHandle handle : contents)
{
// See the if handle mask is incompatible
EntryHandleTmplDesc desc = handle.descFor(repNumFields);
@@ -171,9 +168,7 @@ class WatchersForTemplateClass {
*/
void reap(long now) {
// First remove empty handles
- for (TemplateHandle handle = (TemplateHandle)contents.head();
- handle != null;
- handle = (TemplateHandle)handle.next())
+ for (TemplateHandle handle : contents)
{
// Dump any expired watchers.
handle.reap(now);
