com.alexkasko.unsafe.offheapstruct

Class OffHeapStructSorter

java.lang.Object

com.alexkasko.unsafe.offheapstruct.OffHeapStructSorter

public class OffHeapStructSorter
extends Object

alexkasko: borrowed from https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/DualPivotQuicksort.java and adapted to OffHeapStructCollection.

This class implements the Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Version:

2009.11.29 m765.827.12i

Author:

Vladimir Yaroslavskiy, Jon Bentley, Josh Bloch

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static int	INSERTION_SORT_THRESHOLD If the length of an collection to be sorted is less than this constant, insertion sort is used in preference to Quicksort.

Constructor Summary

Constructors

Constructor and Description
OffHeapStructSorter()

Method Summary

Methods

Modifier and Type	Method and Description
static void	sort(OffHeapStructCollection collection, Comparator<OffHeapStructAccessor> comparator) Sorts collection using comparator.
static void	sort(OffHeapStructCollection collection, Comparator<OffHeapStructAccessor> comparator, long fromIndex, long toIndex) Sorts collection using comparator.
static void	sortByIntKey(OffHeapStructCollection a, int keyOffset) Sorts the specified off-heap struct collection into ascending order using int struct key.
static void	sortByIntKey(OffHeapStructCollection a, long fromIndex, long toIndex, int keyOffset) Sorts the specified range of the off-heap struct collection into ascending order using int struct key.
static void	sortByLongKey(OffHeapStructCollection a, int keyOffset) Sorts the specified off-heap struct collection into ascending order using long struct key.
static void	sortByLongKey(OffHeapStructCollection a, long fromIndex, long toIndex, int keyOffset) Sorts the specified range of the off-heap struct collection into ascending order using long struct key.
static void	sortByLongKeysParallel(Executor executor, int threads, OffHeapStructCollection a, int key1Offset, int key2Offset) Sorts collection by two long keys.
static void	sortByUnsignedIntKey(OffHeapStructCollection a, int keyOffset) Sorts the specified off-heap struct collection into ascending order using unsigned int struct key.
static void	sortByUnsignedIntKey(OffHeapStructCollection a, long fromIndex, long toIndex, int keyOffset) Sorts the specified range of the off-heap struct collection into ascending order using unsigned int struct key.
static void	sortByUnsignedLongKey(OffHeapStructCollection a, int keyOffset) Sorts the specified off-heap struct collection into ascending order using unsigned long struct key.
static void	sortByUnsignedLongKey(OffHeapStructCollection a, long fromIndex, long toIndex, int keyOffset) Sorts the specified range of the off-heap struct collection into ascending order using unsigned long struct key.
static OffHeapDisposableIterable<byte[]>	sortedByRefIterable(OffHeapStructCollection a, Comparator<OffHeapStructAccessor> comparator) Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection
static OffHeapDisposableIterable<byte[]>	sortedByRefIterable(OffHeapStructCollection a, long fromIndex, long toIndex, Comparator<OffHeapStructAccessor> comparator) Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection
static OffHeapDisposableIterator<byte[]>	sortedIterator(ExecutorService executor, int threadsCount, OffHeapStructCollection collection, Comparator<OffHeapStructAccessor> comparator) Partially sorts collection and returns fully sorted iterator over it
static OffHeapDisposableIterator<byte[]>	sortedIterator(ExecutorService executor, int threadsCount, OffHeapStructCollection collection, Comparator<OffHeapStructAccessor> comparator, long fromIndex, long toIndex) Partially sorts part of the collection and returns fully sorted iterator over it
static OffHeapDisposableIterator<byte[]>	sortedIteratorByIntKey(ExecutorService executor, int threadsCount, OffHeapStructCollection collection, int keyOffset) Partially sorts collection and returns fully sorted iterator over it
static OffHeapDisposableIterator<byte[]>	sortedIteratorByIntKey(ExecutorService executor, int threadsCount, OffHeapStructCollection collection, int keyOffset, long fromIndex, long toIndex) Partially sorts part of the collection and returns fully sorted iterator over it
static OffHeapDisposableIterator<byte[]>	sortedIteratorByLongKey(ExecutorService executor, int threadsCount, OffHeapStructCollection collection, int keyOffset) Partially sorts collection and returns fully sorted iterator over it
static OffHeapDisposableIterator<byte[]>	sortedIteratorByLongKey(ExecutorService executor, int threadsCount, OffHeapStructCollection collection, int keyOffset, long fromIndex, long toIndex) Partially sorts part of the collection and returns fully sorted iterator over it

