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
ConcurrentQueueBlockingImpl$Entry
0 %
0/7
N/A
0
ConcurrentQueueBlockingImpl$HandleImpl
0 %
0/21
0 %
0/2
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