/*
 * @(#)SynchQueue.java      0.9.0 04/26/2000 - 13:39:11
 *
 * Copyright (C) 2000,,2003 2002 Matt Albrecht
 * groboclown@users.sourceforge.net
 * http://groboutils.sourceforge.net
 *
 *  Permission is hereby granted, free of charge, to any person obtaining a
 *  copy of this software and associated documentation files (the "Software"),
 *  to deal in the Software without restriction, including without limitation
 *  the rights to use, copy, modify, merge, publish, distribute, sublicense,
 *  and/or sell copies of the Software, and to permit persons to whom the 
 *  Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in 
 *  all copies or substantial portions of the Software. 
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL 
 *  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 *  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 *  DEALINGS IN THE SOFTWARE.
 */

package net.sourceforge.groboutils.util.datastruct.v1;


/**
 * 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.
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * 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.
 * <P>
 * <H3>Changes made for 0.9.1:</H3>
 * <UL>
 *      <LI>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.
 *      <LI>Because of the ordering of the <tt>size</tt> assignment, and
 *          that the {@link #size()} method is unsynchronized, a situation
 *          could occur where {@link #size()} can return an invalid number
 *          (see <a href="http://sourceforge.net/tracker/index.php?func=detail&aid=459457&group_id=22594&atid=375589">
 *          bug #459457 </a>), such as -9.
 *          <P>
 *          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.
 *          <P>
 *          The fix involves adding another lock in the {@link
 *          #enqueue( Object )}
 *          method around the new element (which will become the next tail
 *          element), and making the {@link SynchQueue.ListElement.next}
 *          and <tt>size</tt> values volatile (this will force their setting
 *          to be in the same order specified in the code).
 *      <LI>Removed the double-check locking optimization due to possible
 *          failures occuring with it.
 * </UL>
 *
 * @author   Matt Albrecht <a href="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
 * @since    April 26, 2000 (0.9.0 Alpha)
 * @version  $Date: 2003/02/10 22:52:44 $
 */
public class SynchQueue
{
    /**
     * Inner class to maintain the list's objects, and a next pointer.
     */
    private static class ListElement 
    {
        public Object value;
        public volatile ListElement next;
        public ListElement() {}
        public ListElement( Object o )
        {
            this.value = o;
        }
    }

    /**
     * List pointers; head points to the removal point, and tail points
     * to the addition point.
     */
    private ListElement head, tail;
    
    /**
     * Internal size of the queue.
     */
    private volatile int size = 0;

    
    
    /**
     * Create a new Synchronized Queue with an empty list.
     */
    public SynchQueue()
    {
        this.head = new ListElement();
        this.tail = new ListElement();
        this.tail.next = new ListElement();
    }

    
    /**
     * 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.
     *
     * @param o the object to place at the end of the list.
     */
    public void enqueue( Object o )
    {
        ListElement le = new ListElement( o );
        synchronized( le )
        {

            // note: double-checked locking does not work. See
            // http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
            // HOWEVER:
            //   we are doing an object pointer assignment, not a new Object()
            //   operation.
            //   "It will work for 32-bit primitive values
            //   "Although the double-checked locking idiom cannot be used
            //   for references to objects, it can work for 32-bit primitive
            //   values (e.g., int's or float's). Note that it does not work
            //   for long's or double's, since unsynchronized reads/writes of
            //   64-bit primitives are not guaranteed to be atomic."
            //
            // So... will it work?  Probably not, due to additional logic
            // besides just the assignment.

            synchronized( this.head )
            {
                if (this.head.next == null)
                {
                    this.head.next = le;
                    this.head.notify();
                }
            }
            
            synchronized( this.tail.next )
            {
                this.size++;
                this.tail.next.next = le;
                this.tail.next = le;
            }
        }
    }
    

    /**
     * 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.
     *
     * @see java.lang.Thread#interrupt()
     * @see #enqueue( Object )
     * @see #dequeue( long, int )
     * @see #dequeue( long )
     * @return the first element on the list, or <tt>null</tt> if a time-out
     *      occured.
     * @exception InterruptedException thrown if the thread, while waiting,
     *      is interrupted.
     */
    public Object dequeue()
            throws InterruptedException
    {
        return dequeue( 0, 0 );
    }
    

