Home | History | Annotate | Download | only in source
      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