pt.queues
Class FifoLifoQueue<E>

java.lang.Object
  pt.queues.WorkStealingQueue<E>
      pt.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

Field Summary

Fields inherited from class pt.queues.WorkStealingQueue

capacity, chunksize, HALF, localDeques, remainingCapacity, sleep_amount_milli

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.
protected java.util.ArrayList<E>	asList()
void	clear()
boolean	contains(java.lang.Object o)
int	drainTo(java.util.Collection<? super E> c, int maxElements)
E	element()
boolean	isEmpty()
E	poll()
boolean	remove(java.lang.Object o)
void	setThreadPoolIDs(long[] threadPoolIDs) Set the set of threads that will be the worker-threads.
int	size()

Methods inherited from class pt.queues.WorkStealingQueue

addAll, attemptToStealNonRandom, attemptToStealRandom, containsAll, drainTo, iterator, offer, offer, peek, poll, pollLocalQueue, put, remainingCapacity, remove, removeAll, retainAll, take, toArray, toArray

Methods inherited from class java.lang.Object

clone, equals, finalize, 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.

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>

contains

public boolean contains(java.lang.Object o)

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>

drainTo

public int drainTo(java.util.Collection<? super E> c,
                   int maxElements)

Specified by:

drainTo in interface java.util.concurrent.BlockingQueue<E>

Overrides:

drainTo in class WorkStealingQueue<E>

remove

public boolean remove(java.lang.Object o)

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>

element

public E element()

Specified by:

element in interface java.util.Queue<E>

Overrides:

element in class WorkStealingQueue<E>

poll

public E poll()

Specified by:

poll in interface java.util.Queue<E>

Overrides:

poll in class WorkStealingQueue<E>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<E>

Overrides:

clear in class WorkStealingQueue<E>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection<E>

Overrides:

isEmpty in class WorkStealingQueue<E>

size

public int size()

Specified by:

size in interface java.util.Collection<E>

Overrides:

size in class WorkStealingQueue<E>

asList

protected java.util.ArrayList<E> asList()

Overrides:

asList in class WorkStealingQueue<E>