Methods inherited from class java.lang.Object

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

Field Detail

INSERTION_SORT_THRESHOLD

static final int INSERTION_SORT_THRESHOLD

If the length of an collection to be sorted is less than this constant, insertion sort is used in preference to Quicksort.

See Also:

Constant Field Values

Constructor Detail

OffHeapStructSorter

public OffHeapStructSorter()

Method Detail

sort

public static void sort(OffHeapStructCollection collection,
        Comparator<OffHeapStructAccessor> comparator)

Sorts collection using comparator.

Parameters:

collection - off-heap struct collection

comparator - structs comparator

sort

public static void sort(OffHeapStructCollection collection,
        Comparator<OffHeapStructAccessor> comparator,
        long fromIndex,
        long toIndex)

Sorts collection using comparator.

Parameters:

collection - off-heap struct collection

comparator - structs comparator

fromIndex - start sort collection index

toIndex - end sort collection index

sortedIterator

public static OffHeapDisposableIterator<byte[]> sortedIterator(ExecutorService executor,
                                               int threadsCount,
                                               OffHeapStructCollection collection,
                                               Comparator<OffHeapStructAccessor> comparator)

Partially sorts collection and returns fully sorted iterator over it

Parameters:

executor - executor service for parallel sorting

threadsCount - number of worker threads to use

collection - the off-heap struct collection to be sorted

comparator - structs comparator

Returns:

sorted iterator over the collection

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

RuntimeException - on worker thread error

sortedIterator

public static OffHeapDisposableIterator<byte[]> sortedIterator(ExecutorService executor,
                                               int threadsCount,
                                               OffHeapStructCollection collection,
                                               Comparator<OffHeapStructAccessor> comparator,
                                               long fromIndex,
                                               long toIndex)

Partially sorts part of the collection and returns fully sorted iterator over it

Parameters:

executor - executor service for parallel sorting

threadsCount - number of worker threads to use

collection - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

comparator - structs comparator

Returns:

sorted iterator over the collection part

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

RuntimeException - on worker thread error

sortedIteratorByLongKey

public static OffHeapDisposableIterator<byte[]> sortedIteratorByLongKey(ExecutorService executor,
                                                        int threadsCount,
                                                        OffHeapStructCollection collection,
                                                        int keyOffset)

Partially sorts collection and returns fully sorted iterator over it

Parameters:

executor - executor service for parallel sorting

threadsCount - number of worker threads to use

collection - the off-heap struct collection to be sorted

keyOffset - key offset

Returns:

sorted iterator over the collection

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

RuntimeException - on worker thread error

sortedIteratorByLongKey

public static OffHeapDisposableIterator<byte[]> sortedIteratorByLongKey(ExecutorService executor,
                                                        int threadsCount,
                                                        OffHeapStructCollection collection,
                                                        int keyOffset,
                                                        long fromIndex,
                                                        long toIndex)

Partially sorts part of the collection and returns fully sorted iterator over it

Parameters:

executor - executor service for parallel sorting

threadsCount - number of worker threads to use

collection - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

keyOffset - key offset

Returns:

sorted iterator over the collection part

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

RuntimeException - on worker thread error

sortedIteratorByIntKey

public static OffHeapDisposableIterator<byte[]> sortedIteratorByIntKey(ExecutorService executor,
                                                       int threadsCount,
                                                       OffHeapStructCollection collection,
                                                       int keyOffset)

Partially sorts collection and returns fully sorted iterator over it

Parameters:

executor - executor service for parallel sorting

threadsCount - number of worker threads to use

collection - the off-heap struct collection to be sorted

keyOffset - key offset

Returns:

sorted iterator over the collection

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

RuntimeException - on worker thread error

sortedIteratorByIntKey

public static OffHeapDisposableIterator<byte[]> sortedIteratorByIntKey(ExecutorService executor,
                                                       int threadsCount,
                                                       OffHeapStructCollection collection,
                                                       int keyOffset,
                                                       long fromIndex,
                                                       long toIndex)

Partially sorts part of the collection and returns fully sorted iterator over it

