net.sourceforge.groboutils.util.datastruct.v1
Class SynchQueue

java.lang.Object
  net.sourceforge.groboutils.util.datastruct.v1.SynchQueue

public class SynchQueue

extends java.lang.Object

A Queue optimized for synchronized access. If a request is made to dequeue() an item on an empty list, then the requesting thread waits until an object is placed on the queue.

Care has been taken to ensure proper synchronization. Synchronization has been optimized so that adding an element to the list does not stop access to removing an item off the list. The only conflicts occur when the list has 1 or less items. All synchronization is performed on internal objects, so the queue itself is still available for outside classes to use as a synchronization key.

An additional optimization can be made by pooling the ListElement objects, although it leads to another syncrhonization collision. An alternative would be to make a ListElement specific synch-queue which only stores ListElement objects, and doesn't care about the stored values. To prevent it from having a major memory footprint, it could set a cap on the number of elements it stores.

A small memory leak is present, for performance purposes. If the list is "emptied", then there still remains a reference to a list element on the tail. I have optimized this by nulling out the referenced value, but the ListElement remains. Hopefully, a single ListElement won't be much of a memory burden.

Changes made for 0.9.1:

• The inner ListElement class has been changed to be a private static class. This reduces a bit of a memory overhead caused by the original implementation of having the class be non-static.
• Because of the ordering of the size assignment, and that the size() method is unsynchronized, a situation could occur where size() can return an invalid number (see bug #459457 ), such as -9.

  A quick analysis this may happen during the enqueue method when an optimizer sets the tail to the new value before it sets the size.

  The fix involves adding another lock in the enqueue( Object ) method around the new element (which will become the next tail element), and making the SynchQueue.ListElement.next and size values volatile (this will force their setting to be in the same order specified in the code).

• Removed the double-check locking optimization due to possible failures occuring with it.

Since:

April 26, 2000 (0.9.0 Alpha)

Version:

$Date: 2003/02/10 22:52:44 $

Author:

Matt Albrecht groboclown@users.sourceforge.net

Constructor Summary

SynchQueue()
Create a new Synchronized Queue with an empty list.

Method Summary

java.lang.Object	dequeue() Removes and returns the first element in the list.
java.lang.Object	dequeue(long timeout) Removes and returns the first element in the list.
java.lang.Object	dequeue(long timeout, int nanos) Removes and returns the first element in the list.
void	enqueue(java.lang.Object o) Adds an element to the end of the queue.
boolean	isEmpty() Checks if the list is empty, by a simple, non-blocking check on the head element.
java.lang.Object	peek() Retrieves the top-level object from the list without removing it.
void	removeAll() Removes all the current data in the queue.
int	size()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SynchQueue

public SynchQueue()

Create a new Synchronized Queue with an empty list.

Method Detail

enqueue

public void enqueue(java.lang.Object o)

Adds an element to the end of the queue. If the list is empty, then the next waiting thread is woken up. If the list has one or fewer elements, this this method will block any access to the queue, otherwise this only blocks access to adding to the list.

Parameters:

o - the object to place at the end of the list.

dequeue

public java.lang.Object dequeue()
                         throws java.lang.InterruptedException

Removes and returns the first element in the list. If the list is empty, then the thread waits until a new element is placed onto the list. In general, this method will not be blocked by the enqueue() method.

Returns:

the first element on the list, or null if a time-out occured.

Throws:

java.lang.InterruptedException - thrown if the thread, while waiting, is interrupted.

See Also:

Thread.interrupt(), enqueue( Object ), dequeue( long, int ), dequeue( long )

dequeue

public java.lang.Object dequeue(long timeout)
                         throws java.lang.InterruptedException

Removes and returns the first element in the list. If the list is empty, then the thread waits until a new element is placed onto the list. In general, this method will not be blocked by the enqueue() method.

The wait can be given a maximum time by specifying the timeout as a non-zero value. This means that if the given time expires, and nothing is in the queue, then null is returned. This allows for polling-like features for the queue. If timeout is zero, then real time is not taken into consideration and the thread simply waits until the object is added to the queue. If timeout is less than zero, then no waiting is performed if the queue is empty, and null is returned immediately.

Parameters:

timeout - the maximum time to wait in milliseconds.

Returns:

the first element on the list, or null if a time-out occured.

Throws:

java.lang.InterruptedException - thrown if the thread, while waiting, is interrupted.

See Also:

Thread.interrupt(), enqueue( Object ), dequeue( long, int ), dequeue()

dequeue

public java.lang.Object dequeue(long timeout,
                                int nanos)
                         throws java.lang.InterruptedException

Removes and returns the first element in the list. If the list is empty, then the thread waits until a new element is placed onto the list. In general, this method will not be blocked by the enqueue() method.

The wait can be given a maximum time by specifying the timeout or nanos as non-zero values. This means that if the given time expires, and nothing is in the queue, then null is returned. This allows for polling-like features for the queue. The total wait time in milliseconds = 1000000*timeout + nanos. If the total wait is zero, then real time is not taken into consideration and the thread simply waits until the object is added to the queue. If timeout is less than zero, then no waiting is performed if the queue is empty, and null is returned immediately.

Parameters:

timeout - the maximum time to wait in milliseconds.

nanos - additional time, in nanoseconds range 0-999999.

Returns:

the first element on the list, or null if a time-out occured.

Throws:

java.lang.InterruptedException - thrown if the thread, while waiting, is interrupted.

See Also:

Thread.interrupt(), enqueue( Object ), dequeue(), dequeue( long )

peek

public java.lang.Object peek()

Retrieves the top-level object from the list without removing it. It momentarily blocks the retrieval from the list, but does not wait if the list is empty. Currently, there is no way to test if a null was placed in the list, or if the list is empty.

Returns:

if the list is empty, then null is returned, otherwise the contents of the top level element in the list is returned without removing it from the list.

isEmpty

public boolean isEmpty()

Checks if the list is empty, by a simple, non-blocking check on the head element.

Returns:

true if the list contains no user elements, otherwise false if at least one user element is present on the list.

size

public int size()

Returns:

the current size of the list. Since this method is completely unsynchronized, the returned value may be off by 1, due to threading issues.

removeAll

public void removeAll()

Removes all the current data in the queue.