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 SortSharedDeque

java.lang.Object
  extended by org.mmtk.utility.deque.Deque
      extended by org.mmtk.utility.deque.SharedDeque
          extended by org.mmtk.utility.deque.SortSharedDeque
All Implemented Interfaces:
Constants
Direct Known Subclasses:
SortTODSharedDeque
public abstract class SortSharedDeque
extends SharedDeque

This supports unsynchronized enqueuing and dequeuing of buffers for shared use. The data can be added to and removed from either end of the deque. This class is based upon the SharedQueue class. The sorting routines were modified from code written by Narendran Sachindran and Matthew Hertz for GCTk.

Field Summary
private static int BYTES_PUSHED
           
private static Offset INSERTION_SORT_LIMIT
           
private static Word mask1
           
private static Word mask16
           
private static Word mask2
           
private static Word mask4
           
private static Word mask8
           
private static int MAX_STACK_SIZE
           
private  AddressArray stackBase
           
private  int stackLoc
           
 
Fields inherited from class org.mmtk.utility.deque.SharedDeque
head, tail
 
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
SortSharedDeque(String name, RawPageSpace rps, int arity)
          Constructor
 
Method Summary
private  void checkIfSorted()
          Debug routine, used to check if the object buffer is sorted correctly in decreasing final reference deletion time
private static Word getBitMask(Word addr)
          Find the highest bit that is set in a longword and return a mask with only that bit set.
protected abstract  Word getKey(Address obj)
          Return the sorting key for the object passed as a parameter.
private  void initStack()
           
private  void insertionSort(Address begin, Address end)
          Perform insertion sort within an intra-block address range.
private  void partition(Address startAddr, Address startLinkAddr, Address endAddr, Address endLinkAddr, Word bitMask)
          Partition the slots in an address range based on the value in a particular bit.
private  Address popStack()
          Pop an address from the stack
private  void pushOnStack(Address val)
          Push an address on to the stack
 void sort()
          Sort objects using radix exchange sort.
 
Methods inherited from class org.mmtk.utility.deque.SharedDeque
alloc, assertExhausted, clearDeque, dequeue, dequeue, dequeueAndWait, dequeueAndWait, enqueue, enqueuedPages, free, getArity, getNext, getPrev, prepare, prepareNonBlocking, reset
 
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

BYTES_PUSHED

private static final int BYTES_PUSHED

MAX_STACK_SIZE

private static final int MAX_STACK_SIZE

INSERTION_SORT_LIMIT

private static final Offset INSERTION_SORT_LIMIT

mask16

private static final Word mask16

mask8

private static final Word mask8

mask4

private static final Word mask4

mask2

private static final Word mask2

mask1

private static final Word mask1

stackLoc

private int stackLoc

stackBase

private AddressArray stackBase
Constructor Detail

SortSharedDeque

public SortSharedDeque(String name,
                       RawPageSpace rps,
                       int arity)
Constructor

Parameters:
rps - The space from which the instance should obtain buffers.
Method Detail

getKey

protected abstract Word getKey(Address obj)
Return the sorting key for the object passed as a parameter.

Parameters:
obj - The address of the object whose key is wanted
Returns:
The value of the sorting key for this object

getBitMask

private static Word getBitMask(Word addr)
Find the highest bit that is set in a longword and return a mask with only that bit set.

Parameters:
addr - Value for which the mask needs to be found
Returns:
The highest bit set in the parameter

insertionSort

private void insertionSort(Address begin,
                           Address end)
Perform insertion sort within an intra-block address range.

Parameters:
begin - Start address of the range to be sorted
end - End address of the range to be sorted

sort

public void sort()
Sort objects using radix exchange sort. An explicit stack is maintained to avoid using recursion.

partition

private void partition(Address startAddr,
                       Address startLinkAddr,
                       Address endAddr,
                       Address endLinkAddr,
                       Word bitMask)
Partition the slots in an address range based on the value in a particular bit. Place the start & end addresses of the two partitions & a bitmask per partition (which indicates the highest bit position at which the max & min of a partition differ) on the stack. This works just like the partition in quick sort, except that a bit value is being compared here

Parameters:
startAddr - The start address of the range to be sorted
startLinkAddr - The address where the start block has its next field
endAddr - The end address of the range to be sorted
endLinkAddr - The address where the end block has its next field
bitMask - The mask in which the bit to be commpared is set

initStack

private void initStack()

pushOnStack

private void pushOnStack(Address val)
Push an address on to the stack

Parameters:
val - The address to be pushed

popStack

private Address popStack()
Pop an address from the stack

Returns:
The address at the top of the stack, or 0 if stack is empty

checkIfSorted

private void checkIfSorted()
Debug routine, used to check if the object buffer is sorted correctly in decreasing final reference deletion time

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