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