org.mmtk.utility.deque

Class LocalQueue

java.lang.Object

org.mmtk.utility.deque.Deque

org.mmtk.utility.deque.LocalSSB

org.mmtk.utility.deque.LocalQueue

Direct Known Subclasses:

LocalDeque, TraceBuffer

class LocalQueue
extends LocalSSB

This class implements a local (unsynchronized) queue. A queue is strictly FIFO.

Each instance stores word-sized values into a local buffer. When the buffer is full, or if the flushLocal() method is called, the buffer enqueued at the tail of a SharedDeque. The implementation is intended to be as efficient as possible, in time and space, and is the basis for the TraceBuffer used by heap trace generation. Each instance adds a single field to those inherited from the SSB: a bump pointer. Preconditions: Buffers are always aligned on buffer-size address boundaries.

Invariants: Buffers are filled such that tuples (of the specified arity) are packed to the low end of the buffer. Thus buffer underflows will always arise when then cursor is buffer-size aligned.

Field Summary

Fields

Modifier and Type	Field and Description
protected Address	head the start of the buffer

Fields inherited from class org.mmtk.utility.deque.LocalSSB

queue, tail, tailBufferEnd

Fields inherited from class org.mmtk.utility.deque.Deque

BUFFER_MASK, BUFFER_SIZE, HEAD_INITIAL_VALUE, LOG_PAGES_PER_BUFFER, META_DATA_SIZE, NEXT_FIELD_OFFSET, PAGES_PER_BUFFER, TAIL_INITIAL_VALUE, USABLE_BUFFER_BYTES

Constructor Summary

Constructors

Constructor and Description
LocalQueue(SharedDeque queue) Constructor

Method Summary

Modifier and Type	Method and Description
protected boolean	checkDequeue(int arity) Check whether there are values in the buffer for a pending dequeue.
private boolean	dequeueUnderflow(int arity) There are not sufficient entries in the head buffer for a pending dequeue.
protected boolean	headStarved(int arity) The head is empty (or null), and the shared queue has no buffers available.
void	resetLocal() Reset the local buffer (throwing away any local entries).
protected Address	uncheckedDequeue() Dequeue a value from the buffer.

Methods inherited from class org.mmtk.utility.deque.LocalSSB

bufferSentinel, checkTailInsert, flushLocal, isFlushed, normalizeTail, reset, uncheckedTailInsert

Methods inherited from class org.mmtk.utility.deque.Deque

bufferEnd, bufferFirst, bufferLast, bufferLast, bufferLastOffset, bufferOffset, bufferStart

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

head

protected Address head

the start of the buffer

Constructor Detail

LocalQueue

LocalQueue(SharedDeque queue)

Constructor

Parameters:

queue - The shared queue to which this local ssb will append its buffers (when full or flushed).

Method Detail

resetLocal

public void resetLocal()

Description copied from class: LocalSSB

Reset the local buffer (throwing away any local entries).

Overrides:

resetLocal in class LocalSSB

checkDequeue

protected final boolean checkDequeue(int arity)

Check whether there are values in the buffer for a pending dequeue. If there is not data, grab the first buffer on the shared queue (after freeing the buffer).

Parameters:

arity - The arity of the values stored in this queue: the buffer must contain enough space for this many words.

Returns:

whether there are values available for a dequeue

uncheckedDequeue

protected final Address uncheckedDequeue()

Dequeue a value from the buffer. This is unchecked. The caller must first call checkDequeue() to ensure the buffer has and entry to be removed.

Returns:

The first entry on the queue.

headStarved

protected final boolean headStarved(int arity)

The head is empty (or null), and the shared queue has no buffers available. If the tail has sufficient entries, consume the tail. Otherwise try wait on the global queue until either all other clients of the queue reach exhaustion or a buffer becomes available.

Parameters:

arity - The arity of this buffer

Returns:

True if the consumer has eaten all the entries

dequeueUnderflow

private boolean dequeueUnderflow(int arity)

There are not sufficient entries in the head buffer for a pending dequeue. Acquire a new head buffer. If the shared queue has no buffers available, consume the tail if necessary. Return false if entries cannot be acquired.

Parameters:

arity - The arity of this buffer (used for sanity test only).

Returns:

True if there the head buffer has been successfully replenished.