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
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         }
416 #endif
417         return 0;
418     }
419 
KeySort(void * data,void * key,WebRtc_UWord32 numOfElements,WebRtc_UWord32 sizeOfElement,Type keyType)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