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