##### Coverage Report - com.sun.grizzly.connectioncache.impl.concurrent.ConcurrentQueueBlockingImpl

Classes in this File | Line Coverage | Branch Coverage | Complexity
ConcurrentQueueBlockingImpl |
0 % | 0/32
0 % | 0/4
| 0.0;0
ConcurrentQueueBlockingImpl$Entry |
0 % | 0/7
N/A | N/A
| 0.0;0
ConcurrentQueueBlockingImpl$HandleImpl |
0 % | 0/21
0 % | 0/2
| 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 |  |