paratask.queues
Class WorkStealingQueue<E>

java.lang.Object
  extended by paratask.queues.WorkStealingQueue<E>
Type Parameters:
E - The type of elements held in this collection
All Implemented Interfaces:
java.lang.Iterable<E>, java.util.Collection<E>, java.util.concurrent.BlockingQueue<E>, java.util.Queue<E>
Direct Known Subclasses:
FifoLifoQueue

public class WorkStealingQueue<E>
extends java.lang.Object
implements java.util.concurrent.BlockingQueue<E>

An implementation of a work-stealing queue. Elements are added and removed from the queue using a work-stealing policy.

Elements are added to a thread's local queue, and removed from a thread's local queue using a last in first out (LIFO) policy. If no elements exist in the thread's local queue, an element is stolen using a first in first out (FIFO) policy from another thread's local queue.

Consequently, the "head of the queue" in the context of the WorkStealingQueue refers to the element according to this work-stealing schedule. In other words, "head of the queue" for the thread when it takes from its own local queue refers to the same end where elements are added (i.e. the LIFO end). Similarly, the "head of the queue" for a stealing thread refers to the opposite end of the of the victim's queue (i.e. the FIFO end).

Author:
Nasser Giacaman, Oliver Sinnen

Constructor Summary
WorkStealingQueue()
          Create an empty WorkStealingQueue with maximum capacity and chunksize of 1.
WorkStealingQueue(java.util.Collection<? extends E> c, int chunksize)
          Create a WorkStealingQueue that contains the specified collection of elements and specified chunksize.
WorkStealingQueue(int capacity, int chunksize)
          Create an empty WorkStealingQueue with the specified capacity and chunksize.
 
Method Summary
 boolean add(E e)
          Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
 boolean addAll(java.util.Collection<? extends E> c)
          Adds all of the elements in the specified collection to this collection (optional operation).
 void clear()
          Removes all of the elements from this collection (optional operation).
 boolean contains(java.lang.Object o)
          Returns true if this queue contains the specified element.
 boolean containsAll(java.util.Collection<?> c)
          Returns true if this collection contains all of the elements in the specified collection.
 int drainTo(java.util.Collection<? super E> c)
          Removes all available elements from this queue and adds them to the given collection.
 int drainTo(java.util.Collection<? super E> c, int maxElements)
          Removes at most the given number of available elements from this queue and adds them to the given collection.
 E element()
          Retrieves, but does not remove, the head of this queue.
 boolean isEmpty()
          Returns true if this collection contains no elements.
 java.util.Iterator<E> iterator()
          Returns an iterator over the elements in this collection.
 boolean offer(E e)
          Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and false if no space is currently available.
 boolean offer(E e, long timeout, java.util.concurrent.TimeUnit unit)
          Inserts the specified element into this queue, waiting up to the specified wait time if necessary for space to become available.
 E peek()
          Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
 E poll()
          Retrieves and removes the head of this queue, or returns null if this queue is empty.
 E poll(long timeout, java.util.concurrent.TimeUnit unit)
          Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available.
 void put(E e)
          Inserts the specified element into this queue, waiting if necessary for space to become available.
 int remainingCapacity()
          Returns the number of additional elements that this queue can ideally (in the absence of memory or resource constraints) accept without blocking, or Integer.MAX_VALUE if there is no intrinsic limit.
 E remove()
          Retrieves and removes the head of this queue.
 boolean remove(java.lang.Object o)
          Removes a single instance of the specified element from this queue, if it is present.
 boolean removeAll(java.util.Collection<?> c)
          Removes all of this collection's elements that are also contained in the specified collection (optional operation).
 boolean retainAll(java.util.Collection<?> c)
          Retains only the elements in this collection that are contained in the specified collection (optional operation).
 int size()
          Returns the number of elements in this collection.
 E take()
          Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.
 java.lang.Object[] toArray()
          Returns an array containing all of the elements in this collection.
<T> T[]
toArray(T[] a)
          Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface java.util.Collection
equals, hashCode
 

Constructor Detail

WorkStealingQueue

public WorkStealingQueue()
Create an empty WorkStealingQueue with maximum capacity and chunksize of 1.

See Also:
WorkStealingQueue(int, int), WorkStealingQueue(Collection, int)

WorkStealingQueue

public WorkStealingQueue(int capacity,
                         int chunksize)
Create an empty WorkStealingQueue with the specified capacity and chunksize. Chunksize refers to the number of elements stolen at a time, in the case of a steal.

Parameters:
capacity - The WorkStealingQueue's capacity
chunksize - The chunksize in case of steals
See Also:
WorkStealingQueue(), WorkStealingQueue(Collection, int)

WorkStealingQueue

public WorkStealingQueue(java.util.Collection<? extends E> c,
                         int chunksize)
Create a WorkStealingQueue that contains the specified collection of elements and specified chunksize. The capacity defaults to unlimited.

