multi-tailed queue

[Joe Seigh]

This is a FIFO queue with some differences. One is, there is no
dequeue method as such. Dequeueing elements from the queue is
done with an enumerator. Multiple enumerators are allowed but
each enumerator acts as if it was the only one. In other words,
an enumerator acts as if it has it own private copy of the queue
unaffected by the actions of other enumerators. An enumerator
only returns elements put onto the queue after the enumerator was
created. In order to get all elements that are placed on the
queue, the enumerators have to be created at the same time the
queue is created before any elements have been placed on the
queue. The enumeration never ends. It will block if no
queue elements are available.

The enumerator traverses the queue without synchronized access.
There is an internal pointer delimiting what part of the queue
has been synchronized into a consistent state, i.e. safe and
valid, for traversal. An alternate version of this class is
also posted for comparison purposes. It uses a test for null
to indicate the apparent head of the queue with the necessary
synchronization to ensure valid memory states.

------------------------
import java.util.*;

public class Mqueue {
QNode anchor = new QNode();

class QNode {
QNode next = null;
Object item = null;
}

public synchronized void enqueue(Object item) {
anchor.next = new QNode();
anchor = anchor.next;
anchor.item = item;
this.notifyAll();
}

public synchronized Enumeration elements() {
class QTail implements Enumeration {
QNode current = anchor;
QNode last = anchor;
public boolean hasMoreElements() {
return true;
}

public Object nextElement() {
if (current == last) {
synchronized(Mqueue.this) {
while(last == anchor) {
try {Mqueue.this.wait(); }
catch (InterruptedException e) {}
}
last = anchor;
}
}
current = current.next;
return current.item;
}
}
return new QTail();
}
}

------------------------
import java.util.*;

public class Mqueue2 {
QNode anchor;

class QNode {
QNode next = null;
Object item = null;
}

public Mqueue2() {
anchor = new QNode();
}
public synchronized void enqueue(Object item) {
QNode z = new QNode();
synchronized (this) {
z.item = item;
} // memory store barrier
anchor.next = z;
anchor = z;
this.notifyAll();
}

public synchronized Enumeration elements() {
class QTail implements Enumeration {
QNode current = anchor;
public boolean hasMoreElements() {
return true;
}

public Object nextElement() {
if (current.next == null) {
synchronized(Mqueue2.this) {
while(current.next == null) {
try {Mqueue2.this.wait(); }
catch (InterruptedException e) {}
}
}
}
current = current.next;
synchronized(this) { // memory fetch barrier
return current.item;
}
}
}
return new QTail();
}
}

Joe Seigh