com.alexkasko.unsafe.offheapstruct

Class OffHeapStructSorterWithComparator

java.lang.Object

com.alexkasko.unsafe.offheapstruct.OffHeapStructSorterWithComparator

 class OffHeapStructSorterWithComparator
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 comparator.

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	OffHeapStructSorterWithComparator.MergeIter Merge-sort iterator over partly sorted collection
private static class	OffHeapStructSorterWithComparator.Worker Worker, sorts part of the collection

Constructor Summary

Constructors

Constructor and Description
OffHeapStructSorterWithComparator()

Method Summary

Methods

Modifier and Type	Method and Description
(package private) static void	doSort(OffHeapStructCollection a, long left, long right, OffHeapStructComparator comp, 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 unsigned long struct key.
private static void	dualPivotQuicksort(OffHeapStructCollection a, long left, long right, OffHeapStructComparator comp, 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 unsigned long struct key.
private static void	invokeAndWait(ExecutorService executor, List<OffHeapStructSorterWithComparator.Worker> workers) Helper method to invoke and wait
(package private) static void	sort(OffHeapStructCollection a, Comparator<OffHeapStructAccessor> comparator) Sorts the specified off-heap struct collection into ascending order using unsigned long struct key.
(package private) static void	sort(OffHeapStructCollection a, long fromIndex, long toIndex, Comparator<OffHeapStructAccessor> comparator) Sorts the specified range of the off-heap struct collection into ascending order using unsigned long struct key.
(package private) static OffHeapDisposableIterator<byte[]>	sortedIterator(ExecutorService executor, int threads, OffHeapStructCollection a, Comparator<OffHeapStructAccessor> comparator) 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, Comparator<OffHeapStructAccessor> comparator) 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

OffHeapStructSorterWithComparator

OffHeapStructSorterWithComparator()

Method Detail

sortedIterator

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

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

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

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

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

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

sort

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

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

comparator - structs comparator

sort

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

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

comparator - structs comparator

Throws:

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

doSort

static void doSort(OffHeapStructCollection a,
          long left,
          long right,
          OffHeapStructComparator comp,
          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 unsigned long 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

comp - structs comparator

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,
                      OffHeapStructComparator comp,
                      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 unsigned long 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

comp - structs comparator

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

invokeAndWait

private static void invokeAndWait(ExecutorService executor,
                 List<OffHeapStructSorterWithComparator.Worker> workers)

Helper method to invoke and wait

Parameters:

executor - executor instance

workers - workers list