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
82namespace 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