/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 1997-2008 Sun Microsystems, Inc. All rights reserved. * * The contents of this file are subject to the terms of either the GNU * General Public License Version 2 only ("GPL") or the Common Development * and Distribution License("CDDL") (collectively, the "License"). You * may not use this file except in compliance with the License. You can obtain * a copy of the License at https://glassfish.dev.java.net/public/CDDL+GPL.html * or glassfish/bootstrap/legal/LICENSE.txt. See the License for the specific * language governing permissions and limitations under the License. * * When distributing the software, include this License Header Notice in each * file and include the License file at glassfish/bootstrap/legal/LICENSE.txt. * Sun designates this particular file as subject to the "Classpath" exception * as provided by Sun in the GPL Version 2 section of the License file that * accompanied this code. If applicable, add the following below the License * Header, with the fields enclosed by brackets [] replaced by your own * identifying information: "Portions Copyrighted [year] * [name of copyright owner]" * * Contributor(s): * * If you wish your version of this file to be governed by only the CDDL or * only the GPL Version 2, indicate your decision by adding "[Contributor] * elects to include this software in this distribution under the [CDDL or GPL * Version 2] license." If you don't indicate a single choice of license, a * recipient has the option to distribute your version of this file under * either the CDDL, the GPL Version 2 or to extend the choice of license to * its licensees as provided above. However, if you add GPL Version 2 code * and therefore, elected the GPL Version 2 license, then the option applies * only if the new code is made subject to such option by the copyright * holder. */ /* * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/licenses/publicdomain */ //package com.google.code.yanf4j.util; import java.util.AbstractQueue; import java.util.Collection; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.concurrent.BlockingQueue; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicReference; import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; import java.util.concurrent.locks.LockSupport; /** * An unbounded TransferQueue based on linked nodes. * This queue orders elements FIFO (first-in-first-out) with respect * to any given producer. The head of the queue is that * element that has been on the queue the longest time for some * producer. The tail of the queue is that element that has * been on the queue the shortest time for some producer. * *
Beware that, unlike in most collections, the size * method is NOT a constant-time operation. Because of the * asynchronous nature of these queues, determining the current number * of elements requires a traversal of the elements. * *
This class and its iterator implement all of the * optional methods of the {@link Collection} and {@link * Iterator} interfaces. * *
Memory consistency effects: As with other concurrent * collections, actions in a thread prior to placing an object into a * {@code LinkedTransferQueue} * happen-before * actions subsequent to the access or removal of that element from * the {@code LinkedTransferQueue} in another thread. * * @author Doug Lea * @author The Netty Project (netty-dev@lists.jboss.org) * @author Trustin Lee (tlee@redhat.com) * * @param the type of elements held in this collection * */ public class LinkedTransferQueue extends AbstractQueue implements BlockingQueue { /* * This class extends the approach used in FIFO-mode * SynchronousQueues. See the internal documentation, as well as * the PPoPP 2006 paper "Scalable Synchronous Queues" by Scherer, * Lea & Scott * (http://www.cs.rice.edu/~wns1/papers/2006-PPoPP-SQ.pdf) * * The main extension is to provide different Wait modes for the * main "xfer" method that puts or takes items. These don't * impact the basic dual-queue logic, but instead control whether * or how threads block upon insertion of request or data nodes * into the dual queue. It also uses slightly different * conventions for tracking whether nodes are off-list or * cancelled. */ // Wait modes for xfer method private static final int NOWAIT = 0; private static final int TIMEOUT = 1; private static final int WAIT = 2; /** The number of CPUs, for spin control */ private static final int NCPUS = Runtime.getRuntime().availableProcessors(); /** * The number of times to spin before blocking in timed waits. * The value is empirically derived -- it works well across a * variety of processors and OSes. Empirically, the best value * seems not to vary with number of CPUs (beyond 2) so is just * a constant. */ private static final int maxTimedSpins = NCPUS < 2? 0 : 32; /** * The number of times to spin before blocking in untimed waits. * This is greater than timed value because untimed waits spin * faster since they don't need to check times on each spin. */ private static final int maxUntimedSpins = maxTimedSpins * 16; /** * The number of nanoseconds for which it is faster to spin * rather than to use timed park. A rough estimate suffices. */ private static final long spinForTimeoutThreshold = 1000L; /** * Node class for LinkedTransferQueue. Opportunistically * subclasses from AtomicReference to represent item. Uses Object, * not E, to allow setting item to "this" after use, to avoid * garbage retention. Similarly, setting the next field to this is * used as sentinel that node is off list. */ private static final class QNode extends AtomicReference