org.mmtk.utility.deque

Class SortSharedDeque

java.lang.Object

org.mmtk.utility.deque.Deque

org.mmtk.utility.deque.SharedDeque

org.mmtk.utility.deque.SortSharedDeque

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

Fields

Modifier and Type	Field and Description
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

Constructor Summary

Constructors

Constructor and Description
SortSharedDeque(String name, RawPageSpace rps, int arity)

Method Summary

Modifier and Type	Method and Description
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 final AddressArray stackBase

Constructor Detail

SortSharedDeque

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

Parameters:

name - human-readable name of ther queue

rps - The space from which the instance should obtain buffers

arity - the queue's arity (number of words per entry)

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