View Javadoc

1   /*
2    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3    *
4    * Copyright (c) 2007-2010 Oracle and/or its affiliates. All rights reserved.
5    *
6    * The contents of this file are subject to the terms of either the GNU
7    * General Public License Version 2 only ("GPL") or the Common Development
8    * and Distribution License("CDDL") (collectively, the "License").  You
9    * may not use this file except in compliance with the License.  You can
10   * obtain a copy of the License at
11   * https://glassfish.dev.java.net/public/CDDL+GPL_1_1.html
12   * or packager/legal/LICENSE.txt.  See the License for the specific
13   * language governing permissions and limitations under the License.
14   *
15   * When distributing the software, include this License Header Notice in each
16   * file and include the License file at packager/legal/LICENSE.txt.
17   *
18   * GPL Classpath Exception:
19   * Oracle designates this particular file as subject to the "Classpath"
20   * exception as provided by Oracle in the GPL Version 2 section of the License
21   * file that accompanied this code.
22   *
23   * Modifications:
24   * If applicable, add the following below the License Header, with the fields
25   * enclosed by brackets [] replaced by your own identifying information:
26   * "Portions Copyright [year] [name of copyright owner]"
27   *
28   * Contributor(s):
29   * If you wish your version of this file to be governed by only the CDDL or
30   * only the GPL Version 2, indicate your decision by adding "[Contributor]
31   * elects to include this software in this distribution under the [CDDL or GPL
32   * Version 2] license."  If you don't indicate a single choice of license, a
33   * recipient has the option to distribute your version of this file under
34   * either the CDDL, the GPL Version 2 or to extend the choice of license to
35   * its licensees as provided above.  However, if you add GPL Version 2 code
36   * and therefore, elected the GPL Version 2 license, then the option applies
37   * only if the new code is made subject to such option by the copyright
38   * holder.
39   */
40  
41  package com.sun.grizzly.connectioncache.impl.concurrent;
42  
43  import com.sun.grizzly.connectioncache.spi.concurrent.ConcurrentQueue;
44  
45  public class ConcurrentQueueBlockingImpl<V> implements ConcurrentQueue<V> {
46      // This implementation of ConcurrentQueue uses a single lock, which must be
47      // acquired to update the list.  Every operation on this class updates the 
48      // structure, so read/write locking is probably not useful.
49      //
50      // Trying to build a lock-free implementation runs into the usual problems:
51      // we need to atomically update more than one location at a time in the structure.
52      // Short of a transactional memory implementation, we would either need a complicated
53      // implementation implementing recursive fixup, or something like the Ladan-Mozes and
54      // Shavit algorithm (see "An Optimistic Approach to Lock-Free FIFO Queues" 
55      // at http://people.csail.mit.edu/edya/publications/publicationsAndPatents.htm)
56      // that delays fixing up one direction in a double linked list.  However, that
57      // algorithm does not consider general deletion, and I don't know whether that
58      // capability can be easily added or not.
59      // Any of these approaches are quite complicated, and so we won't go there yet.
60      // As always, first make it work, then make it fast(er), but only if necessary.
61      // 
62      // Structure: Head points to a node containing a null value, which is a special marker.
63      // head.next is the first element, head.prev is the last.  The queue is empty if
64      // head.next == head.prev == head.
65      final Entry<V> head = new Entry<V>( null ) ;
66      final Object lock = new Object() ;
67      int count = 0 ;
68  
69      public ConcurrentQueueBlockingImpl() {
70  	head.next = head ;
71  	head.prev = head ;
72      }
73  
74      private final class Entry<V> {
75  	Entry<V> next = null ;
76  	Entry<V> prev = null ;
77  	private HandleImpl<V> handle ;
78  
79  	Entry( V value ) {
80  	    handle = new HandleImpl<V>( this, value ) ;
81  	}
82  
83  	HandleImpl<V> handle() {
84  	    return handle ;
85  	}
86      }
87  
88      private final class HandleImpl<V> implements Handle<V> {
89  	private Entry<V> entry ;
90  	private final V value ;
91  	private boolean valid ;
92  
93  	HandleImpl( Entry<V> entry, V value ) {
94  	    this.entry = entry ;
95  	    this.value = value ;
96  	    this.valid = true ;
97  	}
98  
99  	Entry<V> entry() {
100 	    return entry ;
101 	}
102 
103 	public V value() {
104 	    return value ;
105 	}
106 
107 	/** Delete the element corresponding to this handle 
108 	 * from the queue.  Takes constant time.
109 	 * @return  element corresponding to this handle was removed, (yes or no)
110   */
111 	public boolean remove() {
112 	    synchronized (lock) {
113 		if (!valid) {
114 		    return false ;
115 		}
116 
117 		valid = false ;
118 
119 		entry.next.prev = entry.prev ;
120 		entry.prev.next = entry.next ;
121 		count-- ;
122 	    }
123 
124 	    entry.prev = null ;
125 	    entry.next = null ;
126 	    entry.handle = null ;
127 	    entry = null ;
128 	    valid = false ;
129 	    return true ;
130 	}
131     }
132 
133     public int size() {
134 	synchronized (lock) {
135 	    return count ;
136 	}
137     }
138 
139     /** Add a new element to the tail of the queue.
140      * Returns a handle for the element in the queue.
141      * @param arg  element to offer to the queue
142      * @return  a {@link Handle} for the element in the queue
143      */
144     public Handle<V> offer( V arg ) {
145 	if (arg == null)
146 	    throw new IllegalArgumentException( "Argument cannot be null" ) ;
147 
148 	Entry<V> entry = new Entry<V>( arg ) ;
149 	
150 	synchronized (lock) {
151 	    entry.next = head ;
152 	    entry.prev = head.prev ;
153 	    head.prev.next = entry ;
154 	    head.prev = entry ;
155 	    count++ ;
156 	}
157 
158 	return entry.handle() ;
159     }
160 
161     /** Return an element from the head of the queue.
162      * The element is removed from the queue.
163      * @return  element at the head of the queue
164      */
165     public V poll() {
166 	Entry<V> first = null ;
167 
168 	synchronized (lock) {
169 	    first = head.next ;
170 	    if (first == head)
171 		return null ;
172 	    else {
173 		// assert that the following expression returns true!
174 		first.handle().remove() ;
175 	    }
176 	}
177 
178 	// Once first is removed from the queue, it is invisible to other threads,
179 	// so we don't need to synchronize here.
180 	first.next = null ;
181 	first.prev = null ;
182 	V value = first.handle().value() ;
183 	return value ;
184     }
185 } 
186