    /**
     * 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.
     * <P>
     * The wait can be given a maximum time by specifying the <tt>timeout</tt>
     * as a non-zero value.  This means that if the given
     * time expires, and nothing is in the queue, then <tt>null</tt> is
     * returned.  This allows for polling-like features for the queue.
     * If <tt>timeout</tt> is zero, then real time is not taken into
     * consideration and the thread simply waits until the object is added to
     * the queue. If <tt>timeout</tt> is less than zero, then no waiting
     * is performed if the queue is empty, and <tt>null</tt> is returned
     * immediately.
     *
     * @param timeout the maximum time to wait in milliseconds.
     * @see java.lang.Thread#interrupt()
     * @see #enqueue( Object )
     * @see #dequeue( long, int )
     * @see #dequeue()
     * @return the first element on the list, or <tt>null</tt> if a time-out
     *      occured.
     * @exception InterruptedException thrown if the thread, while waiting,
     *      is interrupted.
     */
    public Object dequeue( long timeout )
            throws InterruptedException
    {
        return dequeue( timeout, 0 );
    }
    

    /**
     * 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.
     * <P>
     * The wait can be given a maximum time by specifying the <tt>timeout</tt>
     * or <tt>nanos</tt> as non-zero values.  This means that if the given
     * time expires, and nothing is in the queue, then <tt>null</tt> is
     * returned.  This allows for polling-like features for the queue.
     * The total wait time in milliseconds <tt> = 1000000*timeout + nanos</tt>.
     * 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 <tt>timeout</tt> is less than zero, then no waiting
     * is performed if the queue is empty, and <tt>null</tt> is returned
     * immediately.
     *
     * @param timeout the maximum time to wait in milliseconds.
     * @param nanos additional time, in nanoseconds range 0-999999.
     * @see java.lang.Thread#interrupt()
     * @see #enqueue( Object )
     * @see #dequeue()
     * @see #dequeue( long )
     * @return the first element on the list, or <tt>null</tt> if a time-out
     *      occured.
     * @exception InterruptedException thrown if the thread, while waiting,
     *      is interrupted.
     */
    public Object dequeue( long timeout, int nanos )
            throws InterruptedException
    {
        Object o;
        float dTimeout = (float)(timeout + nanos);
        

        synchronized( this.head )
        {
            // this used to be a while (head.next == null) loop,
            // but now it's ugly to reduce the number of "if" checks.
            if (this.head.next == null)
            {
                // quick check, but needs synchronization
                if (timeout < 0)
                {
                    return null;
                }
                while (true)
                {
                    this.head.wait( timeout, nanos );
                    
                    // check if the element was indeed added...
                    if (this.head.next != null)
                    {
                        // yep! Early out!
                        break;
                    }
                    
                    // Check if we timed-out, or if it was a flakey
                    // notify
                    //   - include an epsilon for the floating check...
                    if (dTimeout > 0.9f)
                    {
                        // time-out and a null, so crap out without doing
                        // anything.
                        return null;
                    }
                }
            } // end null checking block
            
            // guaranteed to not have a null at this point
            o = this.head.next.value;
            
            // remove the minor memory leak
            this.head.next.value = null;

            synchronized( this.head.next )
            {
                this.head.next = this.head.next.next;
                this.size--;
            }
        }
        return o;
    }
    
    
    /**
     * 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.
     *
     * @return if the list is empty, then <code>null</code> is returned,
     *    otherwise the contents of the top level element in the list is
     *    returned without removing it from the list.
     */
    public Object peek()
    {
        Object o = null;

        synchronized( this.head )
        {
            if (this.head.next != null)
            {
                o = this.head.next.value;
            }
            // else o = null;
        }
        return o;
    }
    
    
    /**
     * Checks if the list is empty, by a simple, non-blocking check on
     * the head element.
     *
     * @return <code>true</code> if the list contains no user elements,
     *    otherwise <code>false</code> if at least one user element is present
     *    on the list.
     */
    public boolean isEmpty()
    {
        return (this.head.next == null);
    }
    
    
    /**
     * @return the current size of the list.  Since this method is
     *     completely unsynchronized, the returned value may be off by 1,
     *     due to threading issues.
     */
    public int size()
    {
        return this.size;
    }
    
    
    /**
     * Removes all the current data in the queue.
     */
    public void removeAll()
    {
        synchronized( this.head )
        {
            synchronized( this.tail.next )
            {
                this.head.next = null;
                
                // remove the minor memory leak
                this.tail.next.value = null;
                
                this.size = 0;
            }
        }
    }

}