Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  //
  //  ========================================================================
  //  Copyright (c) 1995-2013 Mort Bay Consulting Pty. Ltd.
  //  ------------------------------------------------------------------------
  //  All rights reserved. This program and the accompanying materials
  //  are made available under the terms of the Eclipse Public License v1.0
  //  and Apache License v2.0 which accompanies this distribution.
  //
  //      The Eclipse Public License is available at
 //      http://www.eclipse.org/legal/epl-v10.html
 //
 //      The Apache License v2.0 is available at
 //      http://www.opensource.org/licenses/apache2.0.php
 //
 //  You may elect to redistribute this code under either of these licenses.
 //  ========================================================================
 //
 
 package org.eclipse.jetty.util;
 
 
 
 /* ------------------------------------------------------------ */
Queue backed by a circular array. This queue is uses a variant of the two lock queue algorithm to provide an efficient queue or list backed by a growable circular array. This queue also has a partial implementation of java.util.concurrent.BlockingQueue, specifically the take() and poll(long,java.util.concurrent.TimeUnit) methods. Unlike java.util.concurrent.ArrayBlockingQueue, this class is able to grow and provides a blocking put call.

The queue has both a capacity (the size of the array currently allocated) and a limit (the maximum size that may be allocated), which defaults to java.lang.Integer.MAX_VALUE.

