com.alexkasko.unsafe.offheapstruct

Class OffHeapStructSorterInt

java.lang.Object

com.alexkasko.unsafe.offheapstruct.OffHeapStructSorterInt

 class OffHeapStructSorterInt
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 with signed int keys.

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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	OffHeapStructSorterInt.MergeIter Merge-sort iterator over partly sorted collection
private static class	OffHeapStructSorterInt.Worker Worker, sorts part of the collection

Constructor Summary

Constructors

Constructor and Description
OffHeapStructSorterInt()

Method Summary

Methods

Modifier and Type	Method and Description
private static void	doSort(OffHeapStructCollection a, long left, long right, int keyOffset, byte[] pi, byte[] pj, byte[] pe1, byte[] pe2, byte[] pe3, byte[] pe4, byte[] pe5) Sorts the specified range of the off-heap struct collection into ascending order using signed int struct key.
private static void	dualPivotQuicksort(OffHeapStructCollection a, long left, long right, int keyOffset, byte[] pi, byte[] pj, byte[] pe1, byte[] pe2, byte[] pe3, byte[] pe4, byte[] pe5) Sorts the specified range of the off-heap struct collection into ascending order by the Dual-Pivot Quicksort algorithm using signed int struct key.
(package private) static void	sort(OffHeapStructCollection a, int keyOffset) Sorts the specified off-heap struct collection into ascending order using signed int struct key.
(package private) static void	sort(OffHeapStructCollection a, long fromIndex, long toIndex, int keyOffset) Sorts the specified range of the off-heap struct collection into ascending order using signed int struct key.
(package private) static OffHeapDisposableIterator<byte[]>	sortedIterator(ExecutorService executor, int threads, OffHeapStructCollection a, int keyOffset) Partially sorts collection and returns fully sorted iterator over it
(package private) static OffHeapDisposableIterator<byte[]>	sortedIterator(ExecutorService executor, int threads, OffHeapStructCollection a, long fromIndex, long toIndex, int keyOffset) 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

Constructor Detail

OffHeapStructSorterInt

OffHeapStructSorterInt()

Method Detail

sortedIterator

static OffHeapDisposableIterator<byte[]> sortedIterator(ExecutorService executor,
                                               int threads,
                                               OffHeapStructCollection a,
                                               int keyOffset)

Partially sorts collection and returns fully sorted iterator over it

Parameters:

executor - executor service for parallel sorting

threads - number of worker threads to use

a - 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

sortedIterator

static OffHeapDisposableIterator<byte[]> sortedIterator(ExecutorService executor,
                                               int threads,
                                               OffHeapStructCollection a,
                                               long fromIndex,
                                               long toIndex,
                                               int keyOffset)

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

Parameters:

executor - executor service for parallel sorting

threads - number of worker threads to use

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 - key offset

Returns:

sorted iterator over the collection part

Throws:

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

RuntimeException - on worker thread error

sort

static void sort(OffHeapStructCollection a,
        int keyOffset)

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

Parameters:

a - the off-heap struct collection to be sorted

keyOffset - int key field offset within stuct bounds

sort

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

Sorts the specified range of the off-heap struct collection into ascending order using signed 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())

doSort

private static void doSort(OffHeapStructCollection a,
          long left,
          long right,
          int keyOffset,
          byte[] pi,
          byte[] pj,
          byte[] pe1,
          byte[] pe2,
          byte[] pe3,
          byte[] pe4,
          byte[] pe5)

Sorts the specified range of the off-heap struct collection into ascending order using signed int struct key. This method differs from the public sort method in that the right index is inclusive, and it does no range checking on left or right.

Parameters:

a - the off-heap header-payload collection to be sorted

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

right - the index of the last element, inclusive, to be sorted* @param keyOffset

keyOffset - int sort key field offset within stuct bounds

pi - temporary buffer for structs

pj - temporary buffer for structs

pe1 - temporary buffer for structs

pe2 - temporary buffer for structs

pe3 - temporary buffer for structs

pe4 - temporary buffer for structs

pe5 - temporary buffer for structs

dualPivotQuicksort

private static void dualPivotQuicksort(OffHeapStructCollection a,
                      long left,
                      long right,
                      int keyOffset,
                      byte[] pi,
                      byte[] pj,
                      byte[] pe1,
                      byte[] pe2,
                      byte[] pe3,
                      byte[] pe4,
                      byte[] pe5)

Sorts the specified range of the off-heap struct collection into ascending order by the Dual-Pivot Quicksort algorithm using signed int struct key.

Parameters:

a - the off-heap header-payload collection to be sorted

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

right - the index of the last element, inclusive, to be sorted

keyOffset - int sort key field offset within stuct bounds

pi - temporary buffer for structs

pj - temporary buffer for structs

pe1 - temporary buffer for structs

pe2 - temporary buffer for structs

pe3 - temporary buffer for structs

pe4 - temporary buffer for structs

pe5 - temporary buffer for structs