Coverage Report - com.sun.grizzly.connectioncache.impl.concurrent.ConcurrentQueueNonBlockingImpl
 
Classes in this File Line Coverage Branch Coverage Complexity
ConcurrentQueueNonBlockingImpl
0 %
0/32
0 %
0/4
0
ConcurrentQueueNonBlockingImpl$Entry
0 %
0/7
N/A
0
ConcurrentQueueNonBlockingImpl$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  
 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