paratask.queues
Class FifoLifoQueue<E>

java.lang.Object
  extended by paratask.queues.WorkStealingQueue<E>
      extended by paratask.queues.FifoLifoQueue<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>

public class FifoLifoQueue<E>
extends WorkStealingQueue<E>

A mixed-schedule queue. Elements may be added using either a FIFO policy (addGlobal(Object)), or a LIFO policy (addLocal(Object)).

If only addLocal(Object) is used, then this collection will essentially behave like a WorkStealingQueue.

If only addGlobal(Object) is used, then this collection will essentially behave like a standard FIFO queue.

Having the ability to add both locally and globally allows for increased flexibility. For example, ParaTask uses this queue to ensure fairness for non-recursive tasks, while also ensuring that recursive tasks are handled.

The "head of queue" in the context of a FifoLifoQueue refers to the element according to this schedule. There are three possibilities where the "head of queue" element might come from. First, an element is attempted to be taken from the thread's local queue. If this fails, then an element is removed from the shared global queue. If this fails, an element is stolen from another thread's local queue.

Author:
Nasser Giacaman, Oliver Sinnen

Constructor Summary
FifoLifoQueue()
          Creates an empty queue with maximum capacity and chunksize of 1.
FifoLifoQueue(java.util.Collection<? extends E> c, int chunksize)
          Creates a queue containing the specified collection with the specified chunksize.
FifoLifoQueue(int capacity, int chunksize)
          Creates an empty queue with the specified chunksize and capacity.
FifoLifoQueue(long[] threadPoolIDs)
          Create an empty queue with unlimited capacity and chunksize of 1.
 
Method Summary
 boolean add(E e)
          Deprecated. If the calling thread already has a local queue, or the calling thread is registered as a worker thread, then this call is equivalent to addLocal(Object). Otherwise, the call is equivalent to addGlobal(Object). It is therefore recommended to explicitly use addLocal(Object) or addGlobal(Object) to ensure the correct intention is performed.
 boolean addGlobal(E e)
          Add the specified element globally.
 boolean addLocal(E e)
          Add the specified element locally.
 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.
 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.
 E poll()
          Retrieves and removes the head of this queue, or returns null if this queue is empty.
 boolean remove(java.lang.Object o)
          Removes a single instance of the specified element from this queue, if it is present.
 void setThreadPoolIDs(long[] threadPoolIDs)
          Set the set of threads that will be the worker-threads.
 int size()
          Returns the number of elements in this collection.
 
Methods inherited from class paratask.queues.WorkStealingQueue
addAll, containsAll, drainTo, iterator, offer, offer, peek, poll, put, remainingCapacity, remove, removeAll, retainAll, take, toArray, toArray
 
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

FifoLifoQueue

public FifoLifoQueue()
Creates an empty queue with maximum capacity and chunksize of 1.


FifoLifoQueue

public FifoLifoQueue(int capacity,
                     int chunksize)
Creates an empty queue with the specified chunksize and capacity.

Parameters:
capacity -
chunksize -

FifoLifoQueue

public FifoLifoQueue(java.util.Collection<? extends E> c,
                     int chunksize)
Creates a queue containing the specified collection with the specified chunksize. Capacity is unlimited.

Parameters:
c -
chunksize -

FifoLifoQueue

public FifoLifoQueue(long[] threadPoolIDs)
Create an empty queue with unlimited capacity and chunksize of 1. If planning to use this collection for a thread-pool implementation where a special set of threads are to be considered as worker-threads, then specify them here, or using setThreadPoolIDs() if using another constructor. In this case, those "special" threads will have their elements added locally when using add().

Parameters:
threadPoolIDs -
See Also:
setThreadPoolIDs(long[])
Method Detail

setThreadPoolIDs

public void setThreadPoolIDs(long[] threadPoolIDs)
Set the set of threads that will be the worker-threads. When elements are added using add(E), those elements will be added locally.

Parameters:
threadPoolIDs -

addLocal

public boolean addLocal(E e)
Add the specified element locally. The element will be executed using a work-stealing LIFO schedule.

Parameters:
e - the element to add
Returns:
true (as specified by Collection.add(E))

addGlobal

public boolean addGlobal(E e)
Add the specified element globally. The element will be executed using a work-sharing FIFO schedule.

Parameters:
e - the element to add
Returns:
true (as specified by Collection.add(E))

add

public boolean add(E e)
Deprecated. If the calling thread already has a local queue, or the calling thread is registered as a worker thread, then this call is equivalent to addLocal(Object). Otherwise, the call is equivalent to addGlobal(Object). It is therefore recommended to explicitly use addLocal(Object) or addGlobal(Object) to ensure the correct intention is performed.

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>
Overrides:
add in class WorkStealingQueue<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>
Overrides:
contains in class WorkStealingQueue<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,
                   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>
Overrides:
drainTo in class WorkStealingQueue<E>
Parameters:
c - the collection to transfer elements into
maxElements - the maximum number of elements to transfer
Returns:
the number of elements transferred

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>
Overrides:
remove in class WorkStealingQueue<E>
Parameters:
o - element to be removed from this queue, if present
Returns:
true if this queue changed as a result of the call

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>
Overrides:
element in class WorkStealingQueue<E>
Returns:
the head of this queue

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>
Overrides:
poll in class WorkStealingQueue<E>
Returns:
the head of this queue, or null if this queue is empty

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>
Overrides:
clear in class WorkStealingQueue<E>

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>
Overrides:
isEmpty in class WorkStealingQueue<E>
Returns:
true if this collection contains no elements

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>
Overrides:
size in class WorkStealingQueue<E>
Returns:
the number of elements in this collection