1 /* 2 * Copyright (c) 2011 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 CompareWord8(const void * x,const void * y)102 int CompareWord8(const void* x, const void* y) 103 { 104 COMPARE_FOR_QSORT(x, y, WebRtc_Word8); 105 } 106 CompareUWord8(const void * x,const void * y)107 int CompareUWord8(const void* x, const void* y) 108 { 109 COMPARE_FOR_QSORT(x, y, WebRtc_UWord8); 110 } 111 CompareWord16(const void * x,const void * y)112 int CompareWord16(const void* x, const void* y) 113 { 114 COMPARE_FOR_QSORT(x, y, WebRtc_Word16); 115 } 116 CompareUWord16(const void * x,const void * y)117 int CompareUWord16(const void* x, const void* y) 118 { 119 COMPARE_FOR_QSORT(x, y, WebRtc_UWord16); 120 } 121 CompareWord32(const void * x,const void * y)122 int CompareWord32(const void* x, const void* y) 123 { 124 COMPARE_FOR_QSORT(x, y, WebRtc_Word32); 125 } 126 CompareUWord32(const void * x,const void * y)127 int CompareUWord32(const void* x, const void* y) 128 { 129 COMPARE_FOR_QSORT(x, y, WebRtc_UWord32); 130 } 131 CompareWord64(const void * x,const void * y)132 int CompareWord64(const void* x, const void* y) 133 { 134 COMPARE_FOR_QSORT(x, y, WebRtc_Word64); 135 } 136 CompareUWord64(const void * x,const void * y)137 int CompareUWord64(const void* x, const void* y) 138 { 139 COMPARE_FOR_QSORT(x, y, WebRtc_UWord64); 140 } 141 CompareFloat32(const void * x,const void * y)142 int CompareFloat32(const void* x, const void* y) 143 { 144 COMPARE_FOR_QSORT(x, y, float); 145 } 146 CompareFloat64(const void * x,const void * y)147 int CompareFloat64(const void* x, const void* y) 148 { 149 COMPARE_FOR_QSORT(x, y, double); 150 } 151 CompareKeyWord8(const void * sortKeyX,const void * sortKeyY)152 int CompareKeyWord8(const void* sortKeyX, const void* sortKeyY) 153 { 154 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word8); 155 } 156 CompareKeyUWord8(const void * sortKeyX,const void * sortKeyY)157 int CompareKeyUWord8(const void* sortKeyX, const void* sortKeyY) 158 { 159 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord8); 160 } 161 CompareKeyWord16(const void * sortKeyX,const void * sortKeyY)162 int CompareKeyWord16(const void* sortKeyX, const void* sortKeyY) 163 { 164 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word16); 165 } 166 CompareKeyUWord16(const void * sortKeyX,const void * sortKeyY)167 int CompareKeyUWord16(const void* sortKeyX, const void* sortKeyY) 168 { 169 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord16); 170 } 171 CompareKeyWord32(const void * sortKeyX,const void * sortKeyY)172 int CompareKeyWord32(const void* sortKeyX, const void* sortKeyY) 173 { 174 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word32); 175 } 176 CompareKeyUWord32(const void * sortKeyX,const void * sortKeyY)177 int CompareKeyUWord32(const void* sortKeyX, const void* sortKeyY) 178 { 179 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord32); 180 } 181 CompareKeyWord64(const void * sortKeyX,const void * sortKeyY)182 int CompareKeyWord64(const void* sortKeyX, const void* sortKeyY) 183 { 184 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word64); 185 } 186 CompareKeyUWord64(const void * sortKeyX,const void * sortKeyY)187 int CompareKeyUWord64(const void* sortKeyX, const void* sortKeyY) 188 { 189 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord64); 190 } 191 CompareKeyFloat32(const void * sortKeyX,const void * sortKeyY)192 int CompareKeyFloat32(const void* sortKeyX, const void* sortKeyY) 193 { 194 COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, float); 195 } 196 CompareKeyFloat64(const void * sortKeyX,const void * sortKeyY)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 Sort(void * data,WebRtc_UWord32 numOfElements,Type type)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 default: 416 return -1; 417 } 418 #endif 419 return 0; 420 } 421 KeySort(void * data,void * key,WebRtc_UWord32 numOfElements,WebRtc_UWord32 sizeOfElement,Type keyType)422 WebRtc_Word32 KeySort(void* data, void* key, WebRtc_UWord32 numOfElements, 423 WebRtc_UWord32 sizeOfElement, Type keyType) 424 { 425 if (data == NULL) 426 { 427 return -1; 428 } 429 430 if (key == NULL) 431 { 432 return -1; 433 } 434 435 if ((WebRtc_UWord64)numOfElements * sizeOfElement > 0xffffffff) 436 { 437 return -1; 438 } 439 440 #ifdef NO_STL 441 SortKey* ptrSortKey = new(std::nothrow) SortKey[numOfElements]; 442 if (ptrSortKey == NULL) 443 { 444 return -1; 445 } 446 447 switch (keyType) 448 { 449 case TYPE_Word8: 450 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word8, 451 CompareKeyWord8); 452 break; 453 case TYPE_UWord8: 454 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord8, 455 CompareKeyUWord8); 456 break; 457 case TYPE_Word16: 458 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word16, 459 CompareKeyWord16); 460 break; 461 case TYPE_UWord16: 462 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord16, 463 CompareKeyUWord16); 464 break; 465 case TYPE_Word32: 466 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word32, 467 CompareKeyWord32); 468 break; 469 case TYPE_UWord32: 470 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord32, 471 CompareKeyUWord32); 472 break; 473 case TYPE_Word64: 474 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word64, 475 CompareKeyWord64); 476 break; 477 case TYPE_UWord64: 478 KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord64, 479 CompareKeyUWord64); 480 break; 481 case TYPE_Float32: 482 KEY_QSORT(ptrSortKey, key, numOfElements, float, 483 CompareKeyFloat32); 484 break; 485 case TYPE_Float64: 486 KEY_QSORT(ptrSortKey, key, numOfElements, double, 487 CompareKeyFloat64); 488 break; 489 default: 490 return -1; 491 } 492 493 // Shuffle into sorted position based on index map. 494 WebRtc_UWord8* ptrData = static_cast<WebRtc_UWord8*>(data); 495 WebRtc_UWord8* ptrDataSorted = new(std::nothrow) WebRtc_UWord8 496 [numOfElements * sizeOfElement]; 497 if (ptrDataSorted == NULL) 498 { 499 return -1; 500 } 501 502 for (WebRtc_UWord32 i = 0; i < numOfElements; i++) 503 { 504 memcpy(ptrDataSorted + i * sizeOfElement, ptrData + 505 ptrSortKey[i].index * sizeOfElement, sizeOfElement); 506 } 507 memcpy(ptrData, ptrDataSorted, numOfElements * sizeOfElement); 508 509 delete[] ptrSortKey; 510 delete[] ptrDataSorted; 511 512 return 0; 513 #else 514 // Fall back to std::sort for 64-bit types and floats due to compiler 515 // warnings and errors respectively with spreadsort. 516 switch (keyType) 517 { 518 case TYPE_Word8: 519 return IntegerKeySort<WebRtc_Word8>(data, key, numOfElements, 520 sizeOfElement); 521 case TYPE_UWord8: 522 return IntegerKeySort<WebRtc_UWord8>(data, key, numOfElements, 523 sizeOfElement); 524 case TYPE_Word16: 525 return IntegerKeySort<WebRtc_Word16>(data, key, numOfElements, 526 sizeOfElement); 527 case TYPE_UWord16: 528 return IntegerKeySort<WebRtc_UWord16>(data, key, numOfElements, 529 sizeOfElement); 530 case TYPE_Word32: 531 return IntegerKeySort<WebRtc_Word32>(data, key, numOfElements, 532 sizeOfElement); 533 case TYPE_UWord32: 534 return IntegerKeySort<WebRtc_UWord32>(data, key, numOfElements, 535 sizeOfElement); 536 case TYPE_Word64: 537 return StdKeySort<WebRtc_Word64>(data, key, numOfElements, 538 sizeOfElement); 539 case TYPE_UWord64: 540 return StdKeySort<WebRtc_UWord64>(data, key, numOfElements, 541 sizeOfElement); 542 case TYPE_Float32: 543 return StdKeySort<float>(data, key, numOfElements, sizeOfElement); 544 case TYPE_Float64: 545 return StdKeySort<double>(data, key, numOfElements, sizeOfElement); 546 default: 547 return -1; 548 } 549 #endif 550 } 551 } // namespace webrtc 552