Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
ConcurrentQueueNonBlockingImpl |
|
| 0.0;0 | ||||
ConcurrentQueueNonBlockingImpl$Entry |
|
| 0.0;0 | ||||
ConcurrentQueueNonBlockingImpl$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 | package com.sun.grizzly.connectioncache.impl.concurrent; | |
40 | ||
41 | import com.sun.grizzly.connectioncache.spi.concurrent.ConcurrentQueue; | |
42 | ||
43 | public class ConcurrentQueueNonBlockingImpl<V> implements ConcurrentQueue<V> { | |
44 | // This implementation of ConcurrentQueue uses a non-blocking algorithm (TBD). | |
45 | // For now, this is the same as the blocking impl. | |
46 | // | |
47 | // Trying to build a lock-free implementation runs into the usual problems: | |
48 | // we need to atomically update more than one location at a time in the structure. | |
49 | // Short of a transactional memory implementation, we would either need a complicated | |
50 | // implementation implementing recursive fixup, or something like the Ladan-Mozes and | |
51 | // Shavit algorithm (see "An Optimistic Approach to Lock-Free FIFO Queues" | |
52 | // at http://people.csail.mit.edu/edya/publications/publicationsAndPatents.htm) | |
53 | // that delays fixing up one direction in a double linked list. However, that | |
54 | // algorithm does not consider general deletion, and I don't know whether that | |
55 | // capability can be easily added or not. | |
56 | // Any of these approaches are quite complicated, and so we won't go there yet. | |
57 | // As always, first make it work, then make it fast(er), but only if necessary. | |
58 | // | |
59 | // Structure: Head points to a node containing a null value, which is a special marker. | |
60 | // head.next is the first element, head.prev is the last. The queue is empty if | |
61 | // head.next == head.prev == head. | |
62 | 0 | final Entry<V> head = new Entry<V>( null ) ; |
63 | 0 | final Object lock = new Object() ; |
64 | 0 | int count = 0 ; |
65 | ||
66 | 0 | public ConcurrentQueueNonBlockingImpl() { |
67 | 0 | head.next = head ; |
68 | 0 | head.prev = head ; |
69 | 0 | } |
70 | ||
71 | 0 | private final class Entry<V> { |
72 | 0 | Entry<V> next = null ; |
73 | 0 | Entry<V> prev = null ; |
74 | private HandleImpl<V> handle ; | |
75 | ||
76 | 0 | Entry( V value ) { |
77 | 0 | handle = new HandleImpl<V>( this, value ) ; |
78 | 0 | } |
79 | ||
80 | HandleImpl<V> handle() { | |
81 | 0 | return handle ; |
82 | } | |
83 | } | |
84 | ||
85 | private final class HandleImpl<V> implements Handle<V> { | |
86 | private Entry<V> entry ; | |
87 | private final V value ; | |
88 | private boolean valid ; | |
89 | ||
90 | 0 | HandleImpl( Entry<V> entry, V value ) { |
91 | 0 | this.entry = entry ; |
92 | 0 | this.value = value ; |
93 | 0 | this.valid = true ; |
94 | 0 | } |
95 | ||
96 | Entry<V> entry() { | |
97 | 0 | return entry ; |
98 | } | |
99 | ||
100 | public V value() { | |
101 | 0 | return value ; |
102 | } | |
103 | ||
104 | /** Delete the element corresponding to this handle | |
105 | * from the queue. Takes constant time. | |
106 | */ | |
107 | public boolean remove() { | |
108 | 0 | synchronized (lock) { |
109 | 0 | if (!valid) { |
110 | 0 | return false ; |
111 | } | |
112 | ||
113 | 0 | valid = false ; |
114 | ||
115 | 0 | entry.next.prev = entry.prev ; |
116 | 0 | entry.prev.next = entry.next ; |
117 | 0 | count-- ; |
118 | 0 | } |
119 | ||
120 | 0 | entry.prev = null ; |
121 | 0 | entry.next = null ; |
122 | 0 | entry.handle = null ; |
123 | 0 | entry = null ; |
124 | 0 | valid = false ; |
125 | 0 | return true ; |
126 | } | |
127 | } | |
128 | ||
129 | public int size() { | |
130 | 0 | synchronized (lock) { |
131 | 0 | return count ; |
132 | 0 | } |
133 | } | |
134 | ||
135 | /** Add a new element to the tail of the queue. | |
136 | * Returns a handle for the element in the queue. | |
137 | */ | |
138 | public Handle<V> offer( V arg ) { | |
139 | 0 | if (arg == null) |
140 | 0 | throw new IllegalArgumentException( "Argument cannot be null" ) ; |
141 | ||
142 | 0 | Entry<V> entry = new Entry<V>( arg ) ; |
143 | ||
144 | 0 | synchronized (lock) { |
145 | 0 | entry.next = head ; |
146 | 0 | entry.prev = head.prev ; |
147 | 0 | head.prev.next = entry ; |
148 | 0 | head.prev = entry ; |
149 | 0 | count++ ; |
150 | 0 | } |
151 | ||
152 | 0 | return entry.handle() ; |
153 | } | |
154 | ||
155 | /** Return an element from the head of the queue. | |
156 | * The element is removed from the queue. | |
157 | */ | |
158 | public V poll() { | |
159 | 0 | Entry<V> first = null ; |
160 | ||
161 | 0 | synchronized (lock) { |
162 | 0 | first = head.next ; |
163 | 0 | if (first == head) |
164 | 0 | return null ; |
165 | else { | |
166 | // assert that the following expression returns true! | |
167 | 0 | first.handle().remove() ; |
168 | } | |
169 | 0 | } |
170 | ||
171 | // Once first is removed from the queue, it is invisible to other threads, | |
172 | // so we don't need to synchronize here. | |
173 | 0 | first.next = null ; |
174 | 0 | first.prev = null ; |
175 | 0 | V value = first.handle().value() ; |
176 | 0 | return value ; |
177 | } | |
178 | } | |
179 |