SynchQueue


1   /*
2    * @(#)SynchQueue.java      0.9.0 04/26/2000 - 13:39:11
3    *
4    * Copyright (C) 2000,,2003 2002 Matt Albrecht
5    * groboclown@users.sourceforge.net
6    * http://groboutils.sourceforge.net
7    *
8    *  Permission is hereby granted, free of charge, to any person obtaining a
9    *  copy of this software and associated documentation files (the "Software"),
10   *  to deal in the Software without restriction, including without limitation
11   *  the rights to use, copy, modify, merge, publish, distribute, sublicense,
12   *  and/or sell copies of the Software, and to permit persons to whom the 
13   *  Software is furnished to do so, subject to the following conditions:
14   *
15   *  The above copyright notice and this permission notice shall be included in 
16   *  all copies or substantial portions of the Software. 
17   *
18   *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
19   *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
20   *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL 
21   *  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
22   *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
23   *  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
24   *  DEALINGS IN THE SOFTWARE.
25   */
26  
27  package net.sourceforge.groboutils.util.datastruct.v1;
28  
29  
30  /**
31   * A Queue optimized for synchronized access.  If a request is made to dequeue()
32   * an item on an empty list, then the requesting thread waits until
33   * an object is placed on the queue.
34   * <P>
35   * Care has been taken to ensure proper synchronization.  Synchronization
36   * has been optimized so that adding an element to the list does not stop
37   * access to removing an item off the list.  The only conflicts occur when
38   * the list has 1 or less items.  All synchronization is performed on
39   * internal objects, so the queue itself is still available for outside
40   * classes to use as a synchronization key.
41   * <P>
42   * An additional optimization can be made by pooling the ListElement objects,
43   * although it leads to another syncrhonization collision.  An alternative
44   * would be to make a ListElement specific synch-queue which only stores
45   * ListElement objects, and doesn't care about the stored values.  To prevent
46   * it from having a major memory footprint, it could set a cap on the number
47   * of elements it stores.
48   * <P>
49   * A small memory leak is present, for performance purposes.  If the
50   * list is "emptied", then there still remains a reference to a list element
51   * on the tail.  I have optimized this by nulling out the referenced value,
52   * but the ListElement remains.  Hopefully, a single ListElement won't be
53   * much of a memory burden.
54   * <P>
55   * <H3>Changes made for 0.9.1:</H3>
56   * <UL>
57   *      <LI>The inner ListElement class has been changed to be a private
58   *          static class. This reduces a bit of a memory overhead caused by the
59   *          original implementation of having the class be non-static.
60   *      <LI>Because of the ordering of the <tt>size</tt> assignment, and
61   *          that the {@link #size()} method is unsynchronized, a situation
62   *          could occur where {@link #size()} can return an invalid number
63   *          (see <a HREF="http://sourceforge.net/tracker/index.php?func=detail&aid=459457&group_id=22594&atid=375589">
64   *          bug #459457 </a>), such as -9.
65   *          <P>
66   *          A quick analysis this may happen during the enqueue method
67   *          when an optimizer sets the tail to the new  value before it
68   *          sets the size.
69   *          <P>
70   *          The fix involves adding another lock in the {@link
71   *          #enqueue( Object )}
72   *          method around the new element (which will become the next tail
73   *          element), and making the {@link SynchQueue.ListElement.next}
74   *          and <tt>size</tt> values volatile (this will force their setting
75   *          to be in the same order specified in the code).
76   *      <LI>Removed the double-check locking optimization due to possible
77   *          failures occuring with it.
78   * </UL>
79   *
80   * @author   Matt Albrecht <a HREF="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
81   * @since    April 26, 2000 (0.9.0 Alpha)
82   * @version  $Date: 2003/02/10 22:52:44 $
83   */
84  public class SynchQueue
85  {
86      /**
87       * Inner class to maintain the list's objects, and a next pointer.
88       */
89      private static class ListElement 
90      {
91          public Object   value;
92          public volatile ListElement next;
93          public ListElement() {}
94          public ListElement( Object   o )
95          {
96              this.value = o;
97          }
98      }
99  
100     /**
101      * List pointers; head points to the removal point, and tail points
102      * to the addition point.
103      */
104     private ListElement head, tail;
105     
106     /**
107      * Internal size of the queue.
108      */
109     private volatile int size = 0;
110 
111     
112     
113     /**
114      * Create a new Synchronized Queue with an empty list.
115      */
116     public SynchQueue()
117     {
118         this.head = new ListElement();
119         this.tail = new ListElement();
120         this.tail.next = new ListElement();
121     }
122 
123     
124     /**
125      * Adds an element to the end of the queue.  If the list is empty,
126      * then the next waiting thread is woken up.  If the list has one or
127      * fewer elements, this this method will block any access to the queue,
128      * otherwise this only blocks access to adding to the list.
129      *
130      * @param o the object to place at the end of the list.
131      */
132     public void enqueue( Object   o )
133     {
134         ListElement le = new ListElement( o );
135         synchronized( le )
136         {
137 
138             // note: double-checked locking does not work. See
139             // http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
140             // HOWEVER:
141             //   we are doing an object pointer assignment, not a new Object()
142             //   operation.
143             //   "It will work for 32-bit primitive values
144             //   "Although the double-checked locking idiom cannot be used
145             //   for references to objects, it can work for 32-bit primitive
146             //   values (e.g., int's or float's). Note that it does not work
147             //   for long's or double's, since unsynchronized reads/writes of
148             //   64-bit primitives are not guaranteed to be atomic."
149             //
150             // So... will it work?  Probably not, due to additional logic
151             // besides just the assignment.
152 
153             synchronized( this.head )
154             {
155                 if (this.head.next == null)
156                 {
157                     this.head.next = le;
158                     this.head.notify();
159                 }
160             }
161             
162             synchronized( this.tail.next )
163             {
164                 this.size++;
165                 this.tail.next.next = le;
166                 this.tail.next = le;
167             }
168         }
169     }
170     
171 
172     /**
173      * Removes and returns the first element in the list.  If the list is
174      * empty, then the thread waits until a new element is placed onto the list.
175      * In general, this method will not be blocked by the enqueue() method.
176      *
177      * @see java.lang.Thread#interrupt()
178      * @see #enqueue( Object )
179      * @see #dequeue( long, int )
180      * @see #dequeue( long )
181      * @return the first element on the list, or <tt>null</tt> if a time-out
182      *      occured.
183      * @exception InterruptedException thrown if the thread, while waiting,
184      *      is interrupted.
185      */
186     public Object   dequeue()
187             throws InterruptedException  
188     {
189         return dequeue( 0, 0 );
190     }
191     
192 
193     /**
194      * Removes and returns the first element in the list.  If the list is
195      * empty, then the thread waits until a new element is placed onto the list.
196      * In general, this method will not be blocked by the enqueue() method.
197      * <P>
198      * The wait can be given a maximum time by specifying the <tt>timeout</tt>
199      * as a non-zero value.  This means that if the given
200      * time expires, and nothing is in the queue, then <tt>null</tt> is
201      * returned.  This allows for polling-like features for the queue.
202      * If <tt>timeout</tt> is zero, then real time is not taken into
203      * consideration and the thread simply waits until the object is added to
204      * the queue. If <tt>timeout</tt> is less than zero, then no waiting
205      * is performed if the queue is empty, and <tt>null</tt> is returned
206      * immediately.
207      *
208      * @param timeout the maximum time to wait in milliseconds.
209      * @see java.lang.Thread#interrupt()
210      * @see #enqueue( Object )
211      * @see #dequeue( long, int )
212      * @see #dequeue()
213      * @return the first element on the list, or <tt>null</tt> if a time-out
214      *      occured.
215      * @exception InterruptedException thrown if the thread, while waiting,
216      *      is interrupted.
217      */
218     public Object   dequeue( long timeout )
219             throws InterruptedException  
220     {
221         return dequeue( timeout, 0 );
222     }
223     
224 
225     /**
226      * Removes and returns the first element in the list.  If the list is
227      * empty, then the thread waits until a new element is placed onto the list.
228      * In general, this method will not be blocked by the enqueue() method.
229      * <P>
230      * The wait can be given a maximum time by specifying the <tt>timeout</tt>
231      * or <tt>nanos</tt> as non-zero values.  This means that if the given
232      * time expires, and nothing is in the queue, then <tt>null</tt> is
233      * returned.  This allows for polling-like features for the queue.
234      * The total wait time in milliseconds <tt> = 1000000*timeout + nanos</tt>.
235      * If the total wait is zero, then real time is not taken into
236      * consideration and the thread simply waits until the object is added to
237      * the queue. If <tt>timeout</tt> is less than zero, then no waiting
238      * is performed if the queue is empty, and <tt>null</tt> is returned
239      * immediately.
240      *
241      * @param timeout the maximum time to wait in milliseconds.
242      * @param nanos additional time, in nanoseconds range 0-999999.
243      * @see java.lang.Thread#interrupt()
244      * @see #enqueue( Object )
245      * @see #dequeue()
246      * @see #dequeue( long )
247      * @return the first element on the list, or <tt>null</tt> if a time-out
248      *      occured.
249      * @exception InterruptedException thrown if the thread, while waiting,
250      *      is interrupted.
251      */
252     public Object   dequeue( long timeout, int nanos )
253             throws InterruptedException  
254     {
255         Object   o;
256         float dTimeout = (float)(timeout + nanos);
257         
258 
259         synchronized( this.head )
260         {
261             // this used to be a while (head.next == null) loop,
262             // but now it's ugly to reduce the number of "if" checks.
263             if (this.head.next == null)
264             {
265                 // quick check, but needs synchronization
266                 if (timeout < 0)
267                 {
268                     return null;
269                 }
270                 while (true)
271                 {
272                     this.head.wait( timeout, nanos );
273                     
274                     // check if the element was indeed added...
275                     if (this.head.next != null)
276                     {
277                         // yep! Early out!
278                         break;
279                     }
280                     
281                     // Check if we timed-out, or if it was a flakey
282                     // notify
283                     //   - include an epsilon for the floating check...
284                     if (dTimeout > 0.9f)
285                     {
286                         // time-out and a null, so crap out without doing
287                         // anything.
288                         return null;
289                     }
290                 }
291             } // end null checking block
292             
293             // guaranteed to not have a null at this point
294             o = this.head.next.value;
295             
296             // remove the minor memory leak
297             this.head.next.value = null;
298 
299             synchronized( this.head.next )
300             {
301                 this.head.next = this.head.next.next;
302                 this.size--;
303             }
304         }
305         return o;
306     }
307     
308     
309     /**
310      * Retrieves the top-level object from the list without removing it.
311      * It momentarily blocks the retrieval from the list, but does not
312      * wait if the list is empty.  Currently, there is no way to test if
313      * a null was placed in the list, or if the list is empty.
314      *
315      * @return if the list is empty, then <code>null</code> is returned,
316      *    otherwise the contents of the top level element in the list is
317      *    returned without removing it from the list.
318      */
319     public Object   peek()
320     {
321         Object   o = null;
322 
323         synchronized( this.head )
324         {
325             if (this.head.next != null)
326             {
327                 o = this.head.next.value;
328             }
329             // else o = null;
330         }
331         return o;
332     }
333     
334     
335     /**
336      * Checks if the list is empty, by a simple, non-blocking check on
337      * the head element.
338      *
339      * @return <code>true</code> if the list contains no user elements,
340      *    otherwise <code>false</code> if at least one user element is present
341      *    on the list.
342      */
343     public boolean isEmpty()
344     {
345         return (this.head.next == null);
346     }
347     
348     
349     /**
350      * @return the current size of the list.  Since this method is
351      *     completely unsynchronized, the returned value may be off by 1,
352      *     due to threading issues.
353      */
354     public int size()
355     {
356         return this.size;
357     }
358     
359     
360     /**
361      * Removes all the current data in the queue.
362      */
363     public void removeAll()
364     {
365         synchronized( this.head )
366         {
367             synchronized( this.tail.next )
368             {
369                 this.head.next = null;
370                 
371                 // remove the minor memory leak
372                 this.tail.next.value = null;
373                 
374                 this.size = 0;
375             }
376         }
377     }
378 
379 }
380 
381
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags