001: /*
002: * @(#)SynchQueue.java 0.9.0 04/26/2000 - 13:39:11
003: *
004: * Copyright (C) 2000,,2003 2002 Matt Albrecht
005: * groboclown@users.sourceforge.net
006: * http://groboutils.sourceforge.net
007: *
008: * Permission is hereby granted, free of charge, to any person obtaining a
009: * copy of this software and associated documentation files (the "Software"),
010: * to deal in the Software without restriction, including without limitation
011: * the rights to use, copy, modify, merge, publish, distribute, sublicense,
012: * and/or sell copies of the Software, and to permit persons to whom the
013: * Software is furnished to do so, subject to the following conditions:
014: *
015: * The above copyright notice and this permission notice shall be included in
016: * all copies or substantial portions of the Software.
017: *
018: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
019: * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
020: * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
021: * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
022: * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
023: * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
024: * DEALINGS IN THE SOFTWARE.
025: */
026:
027: package net.sourceforge.groboutils.util.datastruct.v1;
028:
029: /**
030: * A Queue optimized for synchronized access. If a request is made to dequeue()
031: * an item on an empty list, then the requesting thread waits until
032: * an object is placed on the queue.
033: * <P>
034: * Care has been taken to ensure proper synchronization. Synchronization
035: * has been optimized so that adding an element to the list does not stop
036: * access to removing an item off the list. The only conflicts occur when
037: * the list has 1 or less items. All synchronization is performed on
038: * internal objects, so the queue itself is still available for outside
039: * classes to use as a synchronization key.
040: * <P>
041: * An additional optimization can be made by pooling the ListElement objects,
042: * although it leads to another syncrhonization collision. An alternative
043: * would be to make a ListElement specific synch-queue which only stores
044: * ListElement objects, and doesn't care about the stored values. To prevent
045: * it from having a major memory footprint, it could set a cap on the number
046: * of elements it stores.
047: * <P>
048: * A small memory leak is present, for performance purposes. If the
049: * list is "emptied", then there still remains a reference to a list element
050: * on the tail. I have optimized this by nulling out the referenced value,
051: * but the ListElement remains. Hopefully, a single ListElement won't be
052: * much of a memory burden.
053: * <P>
054: * <H3>Changes made for 0.9.1:</H3>
055: * <UL>
056: * <LI>The inner ListElement class has been changed to be a private
057: * static class. This reduces a bit of a memory overhead caused by the
058: * original implementation of having the class be non-static.
059: * <LI>Because of the ordering of the <tt>size</tt> assignment, and
060: * that the {@link #size()} method is unsynchronized, a situation
061: * could occur where {@link #size()} can return an invalid number
062: * (see <a href="http://sourceforge.net/tracker/index.php?func=detail&aid=459457&group_id=22594&atid=375589">
063: * bug #459457 </a>), such as -9.
064: * <P>
065: * A quick analysis this may happen during the enqueue method
066: * when an optimizer sets the tail to the new value before it
067: * sets the size.
068: * <P>
069: * The fix involves adding another lock in the {@link
070: * #enqueue( Object )}
071: * method around the new element (which will become the next tail
072: * element), and making the {@link SynchQueue.ListElement.next}
073: * and <tt>size</tt> values volatile (this will force their setting
074: * to be in the same order specified in the code).
075: * <LI>Removed the double-check locking optimization due to possible
076: * failures occuring with it.
077: * </UL>
078: *
079: * @author Matt Albrecht <a href="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
080: * @since April 26, 2000 (0.9.0 Alpha)
081: * @version $Date: 2003/02/10 22:52:44 $
082: */
083: public class SynchQueue {
084: /**
085: * Inner class to maintain the list's objects, and a next pointer.
086: */
087: private static class ListElement {
088: public Object value;
089: public volatile ListElement next;
090:
091: public ListElement() {
092: }
093:
094: public ListElement(Object o) {
095: this .value = o;
096: }
097: }
098:
099: /**
100: * List pointers; head points to the removal point, and tail points
101: * to the addition point.
102: */
103: private ListElement head, tail;
104:
105: /**
106: * Internal size of the queue.
107: */
108: private volatile int size = 0;
109:
110: /**
111: * Create a new Synchronized Queue with an empty list.
112: */
113: public SynchQueue() {
114: this .head = new ListElement();
115: this .tail = new ListElement();
116: this .tail.next = new ListElement();
117: }
118:
119: /**
120: * Adds an element to the end of the queue. If the list is empty,
121: * then the next waiting thread is woken up. If the list has one or
122: * fewer elements, this this method will block any access to the queue,
123: * otherwise this only blocks access to adding to the list.
124: *
125: * @param o the object to place at the end of the list.
126: */
127: public void enqueue(Object o) {
128: ListElement le = new ListElement(o);
129: synchronized (le) {
130:
131: // note: double-checked locking does not work. See
132: // http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
133: // HOWEVER:
134: // we are doing an object pointer assignment, not a new Object()
135: // operation.
136: // "It will work for 32-bit primitive values
137: // "Although the double-checked locking idiom cannot be used
138: // for references to objects, it can work for 32-bit primitive
139: // values (e.g., int's or float's). Note that it does not work
140: // for long's or double's, since unsynchronized reads/writes of
141: // 64-bit primitives are not guaranteed to be atomic."
142: //
143: // So... will it work? Probably not, due to additional logic
144: // besides just the assignment.
145:
146: synchronized (this .head) {
147: if (this .head.next == null) {
148: this .head.next = le;
149: this .head.notify();
150: }
151: }
152:
153: synchronized (this .tail.next) {
154: this .size++;
155: this .tail.next.next = le;
156: this .tail.next = le;
157: }
158: }
159: }
160:
161: /**
162: * Removes and returns the first element in the list. If the list is
163: * empty, then the thread waits until a new element is placed onto the list.
164: * In general, this method will not be blocked by the enqueue() method.
165: *
166: * @see java.lang.Thread#interrupt()
167: * @see #enqueue( Object )
168: * @see #dequeue( long, int )
169: * @see #dequeue( long )
170: * @return the first element on the list, or <tt>null</tt> if a time-out
171: * occured.
172: * @exception InterruptedException thrown if the thread, while waiting,
173: * is interrupted.
174: */
175: public Object dequeue() throws InterruptedException {
176: return dequeue(0, 0);
177: }
178:
179: /**
180: * Removes and returns the first element in the list. If the list is
181: * empty, then the thread waits until a new element is placed onto the list.
182: * In general, this method will not be blocked by the enqueue() method.
183: * <P>
184: * The wait can be given a maximum time by specifying the <tt>timeout</tt>
185: * as a non-zero value. This means that if the given
186: * time expires, and nothing is in the queue, then <tt>null</tt> is
187: * returned. This allows for polling-like features for the queue.
188: * If <tt>timeout</tt> is zero, then real time is not taken into
189: * consideration and the thread simply waits until the object is added to
190: * the queue. If <tt>timeout</tt> is less than zero, then no waiting
191: * is performed if the queue is empty, and <tt>null</tt> is returned
192: * immediately.
193: *
194: * @param timeout the maximum time to wait in milliseconds.
195: * @see java.lang.Thread#interrupt()
196: * @see #enqueue( Object )
197: * @see #dequeue( long, int )
198: * @see #dequeue()
199: * @return the first element on the list, or <tt>null</tt> if a time-out
200: * occured.
201: * @exception InterruptedException thrown if the thread, while waiting,
202: * is interrupted.
203: */
204: public Object dequeue(long timeout) throws InterruptedException {
205: return dequeue(timeout, 0);
206: }
207:
208: /**
209: * Removes and returns the first element in the list. If the list is
210: * empty, then the thread waits until a new element is placed onto the list.
211: * In general, this method will not be blocked by the enqueue() method.
212: * <P>
213: * The wait can be given a maximum time by specifying the <tt>timeout</tt>
214: * or <tt>nanos</tt> as non-zero values. This means that if the given
215: * time expires, and nothing is in the queue, then <tt>null</tt> is
216: * returned. This allows for polling-like features for the queue.
217: * The total wait time in milliseconds <tt> = 1000000*timeout + nanos</tt>.
218: * If the total wait is zero, then real time is not taken into
219: * consideration and the thread simply waits until the object is added to
220: * the queue. If <tt>timeout</tt> is less than zero, then no waiting
221: * is performed if the queue is empty, and <tt>null</tt> is returned
222: * immediately.
223: *
224: * @param timeout the maximum time to wait in milliseconds.
225: * @param nanos additional time, in nanoseconds range 0-999999.
226: * @see java.lang.Thread#interrupt()
227: * @see #enqueue( Object )
228: * @see #dequeue()
229: * @see #dequeue( long )
230: * @return the first element on the list, or <tt>null</tt> if a time-out
231: * occured.
232: * @exception InterruptedException thrown if the thread, while waiting,
233: * is interrupted.
234: */
235: public Object dequeue(long timeout, int nanos)
236: throws InterruptedException {
237: Object o;
238: float dTimeout = (float) (timeout + nanos);
239:
240: synchronized (this .head) {
241: // this used to be a while (head.next == null) loop,
242: // but now it's ugly to reduce the number of "if" checks.
243: if (this .head.next == null) {
244: // quick check, but needs synchronization
245: if (timeout < 0) {
246: return null;
247: }
248: while (true) {
249: this .head.wait(timeout, nanos);
250:
251: // check if the element was indeed added...
252: if (this .head.next != null) {
253: // yep! Early out!
254: break;
255: }
256:
257: // Check if we timed-out, or if it was a flakey
258: // notify
259: // - include an epsilon for the floating check...
260: if (dTimeout > 0.9f) {
261: // time-out and a null, so crap out without doing
262: // anything.
263: return null;
264: }
265: }
266: } // end null checking block
267:
268: // guaranteed to not have a null at this point
269: o = this .head.next.value;
270:
271: // remove the minor memory leak
272: this .head.next.value = null;
273:
274: synchronized (this .head.next) {
275: this .head.next = this .head.next.next;
276: this .size--;
277: }
278: }
279: return o;
280: }
281:
282: /**
283: * Retrieves the top-level object from the list without removing it.
284: * It momentarily blocks the retrieval from the list, but does not
285: * wait if the list is empty. Currently, there is no way to test if
286: * a null was placed in the list, or if the list is empty.
287: *
288: * @return if the list is empty, then <code>null</code> is returned,
289: * otherwise the contents of the top level element in the list is
290: * returned without removing it from the list.
291: */
292: public Object peek() {
293: Object o = null;
294:
295: synchronized (this .head) {
296: if (this .head.next != null) {
297: o = this .head.next.value;
298: }
299: // else o = null;
300: }
301: return o;
302: }
303:
304: /**
305: * Checks if the list is empty, by a simple, non-blocking check on
306: * the head element.
307: *
308: * @return <code>true</code> if the list contains no user elements,
309: * otherwise <code>false</code> if at least one user element is present
310: * on the list.
311: */
312: public boolean isEmpty() {
313: return (this .head.next == null);
314: }
315:
316: /**
317: * @return the current size of the list. Since this method is
318: * completely unsynchronized, the returned value may be off by 1,
319: * due to threading issues.
320: */
321: public int size() {
322: return this .size;
323: }
324:
325: /**
326: * Removes all the current data in the queue.
327: */
328: public void removeAll() {
329: synchronized (this .head) {
330: synchronized (this .tail.next) {
331: this .head.next = null;
332:
333: // remove the minor memory leak
334: this .tail.next.value = null;
335:
336: this .size = 0;
337: }
338: }
339: }
340:
341: }
|