Parameters:
c - The collection of elements to place inside the WorkStealingQueue
chunksize - The chunksize in case of steals
Method Detail

add

public boolean add(E e)
Description copied from interface: java.util.concurrent.BlockingQueue
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available. When using a capacity-restricted queue, it is generally preferable to use offer.

Specified by:
add in interface java.util.Collection<E>
Specified by:
add in interface java.util.concurrent.BlockingQueue<E>
Specified by:
add in interface java.util.Queue<E>
Parameters:
e - the element to add
Returns:
true (as specified by Collection.add(E))

contains

public boolean contains(java.lang.Object o)
Description copied from interface: java.util.concurrent.BlockingQueue
Returns true if this queue contains the specified element. More formally, returns true if and only if this queue contains at least one element e such that o.equals(e).

Specified by:
contains in interface java.util.Collection<E>
Specified by:
contains in interface java.util.concurrent.BlockingQueue<E>
Parameters:
o - object to be checked for containment in this queue
Returns:
true if this queue contains the specified element

drainTo

public int drainTo(java.util.Collection<? super E> c)
Description copied from interface: java.util.concurrent.BlockingQueue
Removes all available elements from this queue and adds them to the given collection. This operation may be more efficient than repeatedly polling this queue. A failure encountered while attempting to add elements to collection c may result in elements being in neither, either or both collections when the associated exception is thrown. Attempts to drain a queue to itself result in IllegalArgumentException. Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress.

Specified by:
drainTo in interface java.util.concurrent.BlockingQueue<E>
Parameters:
c - the collection to transfer elements into
Returns:
the number of elements transferred

drainTo

public int drainTo(java.util.Collection<? super E> c,
                   int maxElements)
Description copied from interface: java.util.concurrent.BlockingQueue
Removes at most the given number of available elements from this queue and adds them to the given collection. A failure encountered while attempting to add elements to collection c may result in elements being in neither, either or both collections when the associated exception is thrown. Attempts to drain a queue to itself result in IllegalArgumentException. Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress.

Specified by:
drainTo in interface java.util.concurrent.BlockingQueue<E>
Parameters:
c - the collection to transfer elements into
maxElements - the maximum number of elements to transfer
Returns:
the number of elements transferred

offer

public boolean offer(E e)
Description copied from interface: java.util.concurrent.BlockingQueue
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and false if no space is currently available. When using a capacity-restricted queue, this method is generally preferable to BlockingQueue.add(E), which can fail to insert an element only by throwing an exception.

Specified by:
offer in interface java.util.concurrent.BlockingQueue<E>
Specified by:
offer in interface java.util.Queue<E>
Parameters:
e - the element to add
Returns:
true if the element was added to this queue, else false

offer

public boolean offer(E e,
                     long timeout,
                     java.util.concurrent.TimeUnit unit)
              throws java.lang.InterruptedException
Description copied from interface: java.util.concurrent.BlockingQueue
Inserts the specified element into this queue, waiting up to the specified wait time if necessary for space to become available.

Specified by:
offer in interface java.util.concurrent.BlockingQueue<E>
Parameters:
e - the element to add
timeout - how long to wait before giving up, in units of unit
unit - a TimeUnit determining how to interpret the timeout parameter
Returns:
true if successful, or false if the specified waiting time elapses before space is available
Throws:
java.lang.InterruptedException - if interrupted while waiting

poll

public E poll(long timeout,
              java.util.concurrent.TimeUnit unit)
       throws java.lang.InterruptedException
Description copied from interface: java.util.concurrent.BlockingQueue
Retrieves and removes the head of this queue, waiting up to the specified wait time if necessary for an element to become available.

Specified by:
poll in interface java.util.concurrent.BlockingQueue<E>
Parameters:
timeout - 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 available
Throws:
java.lang.InterruptedException - if interrupted while waiting

put

public void put(E e)
         throws java.lang.InterruptedException
Description copied from interface: java.util.concurrent.BlockingQueue
Inserts the specified element into this queue, waiting if necessary for space to become available.

Specified by:
put in interface java.util.concurrent.BlockingQueue<E>
Parameters:
e - the element to add
Throws:
java.lang.InterruptedException - if interrupted while waiting

remainingCapacity

public int remainingCapacity()
Description copied from interface: java.util.concurrent.BlockingQueue
Returns the number of additional elements that this queue can ideally (in the absence of memory or resource constraints) accept without blocking, or Integer.MAX_VALUE if there is no intrinsic limit.

Note that you cannot always tell if an attempt to insert an element will succeed by inspecting remainingCapacity because it may be the case that another thread is about to insert or remove an element.

Specified by:
remainingCapacity in interface java.util.concurrent.BlockingQueue<E>
Returns:
the remaining capacity

remove

public boolean remove(java.lang.Object o)
Description copied from interface: java.util.concurrent.BlockingQueue
Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element e such that o.equals(e), if this queue contains one or more such elements. Returns true if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).