Parameters:
<E> The element type
 
 public class BlockingArrayQueue<E> extends AbstractList<E> implements BlockingQueue<E>
 {
     public final int DEFAULT_CAPACITY=128;
     public final int DEFAULT_GROWTH=64;
     private final int _limit;
     private final AtomicInteger _size=new AtomicInteger();
     private final int _growCapacity;
     
     private volatile int _capacity;
     private Object[] _elements;
     
     private final ReentrantLock _headLock = new ReentrantLock();
     private final Condition _notEmpty = .newCondition();
     private int _head;
 
     // spacers created to prevent false sharing between head and tail http://en.wikipedia.org/wiki/False_sharing
     // TODO verify this has benefits
     private long _space0;
     private long _space1;
     private long _space2;
     private long _space3;
     private long _space4;
     private long _space5;
     private long _space6;
     private long _space7;
     
     private final ReentrantLock _tailLock = new ReentrantLock();
     private int _tail;
     
 
     /* ------------------------------------------------------------ */
    
Create a growing partially blocking Queue
 
     public BlockingArrayQueue()
     {
         =new Object[];
         =;
         =.;
         =.;
     }
 
     /* ------------------------------------------------------------ */
    
Create a fixed size partially blocking Queue

Parameters:
limit The initial capacity and the limit.
 
     public BlockingArrayQueue(int limit)
     {
         =new Object[limit];
         =.;
         =-1;
         =limit;
    }
    /* ------------------------------------------------------------ */
    
Create a growing partially blocking Queue.

Parameters:
capacity Initial capacity
growBy Incremental capacity.
    public BlockingArrayQueue(int capacity,int growBy)
    {
        =new Object[capacity];
        =.;
        =growBy;
        =.;
    }
    /* ------------------------------------------------------------ */
    
Create a growing limited partially blocking Queue.

Parameters:
capacity Initial capacity
growBy Incremental capacity.
limit maximum capacity.
    public BlockingArrayQueue(int capacity,int growBy,int limit)
    {
        if (capacity>limit)
            throw new IllegalArgumentException();
        
        =new Object[capacity];
        =.;
        =growBy;
        =limit;
    }
    /* ------------------------------------------------------------ */
    public int getCapacity()
    {
        return ;
    }
    /* ------------------------------------------------------------ */
    public int getLimit()
    {
        return ;
    }
    
    /* ------------------------------------------------------------ */
    @Override
    public boolean add(E e)
    {
        return offer(e);
    }
    
    /* ------------------------------------------------------------ */
    public E element()
    {
        E e = peek();
        if (e==null)
            throw new NoSuchElementException();
        return e;
    }
    
    /* ------------------------------------------------------------ */
    @SuppressWarnings("unchecked")
    public E peek()
    {
        if (.get() == 0)
            return null;
        
        E e = null;
        .lock(); // Size cannot shrink
        try 
        {
            if (.get() > 0) 
                e = (E)[];
        } 
        finally 
        {
            .unlock();
        }
        
        return e;
    }
    /* ------------------------------------------------------------ */
    public boolean offer(E e)
    {
        if (e == null
            throw new NullPointerException();
        
        boolean not_empty=false;
        .lock();  // size cannot grow... only shrink
        try 
        {
            if (.get() >= 
                return false;
            
            // should we expand array?
            if (.get()==)
            {
                .lock();   // Need to grow array
                try
                {
                    if (!grow())
                        return false;
                }
                finally
                {
                    .unlock();
                }
            }
            // add the element
            []=e;
            =(+1)%;
            not_empty=0==.getAndIncrement();
            
        } 
        finally 
        {
            .unlock();
        }
        
        if (not_empty)
        {
            .lock();
            try
            {
                .signal();
            }
            finally
            {
                .unlock();
            }
        }  
        return true;
    }
    /* ------------------------------------------------------------ */
    @SuppressWarnings("unchecked")
    public E poll()
    {
        if (.get() == 0)
            return null;
        
        E e = null;
        .lock(); // Size cannot shrink
        try 
        {
            if (.get() > 0) 
            {
                final int head=;
                e = (E)[head];
                [head]=null;
                =(head+1)%;
                
                if (.decrementAndGet()>0)
                    .signal();
            }
        } 
        finally 
        {
            .unlock();
        }
        
        return e;
    }
    /* ------------------------------------------------------------ */
    
Retrieves and removes the head of this queue, waiting if no elements are present on this queue.

Returns:
the head of this queue
Throws:
java.lang.InterruptedException if interrupted while waiting.
    @SuppressWarnings("unchecked")
    public E take() throws InterruptedException
    {
        E e = null;
        .lockInterruptibly();  // Size cannot shrink
        try 
        {
            try 
            {
                while (.get() == 0)
                {
                    .await();
                }
            } 
            catch (InterruptedException ie
            {
                .signal();
                throw ie;
            }
            final int head=;
            e = (E)[head];
            [head]=null;
            =(head+1)%;
            if (.decrementAndGet()>0)
                .signal();
        } 
        finally 
        {
            .unlock();
        }
        
        return e;
    }
    /* ------------------------------------------------------------ */
    
Retrieves and removes the head of this queue, waiting if necessary up to the specified wait time if no elements are present on this queue.

Parameters:
time how long to wait before giving up, in units of unit
unit a TimeUnit determining how to interpret the timeout parameter
Returns:
the head of this queue, or null if the specified waiting time elapses before an element is present.
Throws:
java.lang.InterruptedException if interrupted while waiting.
    @SuppressWarnings("unchecked")
    public E poll(long timeTimeUnit unitthrows InterruptedException
    {
        
        E e = null;
        long nanos = unit.toNanos(time);
        
        .lockInterruptibly(); // Size cannot shrink
        try 
        {    
            try 
            {
                while (.get() == 0)
                {
                    if (nanos<=0)
                        return null;
                    nanos = .awaitNanos(nanos);
                }
            } 
            catch (InterruptedException ie
            {
                .signal();
                throw ie;
            }
            e = (E)[];
            []=null;
            =(+1)%;
            if (.decrementAndGet()>0)
                .signal();
        } 
        finally 
        {
            .unlock();
        }
        
        return e;
    }
    /* ------------------------------------------------------------ */
    public E remove()
    {
        E e=poll();
        if (e==null)
            throw new NoSuchElementException();
        return e;
    }
    /* ------------------------------------------------------------ */
    @Override
    public void clear()
    {
        .lock();
        try
        {
            .lock();
            try
            {
                =0;
                =0;
                .set(0);
            }
            finally
            {
                .unlock();
            }
        }
        finally
        {
            .unlock();
        }
    }
    /* ------------------------------------------------------------ */
    @Override
    public boolean isEmpty()
    {
        return .get()==0;
    }
    /* ------------------------------------------------------------ */
    @Override
    public int size()
    {
        return .get();
    }
    /* ------------------------------------------------------------ */
    @SuppressWarnings("unchecked")
    @Override
    public E get(int index)
    {
        .lock();
        try
        {
            .lock();
            try
            {
                if (index<0 || index>=.get())
                    throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="++")");
                int i = +index;
                if (i>=)
                    i-=;
                return (E)[i];
            }
            finally
            {
                .unlock();
            }
        }
        finally
        {
            .unlock();
        }
    }
    
    /* ------------------------------------------------------------ */
    @Override
    public E remove(int index)
    {
        .lock();
        try
        {
            .lock();
            try
            {
                if (index<0 || index>=.get())
                    throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="++")");
                int i = +index;
                if (i>=)
                    i-=;
                @SuppressWarnings("unchecked")
                E old=(E)[i];
                if (i<)
                {
                    System.arraycopy(,i+1,,i,-i);
                    --;
                    .decrementAndGet();
                }
                else
                {
                    System.arraycopy(,i+1,,i,-i-1);
                    if (>0)
                    {
                        []=[0];
                        System.arraycopy(,1,,0,-1);
                        --;
                    }
                    else
                        =-1;
                    .decrementAndGet();
                }
                return old;
            }
            finally
            {
                .unlock();
            }
        }
        finally
        {
            .unlock();
        }
    }
    /* ------------------------------------------------------------ */
    @Override
    public E set(int index, E e)
    {
        if (e == null
            throw new NullPointerException();
        .lock();
        try
        {
            .lock();
            try
            {
                if (index<0 || index>=.get())
                    throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="++")");
                int i = +index;
                if (i>=)
                    i-=;
                @SuppressWarnings("unchecked")
                E old=(E)[i];
                [i]=e;
                return old;
            }
            finally
            {
                .unlock();
            }
        }
        finally
        {
            .unlock();
        }
    }
    
    /* ------------------------------------------------------------ */
    @Override
    public void add(int index, E e)
    {
        if (e == null
            throw new NullPointerException();
        .lock();
        try
        {
            .lock();
            try
            {
                if (index<0 || index>.get())
                    throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="++")");
                if (index==.get())
                {
                    add(e);
                }
                else
                {
                    if (==)
                        if (!grow())
                            throw new IllegalStateException("full");
                    int i = +index;
                    if (i>=)
                        i-=;
                    .incrementAndGet();
                    =(+1)%;
                    if (i<)
                    {
                        System.arraycopy(,i,,i+1,-i);
                        [i]=e;
                    }
                    else
                    {
                        if (>0)
                        {
                            System.arraycopy(,0,,1,);
                            [0]=[-1];
                        }
                        System.arraycopy(,i,,i+1,-i-1);
                        [i]=e;
                    }
                }
            }
            finally
            {
                .unlock();
            }
        }
        finally
        {
            .unlock();
        }
    }
    /* ------------------------------------------------------------ */
    private boolean grow()
    {
        if (<=0)
            return false;
        .lock();
        try
        {
            .lock();
            try
            {
                final int head=;
                final int tail=;
                final int new_tail;
                Object[] elements=new Object[+];
                if (head<tail)
                {
                    new_tail=tail-head;
                    System.arraycopy(,head,elements,0,new_tail);
                }
                else if (head>tail || .get()>0)
                {
                    new_tail=+tail-head;
                    int cut=-head;
                    System.arraycopy(,head,elements,0,cut);
                    System.arraycopy(,0,elements,cut,tail);
                }
                else
                {
                    new_tail=0;
                }
                =elements;
                =.;
                =0;
                =new_tail
                return true;
            }
            finally
            {
                .unlock();
            }
        }
        finally
        {
            .unlock();
        }
    }
    /* ------------------------------------------------------------ */
    public int drainTo(Collection<? super E> c)
    {
        throw new UnsupportedOperationException();
    }
    /* ------------------------------------------------------------ */
    public int drainTo(Collection<? super E> cint maxElements)
    {
        throw new UnsupportedOperationException();
    }
    /* ------------------------------------------------------------ */
    public boolean offer(E olong timeoutTimeUnit unitthrows InterruptedException
    {
        throw new UnsupportedOperationException();
    }
    /* ------------------------------------------------------------ */
    public void put(E othrows InterruptedException
    {
        if (!add(o))
            throw new IllegalStateException("full");
    }
    /* ------------------------------------------------------------ */
    public int remainingCapacity()
    {
        .lock();
        try
        {
            .lock();
            try
            {
                return getCapacity()-size();
            }
            finally
            {
                .unlock();
            }
        }
        finally
        {
            .unlock();
        }
    }
    
    /* ------------------------------------------------------------ */
    long sumOfSpace()
    {
        // this method exists to stop clever optimisers removing the spacers
        return ++ +++ +++ +++ +++ +++ +++ +++; 
    }
New to GrepCode? Check out our FAQ X