//============================================================================== // FifoQueue.java //============================================================================== package tribble.util; // System imports import java.lang.IllegalArgumentException; import java.lang.NullPointerException; import java.lang.String; import java.lang.Throwable; /******************************************************************************* * Generic FIFO queue. * Implements a first-in first-out (FIFO) circular queue, with get and * put methods. * *
* Puts (writes) and gets (reads) to the queue are synchronized, so that a * producer thread can add items to the queue while another thread is * simultaneously retrieving items from the queue, without contention. * However, this implementation reduces the number of synchronization calls * required, making it more efficient than a fully synchronized queue class. * *
* Note that this class is designed to support a single writer thread that calls * the {@link #put put()} method, and a single reader thread that calls the * {@link #get get()} method. Multiple unsynchronized writers and multiple * readers are not supported by this class. * * * @version $Revision: 1.1 $ $Date: 2007/06/21 21:27:28 $ * @since 2007-06-21 * @author David R. Tribble (david@tribble.com). *
* Copyright ©2007 by David R. Tribble, all rights reserved.
* Permission is granted to any person or entity except those designated by
* by the United States Department of State as a terrorist, or terrorist
* government or agency, to use and distribute this source code provided
* that the original copyright notice remains present and unaltered.
*/
public class FifoQueue
{
// Identification
/** Revision information. */
static final String REV =
"@(#)tribble/util/FifoQueue.java $Revision: 1.1 $ $Date: 2007/06/21 21:27:28 $\n";
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Variables
/** Next put (write) item index. */
volatile int m_putI;
/** Next get (read) item index. */
volatile int m_getI;
/** Item queue. */
Object[] m_list;
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Constructors
/***************************************************************************
* Default constructor.
* Creates a FIFO queue of the default size (10 items).
*
* @since 1.1, 2007-06-21
*/
public FifoQueue()
{
// Initialize
this(10);
}
/***************************************************************************
* Constructor.
* Creates a FIFO queue containing a specified number of items.
*
* @param size
* Maximum number of items that the queue can hold at one time.
*
* @throws IllegalArgumentException (unchecked)
* Thrown if size is less than 1.
*
* @since 1.1, 2007-06-21
*/
public FifoQueue(int size)
{
// Sanity checks
if (size < 1 || size > 0x7FFFFFFF-1)
throw new IllegalArgumentException("Invalid queue size: " + size);
// Initialize
m_list = new Object[size+1];
m_putI = 0;
m_getI = 0;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Methods
/***************************************************************************
* Insert an item into the queue.
* Note that the first item written to the queue will be the first item to be
* read from the queue.
*
*
* Note that this method is not synchronized, and does not need to be as long * as there is only one producer thread calling this method at any given * moment. * * @param item * Object to add to the tail of the queue. This cannot be null. * * @return * True if the item was inserted into the queue, otherwise false because the * queue is full. * * @throws NullPointerException (unchecked) * Thrown if item is null. * * @since 1.1, 2007-06-21 */ public boolean put(Object item) { int putI; int getI; // Check for a null item if (item == null) throw new NullPointerException("Null item"); // Check that the queue is not full putI = m_putI; // Not synchronized getI = m_getI; if (putI-getI == m_list.length-1 || putI-getI == -1) return (false); // Insert the next item into the queue m_list[putI++] = item; if (putI >= m_list.length) putI = 0; m_putI = putI; // Not synchronized return (true); } /*************************************************************************** * Remove an item from the queue. * Note that the first item read from the queue is the first item that was * written to the queue. * *
* Note that this method is not synchronized, and does not need to be as long * as there is only one consumer thread calling this method at any given * moment. * * @return * Next object in the queue, or null if the queue is empty. * * @since 1.1, 2007-06-21 */ public Object get() { Object item; int getI; // Check if the queue is empty getI = m_getI; if (getI == m_putI) // Not synchronized return (null); // Read and remove the next item from the queue item = m_list[getI]; m_list[getI++] = null; if (getI >= m_list.length) getI = 0; m_getI = getI; // Not synchronized return (item); } /*************************************************************************** * Determine the number of items in this queue. * * @return * The current number of items in the queue. * * @since 1.1, 2007-06-21 */ public int size() { int putI; int getI; // Check that the queue is not full putI = m_putI; // Not synchronized getI = m_getI; if (putI >= getI) return (putI-getI); else return (putI-getI + m_list.length); } /*************************************************************************** * Finalization. * * @since 1.1, 2007-06-21 */ protected synchronized void finalize() throws java.lang.Throwable { // Empty the queue for (int i = m_list.length-1; i >= 0; i--) m_list[i] = null; // Cascade super.finalize(); } } // End FifoQueue.java