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/include/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
72 namespace webrtc {
73
74 #ifdef NO_STL
75 struct SortKey {
76 void* key_;
77 uint32_t index_;
78 };
79 #else
80 template<typename KeyType>
81 struct SortKey {
82 KeyType key_;
83 uint32_t index_;
84 };
85 #endif
86
87 namespace { // Unnamed namespace provides internal linkage.
88
89 #ifdef NO_STL
CompareWord8(const void * x,const void * y)90 int CompareWord8(const void* x, const void* y) {
91 COMPARE_FOR_QSORT(x, y, int8_t);
92 }
93
CompareUWord8(const void * x,const void * y)94 int CompareUWord8(const void* x, const void* y) {
95 COMPARE_FOR_QSORT(x, y, uint8_t);
96 }
97
CompareWord16(const void * x,const void * y)98 int CompareWord16(const void* x, const void* y) {
99 COMPARE_FOR_QSORT(x, y, int16_t);
100 }
101
CompareUWord16(const void * x,const void * y)102 int CompareUWord16(const void* x, const void* y) {
103 COMPARE_FOR_QSORT(x, y, uint16_t);
104 }
105
CompareWord32(const void * x,const void * y)106 int CompareWord32(const void* x, const void* y) {
107 COMPARE_FOR_QSORT(x, y, int32_t);
108 }
109
CompareUWord32(const void * x,const void * y)110 int CompareUWord32(const void* x, const void* y) {
111 COMPARE_FOR_QSORT(x, y, uint32_t);
112 }
113
CompareWord64(const void * x,const void * y)114 int CompareWord64(const void* x, const void* y) {
115 COMPARE_FOR_QSORT(x, y, int64_t);
116 }
117
CompareUWord64(const void * x,const void * y)118 int CompareUWord64(const void* x, const void* y) {
119 COMPARE_FOR_QSORT(x, y, uint64_t);
120 }
121
CompareFloat32(const void * x,const void * y)122 int CompareFloat32(const void* x, const void* y) {
123 COMPARE_FOR_QSORT(x, y, float);
124 }
125
CompareFloat64(const void * x,const void * y)126 int CompareFloat64(const void* x, const void* y) {
127 COMPARE_FOR_QSORT(x, y, double);
128 }
129
CompareKeyWord8(const void * sort_key_x,const void * sort_key_y)130 int 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
CompareKeyUWord8(const void * sort_key_x,const void * sort_key_y)134 int 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
CompareKeyWord16(const void * sort_key_x,const void * sort_key_y)138 int 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
CompareKeyUWord16(const void * sort_key_x,const void * sort_key_y)142 int 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
CompareKeyWord32(const void * sort_key_x,const void * sort_key_y)146 int 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
CompareKeyUWord32(const void * sort_key_x,const void * sort_key_y)150 int 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
CompareKeyWord64(const void * sort_key_x,const void * sort_key_y)154 int 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
CompareKeyUWord64(const void * sort_key_x,const void * sort_key_y)158 int 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
CompareKeyFloat32(const void * sort_key_x,const void * sort_key_y)162 int 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
CompareKeyFloat64(const void * sort_key_x,const void * sort_key_y)166 int 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
170 template <typename KeyType>
171 struct 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
178 template <typename KeyType>
179 struct KeyRightShift {
180 KeyType operator()(const SortKey<KeyType>& sort_key,
181 const unsigned offset) const {
182 return sort_key.key_ >> offset;
183 }
184 };
185
186 template <typename DataType>
187 inline 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
192 template <typename DataType, typename IntegerType>
193 inline 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
199 template <typename DataType>
200 inline 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
205 template<typename KeyType>
206 inline 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
223 template<typename KeyType>
224 inline 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
245 template<typename KeyType>
246 inline 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
265 template<typename KeyType>
266 inline 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
Sort(void * data,uint32_t num_of_elements,Type type)287 int32_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
KeySort(void * data,void * key,uint32_t num_of_elements,uint32_t size_of_element,Type key_type)366 int32_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