Specified by:
remove in interface java.util.Collection<E>
Specified by:
remove in interface java.util.concurrent.BlockingQueue<E>
Parameters:
o - element to be removed from this queue, if present
Returns:
true if this queue changed as a result of the call

take

public E take()
       throws java.lang.InterruptedException
Description copied from interface: java.util.concurrent.BlockingQueue
Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.

Specified by:
take in interface java.util.concurrent.BlockingQueue<E>
Returns:
the head of this queue
Throws:
java.lang.InterruptedException - if interrupted while waiting

element

public E element()
Description copied from interface: java.util.Queue
Retrieves, but does not remove, the head of this queue. This method differs from peek only in that it throws an exception if this queue is empty.

Specified by:
element in interface java.util.Queue<E>
Returns:
the head of this queue

peek

public E peek()
Description copied from interface: java.util.Queue
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Specified by:
peek in interface java.util.Queue<E>
Returns:
the head of this queue, or null if this queue is empty

poll

public E poll()
Description copied from interface: java.util.Queue
Retrieves and removes the head of this queue, or returns null if this queue is empty.

Specified by:
poll in interface java.util.Queue<E>
Returns:
the head of this queue, or null if this queue is empty

remove

public E remove()
Description copied from interface: java.util.Queue
Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.

Specified by:
remove in interface java.util.Queue<E>
Returns:
the head of this queue

addAll

public boolean addAll(java.util.Collection<? extends E> c)
Description copied from interface: java.util.Collection
Adds all of the elements in the specified collection to this collection (optional operation). The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.)

Specified by:
addAll in interface java.util.Collection<E>
Parameters:
c - collection containing elements to be added to this collection
Returns:
true if this collection changed as a result of the call
See Also:
Collection.add(Object)

clear

public void clear()
Description copied from interface: java.util.Collection
Removes all of the elements from this collection (optional operation). The collection will be empty after this method returns.

Specified by:
clear in interface java.util.Collection<E>

containsAll

public boolean containsAll(java.util.Collection<?> c)
Description copied from interface: java.util.Collection
Returns true if this collection contains all of the elements in the specified collection.

Specified by:
containsAll in interface java.util.Collection<E>
Parameters:
c - collection to be checked for containment in this collection
Returns:
true if this collection contains all of the elements in the specified collection
See Also:
Collection.contains(Object)

isEmpty

public boolean isEmpty()
Description copied from interface: java.util.Collection
Returns true if this collection contains no elements.

Specified by:
isEmpty in interface java.util.Collection<E>
Returns:
true if this collection contains no elements

iterator

public java.util.Iterator<E> iterator()
Description copied from interface: java.util.Collection
Returns an iterator over the elements in this collection. There are no guarantees concerning the order in which the elements are returned (unless this collection is an instance of some class that provides a guarantee).

Specified by:
iterator in interface java.lang.Iterable<E>
Specified by:
iterator in interface java.util.Collection<E>
Returns:
an Iterator over the elements in this collection

removeAll

public boolean removeAll(java.util.Collection<?> c)
Description copied from interface: java.util.Collection
Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection.

Specified by:
removeAll in interface java.util.Collection<E>
Parameters:
c - collection containing elements to be removed from this collection
Returns:
true if this collection changed as a result of the call
See Also:
Collection.remove(Object), Collection.contains(Object)

retainAll

public boolean retainAll(java.util.Collection<?> c)
Description copied from interface: java.util.Collection
Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

Specified by:
retainAll in interface java.util.Collection<E>
Parameters:
c - collection containing elements to be retained in this collection
Returns:
true if this collection changed as a result of the call
See Also:
Collection.remove(Object), Collection.contains(Object)

size

public int size()
Description copied from interface: java.util.Collection
Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Specified by:
size in interface java.util.Collection<E>
Returns:
the number of elements in this collection

toArray

public java.lang.Object[] toArray()
Description copied from interface: java.util.Collection
Returns an array containing all of the elements in this collection. If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

The returned array will be "safe" in that no references to it are maintained by this collection. (In other words, this method must allocate a new array even if this collection is backed by an array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Specified by:
toArray in interface java.util.Collection<E>
Returns:
an array containing all of the elements in this collection

toArray

public <T> T[] toArray(T[] a)
Description copied from interface: java.util.Collection
Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array. If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection.

If this collection fits in the specified array with room to spare (i.e., the array has more elements than this collection), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of this collection only if the caller knows that this collection does not contain any null elements.)

If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

Like the Collection.toArray() method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose x is a collection known to contain only strings. The following code can be used to dump the collection into a newly allocated array of String:

     String[] y = x.toArray(new String[0]);
Note that toArray(new Object[0]) is identical in function to toArray().

Specified by:
toArray in interface java.util.Collection<E>
Parameters:
a - the array into which the elements of this collection are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
Returns:
an array containing all of the elements in this collection