001package com.alexkasko.unsafe.offheapstruct; 002 003import static com.alexkasko.unsafe.offheapstruct.OffHeapStructSorter.INSERTION_SORT_THRESHOLD; 004 005/** 006 * <p>alexkasko: borrowed from {@code https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/DualPivotQuicksort.java} 007 * and adapted to {@link OffHeapStructCollection} with unsigned long keys. 008 * 009 * <p>This class implements the Dual-Pivot Quicksort algorithm by 010 * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm 011 * offers O(n log(n)) performance on many data sets that cause other 012 * quicksorts to degrade to quadratic performance, and is typically 013 * faster than traditional (one-pivot) Quicksort implementations. 014 * 015 * @author Vladimir Yaroslavskiy 016 * @author Jon Bentley 017 * @author Josh Bloch 018 * 019 * @version 2009.11.29 m765.827.12i 020 */ 021class OffHeapStructSorterUnsignedLong { 022 023 /** 024 * Sorts the specified off-heap struct collection into ascending order using unsigned long struct key. 025 * 026 * @param a the off-heap struct collection to be sorted 027 * @param keyOffset long key field offset within stuct bounds 028 */ 029 static void sort(OffHeapStructCollection a, int keyOffset) { 030 sort(a, 0, a.size(), keyOffset); 031 } 032 033 /** 034 * Sorts the specified range of the off-heap struct collection into ascending order using unsigned long struct key. 035 * The range to be sorted extends from the index {@code fromIndex}, inclusive, to 036 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 037 * the range to be sorted is empty (and the call is a no-op). 038 * 039 * @param a the off-heap struct collection to be sorted 040 * @param fromIndex the index of the first element, inclusive, to be sorted 041 * @param toIndex the index of the last element, exclusive, to be sorted 042 * @param keyOffset long sort key field offset within stuct bounds 043 * @throws IllegalArgumentException {@code if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())} 044 */ 045 static void sort(OffHeapStructCollection a, long fromIndex, long toIndex, int keyOffset) { 046 if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size()) { 047 throw new IllegalArgumentException("Illegal input, collection size: [" + a.size() + "], " + 048 "fromIndex: [" + fromIndex + "], toIndex: [" + toIndex + "]"); 049 } 050 int len = a.structLength(); 051 doSort(a, fromIndex, toIndex - 1, keyOffset, new byte[len], new byte[len], new byte[len], new byte[len], new byte[len], 052 new byte[len], new byte[len]); 053 } 054 055 056 /** 057 * Sorts the specified range of the off-heap struct collection into ascending order using unsigned long struct key. 058 * This method differs from the public {@code sort} method in that the 059 * {@code right} index is inclusive, and it does no range checking on 060 * {@code left} or {@code right}. 061 * 062 * @param a the off-heap header-payload collection to be sorted 063 * @param left the index of the first element, inclusive, to be sorted 064 * @param right the index of the last element, inclusive, to be sorted* @param keyOffset 065 * @param keyOffset long sort key field offset within stuct bounds 066 * @param pi temporary buffer for structs 067 * @param pj temporary buffer for structs 068 * @param pe1 temporary buffer for structs 069 * @param pe2 temporary buffer for structs 070 * @param pe3 temporary buffer for structs 071 * @param pe4 temporary buffer for structs 072 * @param pe5 temporary buffer for structs 073 */ 074 private static void doSort(OffHeapStructCollection a, long left, long right, int keyOffset, byte[] pi, byte[] pj, 075 byte[] pe1, byte[] pe2, byte[] pe3, byte[] pe4, byte[] pe5) { 076 // Use insertion sort on tiny arrays 077 if (right - left + 1 < INSERTION_SORT_THRESHOLD) { 078 for (long i = left + 1; i <= right; i++) { 079 long ai = a.getLong(i, keyOffset); 080 a.get(i, pi); 081 long j; 082 for (j = i - 1; j >= left && lt(ai, a.getLong(j, keyOffset)); j--) { 083 a.get(j, pj); 084 a.set(j + 1, pj); 085 } 086 a.set(j + 1, pi); 087 } 088 } else { // Use Dual-Pivot Quicksort on large arrays 089 dualPivotQuicksort(a, left, right, keyOffset, pi, pj, pe1, pe2, pe3, pe4, pe5); 090 } 091 } 092 093 /** 094 * Sorts the specified range of the off-heap struct collection into ascending order by the 095 * Dual-Pivot Quicksort algorithm using unsigned long struct key. 096 * 097 * @param a the off-heap header-payload collection to be sorted 098 * @param left the index of the first element, inclusive, to be sorted 099 * @param right the index of the last element, inclusive, to be sorted 100 * @param keyOffset long sort key field offset within stuct bounds 101 * @param pi temporary buffer for structs 102 * @param pj temporary buffer for structs 103 * @param pe1 temporary buffer for structs 104 * @param pe2 temporary buffer for structs 105 * @param pe3 temporary buffer for structs 106 * @param pe4 temporary buffer for structs 107 * @param pe5 temporary buffer for structs 108 */ 109 private static void dualPivotQuicksort(OffHeapStructCollection a, long left, long right, int keyOffset, byte[] pi, byte[] pj, 110 byte[] pe1, byte[] pe2, byte[] pe3, byte[] pe4, byte[] pe5) { 111 // Compute indices of five evenly spaced elements 112 long sixth = (right - left + 1) / 6; 113 long e1 = left + sixth; 114 long e5 = right - sixth; 115 long e3 = (left + right) >>> 1; // The midpoint 116 long e4 = e3 + sixth; 117 long e2 = e3 - sixth; 118 119 // Sort these elements using a 5-element sorting network 120 long ae1 = a.getLong(e1, keyOffset), ae2 = a.getLong(e2, keyOffset), ae3 = a.getLong(e3, keyOffset), 121 ae4 = a.getLong(e4, keyOffset), ae5 = a.getLong(e5, keyOffset); 122 a.get(e1, pe1); a.get(e2, pe2); a.get(e3, pe3); a.get(e4, pe4); a.get(e5, pe5); 123 124 if (gt(ae1, ae2)) { long t = ae1; byte[] pt = pe1; ae1 = ae2; pe1 = pe2; ae2 = t; pe2 = pt; } 125 if (gt(ae4, ae5)) { long t = ae4; byte[] pt = pe4; ae4 = ae5; pe4 = pe5; ae5 = t; pe5 = pt; } 126 if (gt(ae1, ae3)) { long t = ae1; byte[] pt = pe1; ae1 = ae3; pe1 = pe3; ae3 = t; pe3 = pt; } 127 if (gt(ae2, ae3)) { long t = ae2; byte[] pt = pe2; ae2 = ae3; pe2 = pe3; ae3 = t; pe3 = pt; } 128 if (gt(ae1, ae4)) { long t = ae1; byte[] pt = pe1; ae1 = ae4; pe1 = pe4; ae4 = t; pe4 = pt; } 129 if (gt(ae3, ae4)) { long t = ae3; byte[] pt = pe3; ae3 = ae4; pe3 = pe4; ae4 = t; pe4 = pt; } 130 if (gt(ae2, ae5)) { long t = ae2; byte[] pt = pe2; ae2 = ae5; pe2 = pe5; ae5 = t; pe5 = pt; } 131 if (gt(ae2, ae3)) { long t = ae2; byte[] pt = pe2; ae2 = ae3; pe2 = pe3; ae3 = t; pe3 = pt; } 132 if (gt(ae4, ae5)) { long t = ae4; byte[] pt = pe4; ae4 = ae5; pe4 = pe5; ae5 = t; pe5 = pt; } 133 134 a.set(e1, pe1); a.set(e3, pe3); a.set(e5, pe5); 135 136 /* 137 * Use the second and fourth of the five sorted elements as pivots. 138 * These values are inexpensive approximations of the first and 139 * second terciles of the array. Note that pivot1 <= pivot2. 140 * 141 * The pivots are stored in local variables, and the first and 142 * the last of the elements to be sorted are moved to the locations 143 * formerly occupied by the pivots. When partitioning is complete, 144 * the pivots are swapped back into their final positions, and 145 * excluded from subsequent sorting. 146 */ 147 a.get(left, pe1); 148 long pivot1 = ae2; a.set(e2, pe1); 149 a.get(right, pe1); 150 long pivot2 = ae4; a.set(e4, pe1); 151 152 // Pointers 153 long less = left + 1; // The index of first element of center part 154 long great = right - 1; // The index before first element of right part 155 156 boolean pivotsDiffer = (pivot1 != pivot2); 157 158 if (pivotsDiffer) { 159 /* 160 * Partitioning: 161 * 162 * left part center part right part 163 * +------------------------------------------------------------+ 164 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 165 * +------------------------------------------------------------+ 166 * ^ ^ ^ 167 * | | | 168 * less k great 169 * 170 * Invariants: 171 * 172 * all in (left, less) < pivot1 173 * pivot1 <= all in [less, k) <= pivot2 174 * all in (great, right) > pivot2 175 * 176 * Pointer k is the first index of ?-part 177 */ 178 outer: 179 for (long k = less; k <= great; k++) { 180 long ak = a.getLong(k, keyOffset); 181 a.get(k, pe1); 182 if (lt(ak, pivot1)) { // Move a[k] to left part 183 if (k != less) { 184 a.get(less, pe3); 185 a.set(k, pe3); 186 a.set(less, pe1); 187 } 188 less++; 189 } else if (gt(ak, pivot2)) { // Move a[k] to right part 190 while (gt(a.getLong(great, keyOffset), pivot2)) { 191 if (great-- == k) { 192 break outer; 193 } 194 } 195 if (lt(a.getLong(great, keyOffset), pivot1)) { 196 a.get(less, pe3); 197 a.set(k, pe3); 198 a.get(great, pe3); 199 a.set(less++, pe3); 200 a.set(great--, pe1); 201 } else { // pivot1 <= a[great] <= pivot2 202 a.get(great, pe3); 203 a.set(k, pe3); 204 a.set(great--, pe1); 205 } 206 } 207 } 208 } else { // Pivots are equal 209 /* 210 * Partition degenerates to the traditional 3-way, 211 * or "Dutch National Flag", partition: 212 * 213 * left part center part right part 214 * +----------------------------------------------+ 215 * | < pivot | == pivot | ? | > pivot | 216 * +----------------------------------------------+ 217 * ^ ^ ^ 218 * | | | 219 * less k great 220 * 221 * Invariants: 222 * 223 * all in (left, less) < pivot 224 * all in [less, k) == pivot 225 * all in (great, right) > pivot 226 * 227 * Pointer k is the first index of ?-part 228 */ 229 for (long k = less; k <= great; k++) { 230 long ak = a.getLong(k, keyOffset); 231 a.get(k, pe1); 232 if (ak == pivot1) { 233 continue; 234 } 235 if (lt(ak, pivot1)) { // Move a[k] to left part 236 if (k != less) { 237 a.get(less, pe3); 238 a.set(k, pe3); 239 a.set(less, pe1); 240 } 241 less++; 242 } else { // (a[k] > pivot1) - Move a[k] to right part 243 /* 244 * We know that pivot1 == a[e3] == pivot2. Thus, we know 245 * that great will still be >= k when the following loop 246 * terminates, even though we don't test for it explicitly. 247 * In other words, a[e3] acts as a sentinel for great. 248 */ 249 while (gt(a.getLong(great, keyOffset), pivot1)) { 250 great--; 251 } 252 if (lt(a.getLong(great, keyOffset), pivot1)) { 253 a.get(less, pe3); 254 a.set(k, pe3); 255 a.get(great, pe3); 256 a.set(less++, pe3); 257 a.set(great--, pe1); 258 } else { // a[great] == pivot1 259 a.get(great, pe3); 260 a.set(k, pe3); 261 a.set(great--, pe1); 262 } 263 } 264 } 265 } 266 267 // Swap pivots into their final positions 268 a.get(less - 1, pe1); 269 a.set(left, pe1); a.set(less - 1, pe2); 270 a.get(great + 1, pe1); 271 a.set(right, pe1); a.set(great + 1, pe4); 272 273 // Sort left and right parts recursively, excluding known pivot values 274 doSort(a, left, less - 2, keyOffset, pi, pj, pe1, pe2, pe3, pe4, pe5); 275 doSort(a, great + 2, right, keyOffset, pi, pj, pe1, pe2, pe3, pe4, pe5); 276 277 /* 278 * If pivot1 == pivot2, all elements from center 279 * part are equal and, therefore, already sorted 280 */ 281 if (!pivotsDiffer) { 282 return; 283 } 284 285 /* 286 * If center part is too large (comprises > 2/3 of the array), 287 * swap internal pivot values to ends 288 */ 289 if (less < e1 && great > e5) { 290 while (a.getLong(less, keyOffset) == pivot1) { 291 less++; 292 } 293 while (a.getLong(great, keyOffset) == pivot2) { 294 great--; 295 } 296 297 /* 298 * Partitioning: 299 * 300 * left part center part right part 301 * +----------------------------------------------------------+ 302 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 303 * +----------------------------------------------------------+ 304 * ^ ^ ^ 305 * | | | 306 * less k great 307 * 308 * Invariants: 309 * 310 * all in (*, less) == pivot1 311 * pivot1 < all in [less, k) < pivot2 312 * all in (great, *) == pivot2 313 * 314 * Pointer k is the first index of ?-part 315 */ 316 outer: 317 for (long k = less; k <= great; k++) { 318 long ak = a.getLong(k, keyOffset); 319 a.get(k, pe1); 320 if (ak == pivot2) { // Move a[k] to right part 321 while (a.getLong(great, keyOffset) == pivot2) { 322 if (great-- == k) { 323 break outer; 324 } 325 } 326 if (a.getLong(great, keyOffset) == pivot1) { 327 a.get(less, pe3); 328 a.set(k, pe3); 329 a.get(great, pe3); 330 a.set(less++, pe3); 331 } else { // pivot1 < a[great] < pivot2 332 a.get(great, pe3); 333 a.set(k, pe3); 334 } 335 a.set(great--, pe1); 336 } else if (ak == pivot1) { // Move a[k] to left part 337 a.get(less, pe3); 338 a.set(k, pe3); 339 a.set(less++, pe1); 340 } 341 } 342 } 343 344 // Sort center part recursively, excluding known pivot values 345 doSort(a, less, great, keyOffset, pi, pj, pe1, pe2, pe3, pe4, pe5); 346 } 347 348 private static boolean gt(long l1, long l2) { 349 return compareUnsigned(l1, l2) > 0; 350 } 351 352 private static boolean lt(long l1, long l2) { 353 return compareUnsigned(l1, l2) < 0; 354 } 355 356 private static int compareUnsigned(long l1, long l2) { 357 if (l1 == l2) return 0; 358 if (l1 >= 0 && l2 >= 0 || l1 < 0 && l2 < 0) { 359 if (l1 > l2) return 1; 360 if (l1 < l2) return -1; 361 throw new IllegalStateException(); 362 } else { 363 long i11 = (l1 >>> 32) & 0xffFFffFFL; 364 long i21 = (l2 >>> 32) & 0xffFFffFFL; 365 if (i11 > i21) return 1; 366 if (i11 < i21) return -1; 367 long i12 = l1 & 0xFFFF; 368 long i22 = l2 & 0xFFFF; 369 if (i12 > i22) return 1; 370 if (i12 < i22) return -1; 371 throw new IllegalStateException(); 372 } 373 } 374}