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 "sort.h" 17 18 #include <cassert> 19 #include <cstring> // memcpy 20 #include <new> // nothrow new 21 22 #ifdef NO_STL 23 #include <cstdlib> // qsort 24 #else 25 #include <algorithm> // std::sort 26 #include <vector> 27 #include "spreadsort.hpp" // TODO (ajm) upgrade to spreadsortv2. 28 #endif 29 30 #ifdef NO_STL 31 #define COMPARE_DEREFERENCED(XT, YT) \ 32 do \ 33 { \ 34 if ((XT) > (YT)) \ 35 { \ 36 return 1; \ 37 } \ 38 else if ((XT) < (YT)) \ 39 { \ 40 return -1; \ 41 } \ 42 \ 43 return 0; \ 44 } \ 45 while(0) 46 47 #define COMPARE_FOR_QSORT(X, Y, TYPE) \ 48 do \ 49 { \ 50 TYPE xT = static_cast<TYPE>(*static_cast<const TYPE*>(X)); \ 51 TYPE yT = static_cast<TYPE>(*static_cast<const TYPE*>(Y)); \ 52 COMPARE_DEREFERENCED(xT, yT); \ 53 } \ 54 while(0) 55 56 #define COMPARE_KEY_FOR_QSORT(SORT_KEY_X, SORT_KEY_Y, TYPE) \ 57 do \ 58 { \ 59 TYPE xT = static_cast<TYPE>(*static_cast<TYPE*> \ 60 (static_cast<const SortKey*>(SORT_KEY_X)->key)); \ 61 TYPE yT = static_cast<TYPE>(*static_cast<TYPE*> \ 62 (static_cast<const SortKey*>(SORT_KEY_Y)->key)); \ 63 COMPARE_DEREFERENCED(xT, yT); \ 64 } \ 65 while(0) 66 67 #define KEY_QSORT(SORT_KEY, KEY, NUM_OF_ELEMENTS, KEY_TYPE, COMPARE_FUNC) \ 68 do \ 69 { \ 70 KEY_TYPE* keyT = (KEY_TYPE*)(key); \ 71 for (WebRtc_UWord32 i = 0; i < (NUM_OF_ELEMENTS); i++) \ 72 { \ 73 ptrSortKey[i].key = &keyT[i]; \ 74 ptrSortKey[i].index = i; \ 75 } \ 76 \ 77 qsort((SORT_KEY), (NUM_OF_ELEMENTS), sizeof(SortKey), (COMPARE_FUNC));\ 78 } \ 79 while(0) 80 #endif 81 82 namespace webrtc 83 { 84 #ifdef NO_STL 85 struct SortKey 86 { 87 void* key; 88 WebRtc_UWord32 index; 89 }; 90 #else 91 template<typename KeyType> 92 struct SortKey 93 { 94 KeyType key; 95 WebRtc_UWord32 index; 96 }; 97 #endif 98 99 namespace // Unnamed namespace provides internal linkage. 100 { 101 #ifdef NO_STL 102 int CompareWord8(const void* x, const void* y) 103 { 104 COMPARE_FOR_QSORT(x, y, WebRtc_Word8); 105 } 106 107 int CompareUWord8(const void* x, const void* y) 108 { 109 COMPARE_FOR_QSORT(x, y, WebRtc_UWord8); 110 } 111 112 int CompareWord16(const void* x, const void* y) 113 { 114 COMPARE_FOR_QSORT(x, y, WebRtc_Word16); 115 } 116 117 int CompareUWord16(const void* x, const void* y) 118 { 119 COMPARE_FOR_QSORT(x, y, WebRtc_UWord16); 120 } 121 122 int CompareWord32(const void* x, const void* y) 123 { 124 COMPARE_FOR_QSORT(x, y, WebRtc_Word32); 125 } 126 127 int CompareUWord32(const void* x, const void* y) 128 { 129 COMPARE_FOR_QSORT(x, y, WebRtc_UWord32); 130 } 131 132 int CompareWord64(const void* x, const void* y) 133 { 134 COMPARE_FOR_QSORT(x, y, WebRtc_Word64); 135 } 136 137 int CompareUWord64(const void* x, const void* y) 138 { 139 COMPARE_FOR_QSORT(x, y, WebRtc_UWord64); 140 } 141 142 int CompareFloat32(const void* x, const void* y) 143 { 144 COMPARE_FOR_QSORT(x, y, float); 145 } 146 147 int CompareFloat64(const void* x, const void* y) 148 { 149 COMPARE_FOR_QSORT(x, y, double); 150 } 151 152 int CompareKeyWord8(const void* sortKeyX, const void* sortKeyY) 153 { 154 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word8); 155 } 156 157 int CompareKeyUWord8(const void* sortKeyX, const void* sortKeyY) 158 { 159 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord8); 160 } 161 162 int CompareKeyWord16(const void* sortKeyX, const void* sortKeyY) 163 { 164 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word16); 165 } 166 167 int CompareKeyUWord16(const void* sortKeyX, const void* sortKeyY) 168 { 169 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord16); 170 } 171 172 int CompareKeyWord32(const void* sortKeyX, const void* sortKeyY) 173 { 174 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word32); 175 } 176 177 int CompareKeyUWord32(const void* sortKeyX, const void* sortKeyY) 178 { 179 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord32); 180 } 181 182 int CompareKeyWord64(const void* sortKeyX, const void* sortKeyY) 183 { 184 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word64); 185 } 186 187 int CompareKeyUWord64(const void* sortKeyX, const void* sortKeyY) 188 { 189 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord64); 190 } 191 192 int CompareKeyFloat32(const void* sortKeyX, const void* sortKeyY) 193 { 194 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, float); 195 } 196 197 int CompareKeyFloat64(const void* sortKeyX, const void* sortKeyY) 198 { 199 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, double); 200 } 201 #else 202 template <typename KeyType> 203 struct KeyLessThan 204 { 205 bool operator()(const SortKey<KeyType>& sortKeyX, 206 const SortKey<KeyType>& sortKeyY) const 207 { 208 return sortKeyX.key < sortKeyY.key; 209 } 210 }; 211 212 template <typename KeyType> 213 struct KeyRightShift 214 { 215 KeyType operator()(const SortKey<KeyType>& sortKey, 216 const unsigned offset) const 217 { 218 return sortKey.key >> offset; 219 } 220 }; 221 222 template <typename DataType> 223 inline void IntegerSort(void* data, WebRtc_UWord32 numOfElements) 224 { 225 DataType* dataT = static_cast<DataType*>(data); 226 boost::integer_sort(dataT, dataT + numOfElements); 227 } 228 229 template <typename DataType, typename IntegerType> 230 inline void FloatSort(void* data, WebRtc_UWord32 numOfElements) 231 { 232 DataType* dataT = static_cast<DataType*>(data); 233 IntegerType cVal = 0; 234 boost::float_sort_cast(dataT, dataT + numOfElements, cVal); 235 } 236 237 template <typename DataType> 238 inline void StdSort(void* data, WebRtc_UWord32 numOfElements) 239 { 240 DataType* dataT = static_cast<DataType*>(data); 241 std::sort(dataT, dataT + numOfElements); 242 } 243 244 template<typename KeyType> 245 inline WebRtc_Word32 SetupKeySort(void* key, 246 SortKey<KeyType>*& ptrSortKey, 247 WebRtc_UWord32 numOfElements) 248 { 249 ptrSortKey = new(std::nothrow) SortKey<KeyType>[numOfElements]; 250 if (ptrSortKey == NULL) 251 { 252 return -1; 253 } 254 255 KeyType* keyT = static_cast<KeyType*>(key); 256 for (WebRtc_UWord32 i = 0; i < numOfElements; i++) 257 { 258 ptrSortKey[i].key = keyT[i]; 259 ptrSortKey[i].index = i; 260 } 261 262 return 0; 263 } 264 265 template<typename KeyType> 266 inline WebRtc_Word32 TeardownKeySort(void* data, 267 SortKey<KeyType>* ptrSortKey, 268 WebRtc_UWord32 numOfElements, WebRtc_UWord32 sizeOfElement) 269 { 270 WebRtc_UWord8* ptrData = static_cast<WebRtc_UWord8*>(data); 271 WebRtc_UWord8* ptrDataSorted = new(std::nothrow) WebRtc_UWord8 272 [numOfElements * sizeOfElement]; 273 if (ptrDataSorted == NULL) 274 { 275 return -1; 276 } 277 278 for (WebRtc_UWord32 i = 0; i < numOfElements; i++) 279 { 280 memcpy(ptrDataSorted + i * sizeOfElement, ptrData + 281 ptrSortKey[i].index * sizeOfElement, sizeOfElement); 282 } 283 memcpy(ptrData, ptrDataSorted, numOfElements * sizeOfElement); 284 delete[] ptrSortKey; 285 delete[] ptrDataSorted; 286 return 0; 287 } 288 289 template<typename KeyType> 290 inline WebRtc_Word32 IntegerKeySort(void* data, void* key, 291 WebRtc_UWord32 numOfElements, 292 WebRtc_UWord32 sizeOfElement) 293 { 294 SortKey<KeyType>* ptrSortKey; 295 if (SetupKeySort<KeyType>(key, ptrSortKey, numOfElements) != 0) 296 { 297 return -1; 298 } 299 300 boost::integer_sort(ptrSortKey, ptrSortKey + numOfElements, 301 KeyRightShift<KeyType>(), KeyLessThan<KeyType>()); 302 303 if (TeardownKeySort<KeyType>(data, ptrSortKey, numOfElements, 304 sizeOfElement) != 0) 305 { 306 return -1; 307 } 308 309 return 0; 310 } 311 312 template<typename KeyType> 313 inline WebRtc_Word32 StdKeySort(void* data, void* key, 314 WebRtc_UWord32 numOfElements, 315 WebRtc_UWord32 sizeOfElement) 316 { 317 SortKey<KeyType>* ptrSortKey; 318 if (SetupKeySort<KeyType>(key, ptrSortKey, numOfElements) != 0) 319 { 320 return -1; 321 } 322 323 std::sort(ptrSortKey, ptrSortKey + numOfElements, 324 KeyLessThan<KeyType>()); 325 326 if (TeardownKeySort<KeyType>(data, ptrSortKey, numOfElements, 327 sizeOfElement) != 0) 328 { 329 return -1; 330 } 331 332 return 0; 333 } 334 #endif 335 } 336 337 WebRtc_Word32 Sort(void* data, WebRtc_UWord32 numOfElements, Type type) 338 { 339 if (data == NULL) 340 { 341 return -1; 342 } 343 344 #ifdef NO_STL 345 switch (type) 346 { 347 case TYPE_Word8: 348 qsort(data, numOfElements, sizeof(WebRtc_Word8), CompareWord8); 349 break; 350 case TYPE_UWord8: 351 qsort(data, numOfElements, sizeof(WebRtc_UWord8), CompareUWord8); 352 break; 353 case TYPE_Word16: 354 qsort(data, numOfElements, sizeof(WebRtc_Word16), CompareWord16); 355 break; 356 case TYPE_UWord16: 357 qsort(data, numOfElements, sizeof(WebRtc_UWord16), CompareUWord16); 358 break; 359 case TYPE_Word32: 360 qsort(data, numOfElements, sizeof(WebRtc_Word32), CompareWord32); 361 break; 362 case TYPE_UWord32: 363 qsort(data, numOfElements, sizeof(WebRtc_UWord32), CompareUWord32); 364 break; 365 case TYPE_Word64: 366 qsort(data, numOfElements, sizeof(WebRtc_Word64), CompareWord64); 367 break; 368 case TYPE_UWord64: 369 qsort(data, numOfElements, sizeof(WebRtc_UWord64), CompareUWord64); 370 break; 371 case TYPE_Float32: 372 qsort(data, numOfElements, sizeof(float), CompareFloat32); 373 break; 374 case TYPE_Float64: 375 qsort(data, numOfElements, sizeof(double), CompareFloat64); 376 break; 377 default: 378 return -1; 379 } 380 #else 381 // Fall back to std::sort for 64-bit types and floats due to compiler 382 // warnings and VS 2003 build crashes respectively with spreadsort. 383 switch (type) 384 { 385 case TYPE_Word8: 386 IntegerSort<WebRtc_Word8>(data, numOfElements); 387 break; 388 case TYPE_UWord8: 389 IntegerSort<WebRtc_UWord8>(data, numOfElements); 390 break; 391 case TYPE_Word16: 392 IntegerSort<WebRtc_Word16>(data, numOfElements); 393 break; 394 case TYPE_UWord16: 395 IntegerSort<WebRtc_UWord16>(data, numOfElements); 396 break; 397 case TYPE_Word32: 398 IntegerSort<WebRtc_Word32>(data, numOfElements); 399 break; 400 case TYPE_UWord32: 401 IntegerSort<WebRtc_UWord32>(data, numOfElements); 402 break; 403 case TYPE_Word64: 404 StdSort<WebRtc_Word64>(data, numOfElements); 405 break; 406 case TYPE_UWord64: 407 StdSort<WebRtc_UWord64>(data, numOfElements); 408 break; 409 case TYPE_Float32: 410 StdSort<float>(data, numOfElements); 411 break; 412 case TYPE_Float64: 413 StdSort<double>(data, numOfElements); 414 break; 415 } 416 #endif 417 return 0; 418 } 419 420 WebRtc_Word32 KeySort(void* data, void* key, WebRtc_UWord32 numOfElements, 421 WebRtc_UWord32 sizeOfElement, Type keyType) 422 { 423 if (data == NULL) 424 { 425 return -1; 426 } 427 428 if (key == NULL) 429 { 430 return -1; 431 } 432 433 if ((WebRtc_UWord64)numOfElements * sizeOfElement > 0xffffffff) 434 { 435 return -1; 436 } 437 438 #ifdef NO_STL 439 SortKey* ptrSortKey = new(std::nothrow) SortKey[numOfElements]; 440 if (ptrSortKey == NULL) 441 { 442 return -1; 443 } 444 445 switch (keyType) 446 { 447 case TYPE_Word8: 448 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word8, 449 CompareKeyWord8); 450 break; 451 case TYPE_UWord8: 452 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord8, 453 CompareKeyUWord8); 454 break; 455 case TYPE_Word16: 456 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word16, 457 CompareKeyWord16); 458 break; 459 case TYPE_UWord16: 460 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord16, 461 CompareKeyUWord16); 462 break; 463 case TYPE_Word32: 464 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word32, 465 CompareKeyWord32); 466 break; 467 case TYPE_UWord32: 468 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord32, 469 CompareKeyUWord32); 470 break; 471 case TYPE_Word64: 472 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word64, 473 CompareKeyWord64); 474 break; 475 case TYPE_UWord64: 476 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord64, 477 CompareKeyUWord64); 478 break; 479 case TYPE_Float32: 480 KEY_QSORT(ptrSortKey, key, numOfElements, float, 481 CompareKeyFloat32); 482 break; 483 case TYPE_Float64: 484 KEY_QSORT(ptrSortKey, key, numOfElements, double, 485 CompareKeyFloat64); 486 break; 487 default: 488 return -1; 489 } 490 491 // Shuffle into sorted position based on index map. 492 WebRtc_UWord8* ptrData = static_cast<WebRtc_UWord8*>(data); 493 WebRtc_UWord8* ptrDataSorted = new(std::nothrow) WebRtc_UWord8 494 [numOfElements * sizeOfElement]; 495 if (ptrDataSorted == NULL) 496 { 497 return -1; 498 } 499 500 for (WebRtc_UWord32 i = 0; i < numOfElements; i++) 501 { 502 memcpy(ptrDataSorted + i * sizeOfElement, ptrData + 503 ptrSortKey[i].index * sizeOfElement, sizeOfElement); 504 } 505 memcpy(ptrData, ptrDataSorted, numOfElements * sizeOfElement); 506 507 delete[] ptrSortKey; 508 delete[] ptrDataSorted; 509 510 return 0; 511 #else 512 // Fall back to std::sort for 64-bit types and floats due to compiler 513 // warnings and errors respectively with spreadsort. 514 switch (keyType) 515 { 516 case TYPE_Word8: 517 return IntegerKeySort<WebRtc_Word8>(data, key, numOfElements, 518 sizeOfElement); 519 case TYPE_UWord8: 520 return IntegerKeySort<WebRtc_UWord8>(data, key, numOfElements, 521 sizeOfElement); 522 case TYPE_Word16: 523 return IntegerKeySort<WebRtc_Word16>(data, key, numOfElements, 524 sizeOfElement); 525 case TYPE_UWord16: 526 return IntegerKeySort<WebRtc_UWord16>(data, key, numOfElements, 527 sizeOfElement); 528 case TYPE_Word32: 529 return IntegerKeySort<WebRtc_Word32>(data, key, numOfElements, 530 sizeOfElement); 531 case TYPE_UWord32: 532 return IntegerKeySort<WebRtc_UWord32>(data, key, numOfElements, 533 sizeOfElement); 534 case TYPE_Word64: 535 return StdKeySort<WebRtc_Word64>(data, key, numOfElements, 536 sizeOfElement); 537 case TYPE_UWord64: 538 return StdKeySort<WebRtc_UWord64>(data, key, numOfElements, 539 sizeOfElement); 540 case TYPE_Float32: 541 return StdKeySort<float>(data, key, numOfElements, sizeOfElement); 542 case TYPE_Float64: 543 return StdKeySort<double>(data, key, numOfElements, sizeOfElement); 544 } 545 assert(false); 546 return -1; 547 #endif 548 } 549 } // namespace webrtc 550
