001/* 002 * Copyright 2013 Alex Kasko (alexkasko.com) 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.alexkasko.unsafe.offheapstruct; 018 019import com.alexkasko.unsafe.offheap.OffHeapDisposableIterable; 020import com.alexkasko.unsafe.offheap.OffHeapDisposableIterator; 021import com.alexkasko.unsafe.offheaplong.OffHeapLongArray; 022import com.alexkasko.unsafe.offheaplong.OffHeapLongComparator; 023import com.alexkasko.unsafe.offheaplong.OffHeapLongSorter; 024 025import java.util.Comparator; 026 027import static com.alexkasko.unsafe.offheap.OffHeapUtils.freeAll; 028 029/** 030 * <p>alexkasko: borrowed from {@code https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/DualPivotQuicksort.java} 031 * and adapted to {@link com.alexkasko.unsafe.offheapstruct.OffHeapStructCollection} to sort it by reference. 032 * without changing element positions in array itself. 033 * 034 * <p>Temporary {@link com.alexkasko.unsafe.offheaplong.OffHeapLongArray} with the same size 035 * as collection itself will be used to hold references. 036 * 037 * <p>This class implements the Dual-Pivot Quicksort algorithm by 038 * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm 039 * offers O(n log(n)) performance on many data sets that cause other 040 * quicksorts to degrade to quadratic performance, and is typically 041 * faster than traditional (one-pivot) Quicksort implementations. 042 * 043 * @author Vladimir Yaroslavskiy 044 * @author Jon Bentley 045 * @author Josh Bloch 046 * 047 * @version 2009.11.29 m765.827.12i 048 */ 049public class OffHeapStructSorterByReference { 050 051 /** 052 * Sorts collection using additional {@link com.alexkasko.unsafe.offheaplong.OffHeapLongArray} with the same size 053 * as collection itself as an array of references (indices) of the collection 054 * 055 * @param a the off-heap struct collection to be sorted 056 * @param comparator structs comparator 057 * @return sorted iterable over the collection 058 * @throws IllegalArgumentException {@code if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())} 059 */ 060 static OffHeapDisposableIterable<byte[]> sortedIterable(OffHeapStructCollection a, Comparator<OffHeapStructAccessor> comparator) { 061 return sortedIterable(a, 0, a.size(), comparator); 062 } 063 064 /** 065 * Sorts collection using additional {@link com.alexkasko.unsafe.offheaplong.OffHeapLongArray} with the same size 066 * as collection itself as an array of references (indices) of the collection 067 * 068 * @param a the off-heap struct collection to be sorted 069 * @param fromIndex the index of the first element, inclusive, to be sorted 070 * @param toIndex the index of the last element, exclusive, to be sorted 071 * @param comparator structs comparator 072 * @return sorted iterable over the collection 073 * @throws IllegalArgumentException {@code if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())} 074 */ 075 static OffHeapDisposableIterable<byte[]> sortedIterable(OffHeapStructCollection a, long fromIndex, 076 long toIndex, Comparator<OffHeapStructAccessor> comparator) { 077 if(null == comparator) throw new IllegalArgumentException("Provided comparator is null"); 078 if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size()) { 079 throw new IllegalArgumentException("Illegal input, collection size: [" + a.size() + "], " + 080 "fromIndex: [" + fromIndex + "], toIndex: [" + toIndex + "]"); 081 } 082 OffHeapLongArray indices = new OffHeapLongArray(toIndex - fromIndex); 083 for (long i = fromIndex; i < toIndex; i++) { 084 indices.set(i, i); 085 } 086 OffHeapLongComparator indexComp = new OffHeapReferenceComparator(a, comparator); 087 OffHeapLongSorter.sort(indices, indexComp); 088 return new ReferenceIterable(a, indices); 089 } 090 091 /** 092 * Comparator wrapper to use with references, not thread-safe 093 */ 094 private static class OffHeapReferenceComparator implements OffHeapLongComparator { 095 private final Comparator<OffHeapStructAccessor> comp; 096 private final OffHeapStructIndexAccessor ac1; 097 private final OffHeapStructIndexAccessor ac2; 098 099 /** 100 * Constructor 101 * 102 * @param data data in sorting 103 * @param comp user provided comparator 104 */ 105 private OffHeapReferenceComparator(OffHeapStructCollection data, Comparator<OffHeapStructAccessor> comp) { 106 this.comp = comp; 107 this.ac1 = new OffHeapStructIndexAccessor(data); 108 this.ac2 = new OffHeapStructIndexAccessor(data); 109 } 110 111 /** 112 * {@inheritDoc} 113 */ 114 @Override 115 public int compare(long l1, long l2) { 116 ac1.setIndex(l1); 117 ac2.setIndex(l2); 118 return comp.compare(ac1, ac2); 119 } 120 } 121 122 /** 123 * Struct's accessor implementation for off-heap stored structs 124 * 125 * @author alexkasko 126 * Date: 9/13/13 127 */ 128 private static class OffHeapStructIndexAccessor implements OffHeapStructAccessor { 129 private final OffHeapStructCollection col; 130 private long index = -1; 131 132 /** 133 * Constructor 134 * 135 * @param col collection to access structs from 136 */ 137 private OffHeapStructIndexAccessor(OffHeapStructCollection col) { 138 this.col = col; 139 } 140 141 /** 142 * {@inheritDoc} 143 */ 144 @Override 145 public int structLength() { 146 return col.structLength(); 147 } 148 149 /** 150 * {@inheritDoc} 151 */ 152 @Override 153 public void get(byte[] buffer) { 154 col.get(index, buffer); 155 } 156 157 /** 158 * {@inheritDoc} 159 */ 160 @Override 161 public void get(int srcPos, byte[] dest, int destPos, int length) { 162 col.get(index, srcPos, dest, destPos, length); 163 } 164 165 /** 166 * {@inheritDoc} 167 */ 168 @Override 169 public byte getByte(int offset) { 170 return col.getByte(index, offset); 171 } 172 173 /** 174 * {@inheritDoc} 175 */ 176 @Override 177 public short getUnsignedByte(int offset) { 178 return col.getUnsignedByte(index, offset); 179 } 180 181 /** 182 * {@inheritDoc} 183 */ 184 @Override 185 public short getShort(int offset) { 186 return col.getShort(index, offset); 187 } 188 189 /** 190 * {@inheritDoc} 191 */ 192 @Override 193 public int getUnsignedShort(int offset) { 194 return col.getUnsignedShort(index, offset); 195 } 196 197 /** 198 * {@inheritDoc} 199 */ 200 @Override 201 public int getInt(int offset) { 202 return col.getInt(index, offset); 203 } 204 205 /** 206 * {@inheritDoc} 207 */ 208 @Override 209 public long getUnsignedInt(int offset) { 210 return col.getUnsignedInt(index, offset); 211 } 212 213 /** 214 * {@inheritDoc} 215 */ 216 @Override 217 public long getLong(int offset) { 218 return col.getLong(index, offset); 219 } 220 221 /** 222 * Sets index value 223 * 224 * @param index index value 225 */ 226 private void setIndex(long index) { 227 this.index = index; 228 } 229 230 /** 231 * {@inheritDoc} 232 */ 233 @Override 234 public String toString() { 235 final StringBuilder sb = new StringBuilder(); 236 sb.append("OffHeapStructIndexAccessor"); 237 sb.append("{col=").append(col); 238 sb.append(", index=").append(index); 239 sb.append('}'); 240 return sb.toString(); 241 } 242 } 243 244 /** 245 * Iterable over the data collection using indices from specified array 246 */ 247 private static class ReferenceIterable implements OffHeapDisposableIterable<byte[]> { 248 private final OffHeapStructCollection data; 249 private final OffHeapLongArray index; 250 251 /** 252 * Constructor 253 * 254 * @param data data to iterate over 255 * @param index sorted index 256 */ 257 private ReferenceIterable(OffHeapStructCollection data, OffHeapLongArray index) { 258 this.data = data; 259 this.index = index; 260 } 261 262 /** 263 * {@inheritDoc} 264 */ 265 @Override 266 public OffHeapDisposableIterator<byte[]> iterator() { 267 return new ReferenceIterator(data, index); 268 } 269 270 /** 271 * {@inheritDoc} 272 */ 273 @Override 274 public void free() { 275 freeAll(data, index); 276 } 277 } 278 279 /** 280 * Iterator returning data elements in the order specified by indices array 281 */ 282 private static class ReferenceIterator implements OffHeapDisposableIterator<byte[]> { 283 private final OffHeapStructCollection data; 284 private final OffHeapLongArray index; 285 private final byte[] buf; 286 private final long size; 287 private long ii = 0; 288 289 /** 290 * Constructor 291 * 292 * @param data data to iterate over 293 * @param index sorted index 294 */ 295 private ReferenceIterator(OffHeapStructCollection data, OffHeapLongArray index) { 296 this.data = data; 297 this.index = index; 298 this.buf = new byte[data.structLength()]; 299 this.size = index.size(); 300 } 301 302 /** 303 * {@inheritDoc} 304 */ 305 @Override 306 public long size() { 307 return index.size(); 308 } 309 310 /** 311 * {@inheritDoc} 312 */ 313 @Override 314 public boolean hasNext() { 315 return ii < size; 316 } 317 318 /** 319 * {@inheritDoc} 320 */ 321 @Override 322 public byte[] next() { 323 long ind = index.get(ii); 324 ii += 1; 325 data.get(ind, buf); 326 return buf; 327 } 328 329 /** 330 * {@inheritDoc} 331 */ 332 @Override 333 public void remove() { 334 throw new UnsupportedOperationException("remove"); 335 } 336 337 /** 338 * {@inheritDoc} 339 */ 340 @Override 341 public void free() { 342 freeAll(data, index); 343 } 344 345 /** 346 * {@inheritDoc} 347 */ 348 @Override 349 public String toString() { 350 final StringBuilder sb = new StringBuilder(); 351 sb.append("ReferenceIterator"); 352 sb.append("{data=").append(data); 353 sb.append(", index=").append(index); 354 sb.append(", ii=").append(ii); 355 sb.append('}'); 356 return sb.toString(); 357 } 358 } 359}