1 /* 2 * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 // When the platform supports STL, the functions are implemented using a 12 // templated spreadsort algorithm (http://sourceforge.net/projects/spreadsort/), 13 // part of the Boost C++ library collection. Otherwise, the C standard library's 14 // qsort() will be used. 15 16 #include "webrtc/system_wrappers/include/sort.h" 17 18 #include <assert.h> 19 #include <string.h> // memcpy 20 21 #include <new> // nothrow new 22 23 #ifdef NO_STL 24 #include <stdlib.h> // qsort 25 #else 26 #include <algorithm> // std::sort 27 #include <vector> 28 29 // TODO(ajm) upgrade to spreadsort v2. 30 #include "webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp" 31 #endif 32 33 #ifdef NO_STL 34 #define COMPARE_DEREFERENCED(XT, YT) \ 35 do { \ 36 if ((XT) > (YT)) { \ 37 return 1; \ 38 } \ 39 else if ((XT) < (YT)) { \ 40 return -1; \ 41 } \ 42 return 0; \ 43 } while(0) 44 45 #define COMPARE_FOR_QSORT(X, Y, TYPE) \ 46 do { \ 47 TYPE xT = static_cast<TYPE>(*static_cast<const TYPE*>(X)); \ 48 TYPE yT = static_cast<TYPE>(*static_cast<const TYPE*>(Y)); \ 49 COMPARE_DEREFERENCED(xT, yT); \ 50 } while(0) 51 52 #define COMPARE_KEY_FOR_QSORT(SORT_KEY_X, SORT_KEY_Y, TYPE) \ 53 do { \ 54 TYPE xT = static_cast<TYPE>( \ 55 *static_cast<TYPE*>(static_cast<const SortKey*>(SORT_KEY_X)->key_)); \ 56 TYPE yT = static_cast<TYPE>( \ 57 *static_cast<TYPE*>(static_cast<const SortKey*>(SORT_KEY_Y)->key_)); \ 58 COMPARE_DEREFERENCED(xT, yT); \ 59 } while(0) 60 61 #define KEY_QSORT(SORT_KEY, KEY, NUM_OF_ELEMENTS, KEY_TYPE, COMPARE_FUNC) \ 62 do { \ 63 KEY_TYPE* key_type = (KEY_TYPE*)(key); \ 64 for (uint32_t i = 0; i < (NUM_OF_ELEMENTS); ++i) { \ 65 ptr_sort_key[i].key_ = &key_type[i]; \ 66 ptr_sort_key[i].index_ = i; \ 67 } \ 68 qsort((SORT_KEY), (NUM_OF_ELEMENTS), sizeof(SortKey), (COMPARE_FUNC)); \ 69 } while(0) 70 #endif 71 72 namespace webrtc { 73 74 #ifdef NO_STL 75 struct SortKey { 76 void* key_; 77 uint32_t index_; 78 }; 79 #else 80 template<typename KeyType> 81 struct SortKey { 82 KeyType key_; 83 uint32_t index_; 84 }; 85 #endif 86 87 namespace { // Unnamed namespace provides internal linkage. 88 89 #ifdef NO_STL 90 int CompareWord8(const void* x, const void* y) { 91 COMPARE_FOR_QSORT(x, y, int8_t); 92 } 93 94 int CompareUWord8(const void* x, const void* y) { 95 COMPARE_FOR_QSORT(x, y, uint8_t); 96 } 97 98 int CompareWord16(const void* x, const void* y) { 99 COMPARE_FOR_QSORT(x, y, int16_t); 100 } 101 102 int CompareUWord16(const void* x, const void* y) { 103 COMPARE_FOR_QSORT(x, y, uint16_t); 104 } 105 106 int CompareWord32(const void* x, const void* y) { 107 COMPARE_FOR_QSORT(x, y, int32_t); 108 } 109 110 int CompareUWord32(const void* x, const void* y) { 111 COMPARE_FOR_QSORT(x, y, uint32_t); 112 } 113 114 int CompareWord64(const void* x, const void* y) { 115 COMPARE_FOR_QSORT(x, y, int64_t); 116 } 117 118 int CompareUWord64(const void* x, const void* y) { 119 COMPARE_FOR_QSORT(x, y, uint64_t); 120 } 121 122 int CompareFloat32(const void* x, const void* y) { 123 COMPARE_FOR_QSORT(x, y, float); 124 } 125 126 int CompareFloat64(const void* x, const void* y) { 127 COMPARE_FOR_QSORT(x, y, double); 128 } 129 130 int CompareKeyWord8(const void* sort_key_x, const void* sort_key_y) { 131 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int8_t); 132 } 133 134 int CompareKeyUWord8(const void* sort_key_x, const void* sort_key_y) { 135 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint8_t); 136 } 137 138 int CompareKeyWord16(const void* sort_key_x, const void* sort_key_y) { 139 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int16_t); 140 } 141 142 int CompareKeyUWord16(const void* sort_key_x, const void* sort_key_y) { 143 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint16_t); 144 } 145 146 int CompareKeyWord32(const void* sort_key_x, const void* sort_key_y) { 147 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int32_t); 148 } 149 150 int CompareKeyUWord32(const void* sort_key_x, const void* sort_key_y) { 151 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint32_t); 152 } 153 154 int CompareKeyWord64(const void* sort_key_x, const void* sort_key_y) { 155 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int64_t); 156 } 157 158 int CompareKeyUWord64(const void* sort_key_x, const void* sort_key_y) { 159 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint64_t); 160 } 161 162 int CompareKeyFloat32(const void* sort_key_x, const void* sort_key_y) { 163 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, float); 164 } 165 166 int CompareKeyFloat64(const void* sort_key_x, const void* sort_key_y) { 167 COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, double); 168 } 169 #else 170 template <typename KeyType> 171 struct KeyLessThan { 172 bool operator()(const SortKey<KeyType>& sort_key_x, 173 const SortKey<KeyType>& sort_key_y) const { 174 return sort_key_x.key_ < sort_key_y.key_; 175 } 176 }; 177 178 template <typename KeyType> 179 struct KeyRightShift { 180 KeyType operator()(const SortKey<KeyType>& sort_key, 181 const unsigned offset) const { 182 return sort_key.key_ >> offset; 183 } 184 }; 185 186 template <typename DataType> 187 inline void IntegerSort(void* data, uint32_t num_of_elements) { 188 DataType* data_type = static_cast<DataType*>(data); 189 boost::integer_sort(data_type, data_type + num_of_elements); 190 } 191 192 template <typename DataType, typename IntegerType> 193 inline void FloatSort(void* data, uint32_t num_of_elements) { 194 DataType* data_type = static_cast<DataType*>(data); 195 IntegerType c_val = 0; 196 boost::float_sort_cast(data_type, data_type + num_of_elements, c_val); 197 } 198 199 template <typename DataType> 200 inline void StdSort(void* data, uint32_t num_of_elements) { 201 DataType* data_type = static_cast<DataType*>(data); 202 std::sort(data_type, data_type + num_of_elements); 203 } 204 205 template<typename KeyType> 206 inline int32_t SetupKeySort(void* key, 207 SortKey<KeyType>*& ptr_sort_key, 208 uint32_t num_of_elements) { 209 ptr_sort_key = new(std::nothrow) SortKey<KeyType>[num_of_elements]; 210 if (ptr_sort_key == NULL) { 211 return -1; 212 } 213 214 KeyType* key_type = static_cast<KeyType*>(key); 215 for (uint32_t i = 0; i < num_of_elements; i++) { 216 ptr_sort_key[i].key_ = key_type[i]; 217 ptr_sort_key[i].index_ = i; 218 } 219 220 return 0; 221 } 222 223 template<typename KeyType> 224 inline int32_t TeardownKeySort(void* data, 225 SortKey<KeyType>* ptr_sort_key, 226 uint32_t num_of_elements, 227 uint32_t size_of_element) { 228 uint8_t* ptr_data = static_cast<uint8_t*>(data); 229 uint8_t* ptr_data_sorted = 230 new(std::nothrow) uint8_t[num_of_elements * size_of_element]; 231 if (ptr_data_sorted == NULL) { 232 return -1; 233 } 234 235 for (uint32_t i = 0; i < num_of_elements; i++) { 236 memcpy(ptr_data_sorted + i * size_of_element, ptr_data + 237 ptr_sort_key[i].index_ * size_of_element, size_of_element); 238 } 239 memcpy(ptr_data, ptr_data_sorted, num_of_elements * size_of_element); 240 delete[] ptr_sort_key; 241 delete[] ptr_data_sorted; 242 return 0; 243 } 244 245 template<typename KeyType> 246 inline int32_t IntegerKeySort(void* data, void* key, 247 uint32_t num_of_elements, 248 uint32_t size_of_element) { 249 SortKey<KeyType>* ptr_sort_key; 250 if (SetupKeySort<KeyType>(key, ptr_sort_key, num_of_elements) != 0) { 251 return -1; 252 } 253 254 boost::integer_sort(ptr_sort_key, ptr_sort_key + num_of_elements, 255 KeyRightShift<KeyType>(), KeyLessThan<KeyType>()); 256 257 if (TeardownKeySort<KeyType>(data, ptr_sort_key, num_of_elements, 258 size_of_element) != 0) { 259 return -1; 260 } 261 262 return 0; 263 } 264 265 template<typename KeyType> 266 inline int32_t StdKeySort(void* data, void* key, 267 uint32_t num_of_elements, 268 uint32_t size_of_element) { 269 SortKey<KeyType>* ptr_sort_key; 270 if (SetupKeySort<KeyType>(key, ptr_sort_key, num_of_elements) != 0) { 271 return -1; 272 } 273 274 std::sort(ptr_sort_key, ptr_sort_key + num_of_elements, 275 KeyLessThan<KeyType>()); 276 277 if (TeardownKeySort<KeyType>(data, ptr_sort_key, num_of_elements, 278 size_of_element) != 0) { 279 return -1; 280 } 281 282 return 0; 283 } 284 #endif 285 } 286 287 int32_t Sort(void* data, uint32_t num_of_elements, Type type) { 288 if (data == NULL) { 289 return -1; 290 } 291 292 #ifdef NO_STL 293 switch (type) { 294 case TYPE_Word8: 295 qsort(data, num_of_elements, sizeof(int8_t), CompareWord8); 296 break; 297 case TYPE_UWord8: 298 qsort(data, num_of_elements, sizeof(uint8_t), CompareUWord8); 299 break; 300 case TYPE_Word16: 301 qsort(data, num_of_elements, sizeof(int16_t), CompareWord16); 302 break; 303 case TYPE_UWord16: 304 qsort(data, num_of_elements, sizeof(uint16_t), CompareUWord16); 305 break; 306 case TYPE_Word32: 307 qsort(data, num_of_elements, sizeof(int32_t), CompareWord32); 308 break; 309 case TYPE_UWord32: 310 qsort(data, num_of_elements, sizeof(uint32_t), CompareUWord32); 311 break; 312 case TYPE_Word64: 313 qsort(data, num_of_elements, sizeof(int64_t), CompareWord64); 314 break; 315 case TYPE_UWord64: 316 qsort(data, num_of_elements, sizeof(uint64_t), CompareUWord64); 317 break; 318 case TYPE_Float32: 319 qsort(data, num_of_elements, sizeof(float), CompareFloat32); 320 break; 321 case TYPE_Float64: 322 qsort(data, num_of_elements, sizeof(double), CompareFloat64); 323 break; 324 default: 325 return -1; 326 } 327 #else 328 // Fall back to std::sort for 64-bit types and floats due to compiler 329 // warnings and VS 2003 build crashes respectively with spreadsort. 330 switch (type) { 331 case TYPE_Word8: 332 IntegerSort<int8_t>(data, num_of_elements); 333 break; 334 case TYPE_UWord8: 335 IntegerSort<uint8_t>(data, num_of_elements); 336 break; 337 case TYPE_Word16: 338 IntegerSort<int16_t>(data, num_of_elements); 339 break; 340 case TYPE_UWord16: 341 IntegerSort<uint16_t>(data, num_of_elements); 342 break; 343 case TYPE_Word32: 344 IntegerSort<int32_t>(data, num_of_elements); 345 break; 346 case TYPE_UWord32: 347 IntegerSort<uint32_t>(data, num_of_elements); 348 break; 349 case TYPE_Word64: 350 StdSort<int64_t>(data, num_of_elements); 351 break; 352 case TYPE_UWord64: 353 StdSort<uint64_t>(data, num_of_elements); 354 break; 355 case TYPE_Float32: 356 StdSort<float>(data, num_of_elements); 357 break; 358 case TYPE_Float64: 359 StdSort<double>(data, num_of_elements); 360 break; 361 } 362 #endif 363 return 0; 364 } 365 366 int32_t KeySort(void* data, void* key, uint32_t num_of_elements, 367 uint32_t size_of_element, Type key_type) { 368 if (data == NULL) { 369 return -1; 370 } 371 372 if (key == NULL) { 373 return -1; 374 } 375 376 if ((uint64_t)num_of_elements * size_of_element > 0xffffffff) { 377 return -1; 378 } 379 380 #ifdef NO_STL 381 SortKey* ptr_sort_key = new(std::nothrow) SortKey[num_of_elements]; 382 if (ptr_sort_key == NULL) { 383 return -1; 384 } 385 386 switch (key_type) { 387 case TYPE_Word8: 388 KEY_QSORT(ptr_sort_key, key, num_of_elements, int8_t, 389 CompareKeyWord8); 390 break; 391 case TYPE_UWord8: 392 KEY_QSORT(ptr_sort_key, key, num_of_elements, uint8_t, 393 CompareKeyUWord8); 394 break; 395 case TYPE_Word16: 396 KEY_QSORT(ptr_sort_key, key, num_of_elements, int16_t, 397 CompareKeyWord16); 398 break; 399 case TYPE_UWord16: 400 KEY_QSORT(ptr_sort_key, key, num_of_elements, uint16_t, 401 CompareKeyUWord16); 402 break; 403 case TYPE_Word32: 404 KEY_QSORT(ptr_sort_key, key, num_of_elements, int32_t, 405 CompareKeyWord32); 406 break; 407 case TYPE_UWord32: 408 KEY_QSORT(ptr_sort_key, key, num_of_elements, uint32_t, 409 CompareKeyUWord32); 410 break; 411 case TYPE_Word64: 412 KEY_QSORT(ptr_sort_key, key, num_of_elements, int64_t, 413 CompareKeyWord64); 414 break; 415 case TYPE_UWord64: 416 KEY_QSORT(ptr_sort_key, key, num_of_elements, uint64_t, 417 CompareKeyUWord64); 418 break; 419 case TYPE_Float32: 420 KEY_QSORT(ptr_sort_key, key, num_of_elements, float, 421 CompareKeyFloat32); 422 break; 423 case TYPE_Float64: 424 KEY_QSORT(ptr_sort_key, key, num_of_elements, double, 425 CompareKeyFloat64); 426 break; 427 default: 428 return -1; 429 } 430 431 // Shuffle into sorted position based on index map. 432 uint8_t* ptr_data = static_cast<uint8_t*>(data); 433 uint8_t* ptr_data_sorted = 434 new(std::nothrow) uint8_t[num_of_elements * size_of_element]; 435 if (ptr_data_sorted == NULL) { 436 return -1; 437 } 438 439 for (uint32_t i = 0; i < num_of_elements; i++) { 440 memcpy(ptr_data_sorted + i * size_of_element, ptr_data + 441 ptr_sort_key[i].index_ * size_of_element, size_of_element); 442 } 443 memcpy(ptr_data, ptr_data_sorted, num_of_elements * size_of_element); 444 445 delete[] ptr_sort_key; 446 delete[] ptr_data_sorted; 447 448 return 0; 449 #else 450 // Fall back to std::sort for 64-bit types and floats due to compiler 451 // warnings and errors respectively with spreadsort. 452 switch (key_type) { 453 case TYPE_Word8: 454 return IntegerKeySort<int8_t>(data, key, num_of_elements, 455 size_of_element); 456 case TYPE_UWord8: 457 return IntegerKeySort<uint8_t>(data, key, num_of_elements, 458 size_of_element); 459 case TYPE_Word16: 460 return IntegerKeySort<int16_t>(data, key, num_of_elements, 461 size_of_element); 462 case TYPE_UWord16: 463 return IntegerKeySort<uint16_t>(data, key, num_of_elements, 464 size_of_element); 465 case TYPE_Word32: 466 return IntegerKeySort<int32_t>(data, key, num_of_elements, 467 size_of_element); 468 case TYPE_UWord32: 469 return IntegerKeySort<uint32_t>(data, key, num_of_elements, 470 size_of_element); 471 case TYPE_Word64: 472 return StdKeySort<int64_t>(data, key, num_of_elements, 473 size_of_element); 474 case TYPE_UWord64: 475 return StdKeySort<uint64_t>(data, key, num_of_elements, 476 size_of_element); 477 case TYPE_Float32: 478 return StdKeySort<float>(data, key, num_of_elements, size_of_element); 479 case TYPE_Float64: 480 return StdKeySort<double>(data, key, num_of_elements, size_of_element); 481 } 482 assert(false); 483 return -1; 484 #endif 485 } 486 487 } // namespace webrtc 488
