Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.mmtk.utility.deque
Class LocalQueue

java.lang.Object
  extended by org.mmtk.utility.deque.Deque
      extended by org.mmtk.utility.deque.LocalSSB
          extended by org.mmtk.utility.deque.LocalQueue
All Implemented Interfaces:
Constants
Direct Known Subclasses:
LocalDeque, TraceBuffer
 class LocalQueue
extends LocalSSB
implements Constants

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
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
 
Fields inherited from interface org.mmtk.utility.Constants
ALIGNMENT_VALUE, ARRAY_ELEMENT, BITS_IN_ADDRESS, BITS_IN_BYTE, BITS_IN_CHAR, BITS_IN_INT, BITS_IN_PAGE, BITS_IN_SHORT, BITS_IN_WORD, BYTES_IN_ADDRESS, BYTES_IN_BYTE, BYTES_IN_CHAR, BYTES_IN_INT, BYTES_IN_KBYTE, BYTES_IN_MBYTE, BYTES_IN_PAGE, BYTES_IN_SHORT, BYTES_IN_WORD, CARD_MASK, CARD_META_PAGES_PER_REGION, INSTANCE_FIELD, LOG_BITS_IN_ADDRESS, LOG_BITS_IN_BYTE, LOG_BITS_IN_CHAR, LOG_BITS_IN_INT, LOG_BITS_IN_PAGE, LOG_BITS_IN_SHORT, LOG_BITS_IN_WORD, LOG_BYTES_IN_ADDRESS, LOG_BYTES_IN_ADDRESS_SPACE, LOG_BYTES_IN_BYTE, LOG_BYTES_IN_CHAR, LOG_BYTES_IN_INT, LOG_BYTES_IN_KBYTE, LOG_BYTES_IN_MBYTE, LOG_BYTES_IN_PAGE, LOG_BYTES_IN_SHORT, LOG_BYTES_IN_WORD, LOG_CARD_BYTES, LOG_CARD_GRAIN, LOG_CARD_META_BYTES, LOG_CARD_META_PAGES, LOG_CARD_META_SIZE, LOG_CARD_UNITS, LOG_MIN_ALIGNMENT, MAX_ALIGNMENT, MAX_BYTES_PADDING, MAX_INT, MIN_ALIGNMENT, MIN_INT, SUPPORT_CARD_SCANNING
 
Constructor Summary
LocalQueue(SharedDeque queue)
          Constructor
 
Method Summary
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.

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.
Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD