OLD | NEW |
| (Empty) |
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 | |
90 int CompareWord8(const void* x, const void* y) { | |
91 COMPARE_FOR_QSORT(x, y, int8_t); | |
92 } | |
93 | |
94 int CompareUWord8(const void* x, const void* y) { | |
95 COMPARE_FOR_QSORT(x, y, uint8_t); | |
96 } | |
97 | |
98 int CompareWord16(const void* x, const void* y) { | |
99 COMPARE_FOR_QSORT(x, y, int16_t); | |
100 } | |
101 | |
102 int CompareUWord16(const void* x, const void* y) { | |
103 COMPARE_FOR_QSORT(x, y, uint16_t); | |
104 } | |
105 | |
106 int CompareWord32(const void* x, const void* y) { | |
107 COMPARE_FOR_QSORT(x, y, int32_t); | |
108 } | |
109 | |
110 int CompareUWord32(const void* x, const void* y) { | |
111 COMPARE_FOR_QSORT(x, y, uint32_t); | |
112 } | |
113 | |
114 int CompareWord64(const void* x, const void* y) { | |
115 COMPARE_FOR_QSORT(x, y, int64_t); | |
116 } | |
117 | |
118 int CompareUWord64(const void* x, const void* y) { | |
119 COMPARE_FOR_QSORT(x, y, uint64_t); | |
120 } | |
121 | |
122 int CompareFloat32(const void* x, const void* y) { | |
123 COMPARE_FOR_QSORT(x, y, float); | |
124 } | |
125 | |
126 int CompareFloat64(const void* x, const void* y) { | |
127 COMPARE_FOR_QSORT(x, y, double); | |
128 } | |
129 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
OLD | NEW |