com.alexkasko.unsafe.offheapstruct

Class OffHeapStructSorterUnsignedLong

java.lang.Object

com.alexkasko.unsafe.offheapstruct.OffHeapStructSorterUnsignedLong

 class OffHeapStructSorterUnsignedLong
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 unsigned long 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

Constructor Summary

Constructors

Constructor and Description
OffHeapStructSorterUnsignedLong()

Method Summary

Methods

Modifier and Type	Method and Description
private static int	compareUnsigned(long l1, long l2)
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 unsigned long 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 unsigned long struct key.
private static boolean	gt(long l1, long l2)
private static boolean	lt(long l1, long l2)
(package private) static void	sort(OffHeapStructCollection a, int keyOffset) 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, int keyOffset) Sorts the specified range of the off-heap struct collection into ascending order using unsigned long struct key.

Methods inherited from class java.lang.Object

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

Constructor Detail

OffHeapStructSorterUnsignedLong

OffHeapStructSorterUnsignedLong()

Method Detail

sort

static void sort(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

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 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())

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

keyOffset - long 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 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

keyOffset - long 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

gt

private static boolean gt(long l1,
         long l2)

lt

private static boolean lt(long l1,
         long l2)

compareUnsigned

private static int compareUnsigned(long l1,
                  long l2)