Parameters:

executor - executor service for parallel sorting

threadsCount - number of worker threads to use

collection - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

keyOffset - key offset

Returns:

sorted iterator over the collection part

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

RuntimeException - on worker thread error

sortByLongKey

public static void sortByLongKey(OffHeapStructCollection a,
                 int keyOffset)

Sorts the specified off-heap struct collection into ascending order using long struct key.

Parameters:

a - the off-heap struct collection to be sorted

keyOffset - long key field offset within stuct bounds

sortByLongKey

public static void sortByLongKey(OffHeapStructCollection a,
                 long fromIndex,
                 long toIndex,
                 int keyOffset)

Sorts the specified range of the off-heap struct collection into ascending order using long struct key. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty (and the call is a no-op).

Parameters:

a - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

keyOffset - long sort key field offset within stuct bounds

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

sortByLongKeysParallel

public static void sortByLongKeysParallel(Executor executor,
                          int threads,
                          OffHeapStructCollection a,
                          int key1Offset,
                          int key2Offset)

Sorts collection by two long keys. Second key sorting is done in parallel.

Parameters:

executor - executor for parallel sorting

threads - number of worker threads to use

a - the off-heap struct collection to be sorted

key1Offset - first key offset

key2Offset - second key offset

sortByUnsignedLongKey

public static void sortByUnsignedLongKey(OffHeapStructCollection a,
                         int keyOffset)

Sorts the specified off-heap struct collection into ascending order using unsigned long struct key.

Parameters:

a - the off-heap struct collection to be sorted

keyOffset - long key field offset within stuct bounds

sortByUnsignedLongKey

public static void sortByUnsignedLongKey(OffHeapStructCollection a,
                         long fromIndex,
                         long toIndex,
                         int keyOffset)

Sorts the specified range of the off-heap struct collection into ascending order using unsigned long struct key. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty (and the call is a no-op).

Parameters:

a - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

keyOffset - long sort key field offset within stuct bounds

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

sortByIntKey

public static void sortByIntKey(OffHeapStructCollection a,
                int keyOffset)

Sorts the specified off-heap struct collection into ascending order using int struct key.

Parameters:

a - the off-heap struct collection to be sorted

keyOffset - int key field offset within stuct bounds

sortByIntKey

public static void sortByIntKey(OffHeapStructCollection a,
                long fromIndex,
                long toIndex,
                int keyOffset)

Sorts the specified range of the off-heap struct collection into ascending order using int struct key. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty (and the call is a no-op).

Parameters:

a - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

keyOffset - int sort key field offset within stuct bounds

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

sortByUnsignedIntKey

public static void sortByUnsignedIntKey(OffHeapStructCollection a,
                        int keyOffset)

Sorts the specified off-heap struct collection into ascending order using unsigned int struct key.

Parameters:

a - the off-heap struct collection to be sorted

keyOffset - int key field offset within stuct bounds

sortByUnsignedIntKey

public static void sortByUnsignedIntKey(OffHeapStructCollection a,
                        long fromIndex,
                        long toIndex,
                        int keyOffset)

Sorts the specified range of the off-heap struct collection into ascending order using unsigned int struct key. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty (and the call is a no-op).

Parameters:

a - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

keyOffset - int sort key field offset within stuct bounds

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

sortedByRefIterable

public static OffHeapDisposableIterable<byte[]> sortedByRefIterable(OffHeapStructCollection a,
                                                    Comparator<OffHeapStructAccessor> comparator)

Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection

Parameters:

a - the off-heap struct collection to be sorted

comparator - structs comparator

Returns:

sorted iterable over the collection

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())

sortedByRefIterable

public static OffHeapDisposableIterable<byte[]> sortedByRefIterable(OffHeapStructCollection a,
                                                    long fromIndex,
                                                    long toIndex,
                                                    Comparator<OffHeapStructAccessor> comparator)

Sorts collection using additional OffHeapLongArray with the same size as collection itself as an array of references (indices) of the collection

Parameters:

a - the off-heap struct collection to be sorted

fromIndex - the index of the first element, inclusive, to be sorted

toIndex - the index of the last element, exclusive, to be sorted

comparator - structs comparator

Returns:

sorted iterable over the collection

Throws:

IllegalArgumentException - if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())