0N/A/*
2362N/A * Copyright (c) 1999, Oracle and/or its affiliates. All rights reserved.
0N/A *
0N/A * Redistribution and use in source and binary forms, with or without
0N/A * modification, are permitted provided that the following conditions
0N/A * are met:
0N/A *
0N/A * - Redistributions of source code must retain the above copyright
0N/A * notice, this list of conditions and the following disclaimer.
0N/A *
0N/A * - Redistributions in binary form must reproduce the above copyright
0N/A * notice, this list of conditions and the following disclaimer in the
0N/A * documentation and/or other materials provided with the distribution.
0N/A *
2362N/A * - Neither the name of Oracle nor the names of its
0N/A * contributors may be used to endorse or promote products derived
0N/A * from this software without specific prior written permission.
0N/A *
0N/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
0N/A * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
0N/A * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
0N/A * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
0N/A * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
0N/A * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
0N/A * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
0N/A * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
0N/A * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
0N/A * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0N/A * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0N/A */
0N/A
0N/A/*
4378N/A * This source code is provided to illustrate the usage of a given feature
4378N/A * or technique and has been deliberately simplified. Additional steps
4378N/A * required for a production-quality application, such as security checks,
4378N/A * input validation and proper error handling, might not be present in
4378N/A * this sample code.
4378N/A */
4378N/A
4378N/A
4378N/A/*
0N/A File: SLQ.java
0N/A Originally: LinkedQueue.java
0N/A
0N/A Originally written by Doug Lea and released into the public domain.
0N/A This may be used for any purposes whatsoever without acknowledgment.
0N/A Thanks for the assistance and support of Sun Microsystems Labs,
0N/A and everyone contributing, testing, and using this code.
0N/A
0N/A History:
0N/A Date Who What
0N/A 11Jun1998 dl Create public version
0N/A 25aug1998 dl added peek
0N/A 10dec1998 dl added isEmpty
0N/A 10jun1999 bc modified for isolated use
0N/A*/
0N/A
0N/A// Original was in package EDU.oswego.cs.dl.util.concurrent;
0N/A
0N/A/**
0N/A * A linked list based channel implementation,
0N/A * adapted from the TwoLockQueue class from CPJ.
0N/A * The algorithm avoids contention between puts
0N/A * and takes when the queue is not empty.
0N/A * Normally a put and a take can proceed simultaneously.
0N/A * (Although it does not allow multiple concurrent puts or takes.)
0N/A * This class tends to perform more efficently than
0N/A * other Channel implementations in producer/consumer
0N/A * applications.
0N/A * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
0N/A **/
0N/A
0N/Apublic class LinkedQueue {
0N/A
0N/A
0N/A /**
0N/A * Dummy header node of list. The first actual node, if it exists, is always
0N/A * at head_.next. After each take, the old first node becomes the head.
0N/A **/
0N/A protected LinkedNode head_;
0N/A protected int count_;
0N/A /**
0N/A * Helper monitor for managing access to last node, in case it is also first.
0N/A * last_ and waitingForTake_ ONLY used with synch on appendMonitor_
0N/A **/
0N/A protected final Object lastMonitor_ = new Object();
0N/A
0N/A /**
0N/A * The last node of list. Put() appends to list, so modifies last_
0N/A **/
0N/A protected LinkedNode last_;
0N/A
0N/A /**
0N/A * The number of threads waiting for a take.
0N/A * Notifications are provided in put only if greater than zero.
0N/A * The bookkeeping is worth it here since in reasonably balanced
0N/A * usages, the notifications will hardly ever be necessary, so
0N/A * the call overhead to notify can be eliminated.
0N/A **/
0N/A protected int waitingForTake_ = 0;
0N/A
0N/A public LinkedQueue() {
0N/A head_ = new LinkedNode(null);
0N/A last_ = head_;
0N/A count_ = 0;
0N/A }
0N/A
0N/A /** Main mechanics for put/offer **/
0N/A protected void insert(Object x) {
0N/A synchronized(lastMonitor_) {
0N/A LinkedNode p = new LinkedNode(x);
0N/A last_.next = p;
0N/A last_ = p;
0N/A count_++;
0N/A if (count_ > 1000 && (count_ % 1000 == 0))
0N/A System.out.println("In Queue : " + count_);
0N/A if (waitingForTake_ > 0)
0N/A lastMonitor_.notify();
0N/A }
0N/A }
0N/A
0N/A /** Main mechanics for take/poll **/
0N/A protected synchronized Object extract() {
0N/A Object x = null;
0N/A LinkedNode first = head_.next;
0N/A if (first != null) {
0N/A x = first.value;
0N/A first.value = null;
0N/A head_ = first;
0N/A count_ --;
0N/A }
0N/A return x;
0N/A }
0N/A
0N/A
0N/A public void put(Object x) throws InterruptedException {
0N/A if (x == null) throw new IllegalArgumentException();
0N/A if (Thread.interrupted()) throw new InterruptedException();
0N/A insert(x);
0N/A }
0N/A
0N/A public boolean offer(Object x, long msecs) throws InterruptedException {
0N/A if (x == null) throw new IllegalArgumentException();
0N/A if (Thread.interrupted()) throw new InterruptedException();
0N/A insert(x);
0N/A return true;
0N/A }
0N/A
0N/A public Object take() throws InterruptedException {
0N/A if (Thread.interrupted()) throw new InterruptedException();
0N/A // try to extract. If fail, then enter wait-based retry loop
0N/A Object x = extract();
0N/A if (x != null)
0N/A return x;
0N/A else {
0N/A synchronized(lastMonitor_) {
0N/A try {
0N/A ++waitingForTake_;
0N/A for (;;) {
0N/A x = extract();
0N/A if (x != null) {
0N/A --waitingForTake_;
0N/A return x;
0N/A }
0N/A else {
0N/A lastMonitor_.wait();
0N/A }
0N/A }
0N/A }
0N/A catch(InterruptedException ex) {
0N/A --waitingForTake_;
0N/A lastMonitor_.notify();
0N/A throw ex;
0N/A }
0N/A }
0N/A }
0N/A }
0N/A
0N/A public synchronized Object peek() {
0N/A LinkedNode first = head_.next;
0N/A if (first != null)
0N/A return first.value;
0N/A else
0N/A return null;
0N/A }
0N/A
0N/A
0N/A public synchronized boolean isEmpty() {
0N/A return head_.next == null;
0N/A }
0N/A
0N/A public Object poll(long msecs) throws InterruptedException {
0N/A if (Thread.interrupted()) throw new InterruptedException();
0N/A Object x = extract();
0N/A if (x != null)
0N/A return x;
0N/A else {
0N/A synchronized(lastMonitor_) {
0N/A try {
0N/A long waitTime = msecs;
0N/A long start = (msecs <= 0)? 0 : System.currentTimeMillis();
0N/A ++waitingForTake_;
0N/A for (;;) {
0N/A x = extract();
0N/A if (x != null || waitTime <= 0) {
0N/A --waitingForTake_;
0N/A return x;
0N/A }
0N/A else {
0N/A lastMonitor_.wait(waitTime);
0N/A waitTime = msecs - (System.currentTimeMillis() - start);
0N/A }
0N/A }
0N/A }
0N/A catch(InterruptedException ex) {
0N/A --waitingForTake_;
0N/A lastMonitor_.notify();
0N/A throw ex;
0N/A }
0N/A }
0N/A }
0N/A }
0N/A
0N/A class LinkedNode {
0N/A Object value;
0N/A LinkedNode next = null;
0N/A LinkedNode(Object x) { value = x; }
0N/A LinkedNode(Object x, LinkedNode n) { value = x; next = n; }
0N/A }
0N/A}