1470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com/* 2c80d9d9361ac22bbd277e8377a2dba93479ebff8mflodman@webrtc.org * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved. 3470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com * 4470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com * Use of this source code is governed by a BSD-style license 5470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com * that can be found in the LICENSE file in the root of the source 6470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com * tree. An additional intellectual property rights grant can be found 7470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com * in the file PATENTS. All contributing project authors may 8470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com * be found in the AUTHORS file in the root of the source tree. 9470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com */ 10470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 11470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com// When the platform supports STL, the functions are implemented using a 12470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com// templated spreadsort algorithm (http://sourceforge.net/projects/spreadsort/), 13470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com// part of the Boost C++ library collection. Otherwise, the C standard library's 14470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com// qsort() will be used. 15470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 1698f53510b222f71fdd8b799b2f33737ceeb28c61Henrik Kjellander#include "webrtc/system_wrappers/include/sort.h" 17470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 1812dc1a38ca54a000e4fecfbc6d41138b895c9ca5pbos@webrtc.org#include <assert.h> 1912dc1a38ca54a000e4fecfbc6d41138b895c9ca5pbos@webrtc.org#include <string.h> // memcpy 2012dc1a38ca54a000e4fecfbc6d41138b895c9ca5pbos@webrtc.org 21470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#include <new> // nothrow new 22470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 23470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#ifdef NO_STL 2412dc1a38ca54a000e4fecfbc6d41138b895c9ca5pbos@webrtc.org#include <stdlib.h> // qsort 25470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#else 26470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#include <algorithm> // std::sort 27470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#include <vector> 286bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 29acaf3a1b131e049000552c53c8cbfe737e2d8f58pbos@webrtc.org// TODO(ajm) upgrade to spreadsort v2. 30acaf3a1b131e049000552c53c8cbfe737e2d8f58pbos@webrtc.org#include "webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp" 31470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#endif 32470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 33470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#ifdef NO_STL 346bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org#define COMPARE_DEREFERENCED(XT, YT) \ 356bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org do { \ 366bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if ((XT) > (YT)) { \ 376bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 1; \ 386bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } \ 396bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org else if ((XT) < (YT)) { \ 406bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; \ 416bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } \ 426bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 0; \ 436bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } while(0) 446bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 456bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org#define COMPARE_FOR_QSORT(X, Y, TYPE) \ 466bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org do { \ 476bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org TYPE xT = static_cast<TYPE>(*static_cast<const TYPE*>(X)); \ 486bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org TYPE yT = static_cast<TYPE>(*static_cast<const TYPE*>(Y)); \ 496bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org COMPARE_DEREFERENCED(xT, yT); \ 506bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } while(0) 516bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 526bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org#define COMPARE_KEY_FOR_QSORT(SORT_KEY_X, SORT_KEY_Y, TYPE) \ 536bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org do { \ 546bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org TYPE xT = static_cast<TYPE>( \ 556bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org *static_cast<TYPE*>(static_cast<const SortKey*>(SORT_KEY_X)->key_)); \ 566bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org TYPE yT = static_cast<TYPE>( \ 576bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org *static_cast<TYPE*>(static_cast<const SortKey*>(SORT_KEY_Y)->key_)); \ 586bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org COMPARE_DEREFERENCED(xT, yT); \ 596bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } while(0) 60470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 61470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#define KEY_QSORT(SORT_KEY, KEY, NUM_OF_ELEMENTS, KEY_TYPE, COMPARE_FUNC) \ 626bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org do { \ 636bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KEY_TYPE* key_type = (KEY_TYPE*)(key); \ 64046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org for (uint32_t i = 0; i < (NUM_OF_ELEMENTS); ++i) { \ 656bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org ptr_sort_key[i].key_ = &key_type[i]; \ 666bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org ptr_sort_key[i].index_ = i; \ 67470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com } \ 686bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org qsort((SORT_KEY), (NUM_OF_ELEMENTS), sizeof(SortKey), (COMPARE_FUNC)); \ 696bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } while(0) 70470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#endif 71470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 726bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgnamespace webrtc { 736bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 74470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#ifdef NO_STL 756bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgstruct SortKey { 766bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org void* key_; 77046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t index_; 786bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org}; 79470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#else 806bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate<typename KeyType> 816bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgstruct SortKey { 826bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KeyType key_; 83046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t index_; 846bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org}; 85470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#endif 86470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 876bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgnamespace { // Unnamed namespace provides internal linkage. 886bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 89470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#ifdef NO_STL 906bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareWord8(const void* x, const void* y) { 91046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, int8_t); 926bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 936bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 946bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareUWord8(const void* x, const void* y) { 95046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, uint8_t); 966bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 976bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 986bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareWord16(const void* x, const void* y) { 99046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, int16_t); 1006bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1016bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1026bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareUWord16(const void* x, const void* y) { 103046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, uint16_t); 1046bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1056bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1066bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareWord32(const void* x, const void* y) { 107046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, int32_t); 1086bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1096bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1106bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareUWord32(const void* x, const void* y) { 111046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, uint32_t); 1126bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1136bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1146bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareWord64(const void* x, const void* y) { 115046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, int64_t); 1166bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1176bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1186bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareUWord64(const void* x, const void* y) { 119046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_FOR_QSORT(x, y, uint64_t); 1206bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1216bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1226bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareFloat32(const void* x, const void* y) { 1236bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org COMPARE_FOR_QSORT(x, y, float); 1246bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1256bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1266bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareFloat64(const void* x, const void* y) { 1276bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org COMPARE_FOR_QSORT(x, y, double); 1286bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1296bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1306bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyWord8(const void* sort_key_x, const void* sort_key_y) { 131046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int8_t); 1326bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1336bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1346bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyUWord8(const void* sort_key_x, const void* sort_key_y) { 135046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint8_t); 1366bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1376bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1386bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyWord16(const void* sort_key_x, const void* sort_key_y) { 139046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int16_t); 1406bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1416bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1426bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyUWord16(const void* sort_key_x, const void* sort_key_y) { 143046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint16_t); 1446bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1456bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1466bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyWord32(const void* sort_key_x, const void* sort_key_y) { 147046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int32_t); 1486bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1496bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1506bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyUWord32(const void* sort_key_x, const void* sort_key_y) { 151046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint32_t); 1526bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1536bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1546bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyWord64(const void* sort_key_x, const void* sort_key_y) { 155046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, int64_t); 1566bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1576bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1586bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyUWord64(const void* sort_key_x, const void* sort_key_y) { 159046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, uint64_t); 1606bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1616bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1626bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyFloat32(const void* sort_key_x, const void* sort_key_y) { 1636bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, float); 1646bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1656bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1666bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgint CompareKeyFloat64(const void* sort_key_x, const void* sort_key_y) { 1676bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org COMPARE_KEY_FOR_QSORT(sort_key_x, sort_key_y, double); 1686bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 169470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#else 1706bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate <typename KeyType> 1716bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgstruct KeyLessThan { 1726bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org bool operator()(const SortKey<KeyType>& sort_key_x, 1736bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org const SortKey<KeyType>& sort_key_y) const { 1746bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return sort_key_x.key_ < sort_key_y.key_; 1756bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 1766bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org}; 1776bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1786bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate <typename KeyType> 1796bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgstruct KeyRightShift { 1806bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KeyType operator()(const SortKey<KeyType>& sort_key, 1816bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org const unsigned offset) const { 1826bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return sort_key.key_ >> offset; 1836bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 1846bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org}; 1856bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1866bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate <typename DataType> 187046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orginline void IntegerSort(void* data, uint32_t num_of_elements) { 1886bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org DataType* data_type = static_cast<DataType*>(data); 1896bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org boost::integer_sort(data_type, data_type + num_of_elements); 1906bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1916bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1926bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate <typename DataType, typename IntegerType> 193046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orginline void FloatSort(void* data, uint32_t num_of_elements) { 1946bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org DataType* data_type = static_cast<DataType*>(data); 1956bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org IntegerType c_val = 0; 1966bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org boost::float_sort_cast(data_type, data_type + num_of_elements, c_val); 1976bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 1986bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 1996bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate <typename DataType> 200046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orginline void StdSort(void* data, uint32_t num_of_elements) { 2016bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org DataType* data_type = static_cast<DataType*>(data); 2026bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org std::sort(data_type, data_type + num_of_elements); 2036bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 2046bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2056bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate<typename KeyType> 206046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orginline int32_t SetupKeySort(void* key, 207046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org SortKey<KeyType>*& ptr_sort_key, 208046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t num_of_elements) { 2096bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org ptr_sort_key = new(std::nothrow) SortKey<KeyType>[num_of_elements]; 2106bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (ptr_sort_key == NULL) { 2116bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 2126bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2136bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2146bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KeyType* key_type = static_cast<KeyType*>(key); 215046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org for (uint32_t i = 0; i < num_of_elements; i++) { 2166bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org ptr_sort_key[i].key_ = key_type[i]; 2176bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org ptr_sort_key[i].index_ = i; 2186bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2196bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2206bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 0; 2216bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 2226bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2236bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate<typename KeyType> 224046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orginline int32_t TeardownKeySort(void* data, 225046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org SortKey<KeyType>* ptr_sort_key, 226046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t num_of_elements, 227046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t size_of_element) { 228046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint8_t* ptr_data = static_cast<uint8_t*>(data); 229046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint8_t* ptr_data_sorted = 230046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org new(std::nothrow) uint8_t[num_of_elements * size_of_element]; 2316bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (ptr_data_sorted == NULL) { 2326bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 2336bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2346bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 235046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org for (uint32_t i = 0; i < num_of_elements; i++) { 2366bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org memcpy(ptr_data_sorted + i * size_of_element, ptr_data + 2376bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org ptr_sort_key[i].index_ * size_of_element, size_of_element); 2386bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2396bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org memcpy(ptr_data, ptr_data_sorted, num_of_elements * size_of_element); 2406bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org delete[] ptr_sort_key; 2416bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org delete[] ptr_data_sorted; 2426bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 0; 2436bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 2446bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2456bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate<typename KeyType> 246046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orginline int32_t IntegerKeySort(void* data, void* key, 247046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t num_of_elements, 248046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t size_of_element) { 2496bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org SortKey<KeyType>* ptr_sort_key; 2506bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (SetupKeySort<KeyType>(key, ptr_sort_key, num_of_elements) != 0) { 2516bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 2526bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2536bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2546bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org boost::integer_sort(ptr_sort_key, ptr_sort_key + num_of_elements, 2556bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KeyRightShift<KeyType>(), KeyLessThan<KeyType>()); 2566bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2576bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (TeardownKeySort<KeyType>(data, ptr_sort_key, num_of_elements, 2586bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org size_of_element) != 0) { 2596bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 2606bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2616bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2626bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 0; 2636bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 2646bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2656bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.orgtemplate<typename KeyType> 266046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orginline int32_t StdKeySort(void* data, void* key, 267046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t num_of_elements, 268046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t size_of_element) { 2696bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org SortKey<KeyType>* ptr_sort_key; 2706bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (SetupKeySort<KeyType>(key, ptr_sort_key, num_of_elements) != 0) { 2716bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 2726bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2736bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2746bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org std::sort(ptr_sort_key, ptr_sort_key + num_of_elements, 2756bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KeyLessThan<KeyType>()); 2766bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2776bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (TeardownKeySort<KeyType>(data, ptr_sort_key, num_of_elements, 2786bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org size_of_element) != 0) { 2796bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 2806bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 2816bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 2826bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 0; 2836bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 284470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#endif 2856bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 286470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 287046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orgint32_t Sort(void* data, uint32_t num_of_elements, Type type) { 2886bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (data == NULL) { 2896bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 2906bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 291470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 292470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#ifdef NO_STL 2936bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org switch (type) { 2946bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word8: 295046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(int8_t), CompareWord8); 2966bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 2976bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord8: 298046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(uint8_t), CompareUWord8); 2996bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3006bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word16: 301046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(int16_t), CompareWord16); 3026bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3036bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord16: 304046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(uint16_t), CompareUWord16); 3056bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3066bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word32: 307046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(int32_t), CompareWord32); 3086bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3096bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord32: 310046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(uint32_t), CompareUWord32); 3116bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3126bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word64: 313046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(int64_t), CompareWord64); 3146bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3156bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord64: 316046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org qsort(data, num_of_elements, sizeof(uint64_t), CompareUWord64); 3176bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3186bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float32: 3196bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org qsort(data, num_of_elements, sizeof(float), CompareFloat32); 3206bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3216bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float64: 3226bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org qsort(data, num_of_elements, sizeof(double), CompareFloat64); 3236bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3246bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org default: 3256bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 3266bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 327470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#else 3286bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org // Fall back to std::sort for 64-bit types and floats due to compiler 3296bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org // warnings and VS 2003 build crashes respectively with spreadsort. 3306bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org switch (type) { 3316bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word8: 332046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org IntegerSort<int8_t>(data, num_of_elements); 3336bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3346bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord8: 335046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org IntegerSort<uint8_t>(data, num_of_elements); 3366bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3376bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word16: 338046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org IntegerSort<int16_t>(data, num_of_elements); 3396bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3406bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord16: 341046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org IntegerSort<uint16_t>(data, num_of_elements); 3426bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3436bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word32: 344046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org IntegerSort<int32_t>(data, num_of_elements); 3456bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3466bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord32: 347046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org IntegerSort<uint32_t>(data, num_of_elements); 3486bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3496bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word64: 350046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org StdSort<int64_t>(data, num_of_elements); 3516bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3526bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord64: 353046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org StdSort<uint64_t>(data, num_of_elements); 3546bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3556bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float32: 3566bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org StdSort<float>(data, num_of_elements); 3576bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3586bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float64: 3596bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org StdSort<double>(data, num_of_elements); 3606bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3616bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 362470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#endif 3636bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 0; 3646bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 3656bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 366046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.orgint32_t KeySort(void* data, void* key, uint32_t num_of_elements, 367046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint32_t size_of_element, Type key_type) { 3686bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (data == NULL) { 3696bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 3706bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 3716bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 3726bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (key == NULL) { 3736bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 3746bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 3756bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 376046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org if ((uint64_t)num_of_elements * size_of_element > 0xffffffff) { 3776bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 3786bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 379470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com 380470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#ifdef NO_STL 3816bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org SortKey* ptr_sort_key = new(std::nothrow) SortKey[num_of_elements]; 3826bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (ptr_sort_key == NULL) { 3836bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 3846bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 3856bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 3866bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org switch (key_type) { 3876bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word8: 388046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, int8_t, 389470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyWord8); 3906bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3916bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord8: 392046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, uint8_t, 393470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyUWord8); 3946bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3956bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word16: 396046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, int16_t, 397470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyWord16); 3986bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 3996bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord16: 400046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, uint16_t, 401470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyUWord16); 4026bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 4036bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word32: 404046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, int32_t, 405470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyWord32); 4066bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 4076bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord32: 408046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, uint32_t, 409470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyUWord32); 4106bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 4116bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word64: 412046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, int64_t, 413470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyWord64); 4146bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 4156bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord64: 416046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, uint64_t, 417470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyUWord64); 4186bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 4196bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float32: 4206bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, float, 421470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyFloat32); 4226bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 4236bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float64: 4246bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org KEY_QSORT(ptr_sort_key, key, num_of_elements, double, 425470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com CompareKeyFloat64); 4266bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org break; 4276bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org default: 4286bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 4296bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 4306bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 4316bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org // Shuffle into sorted position based on index map. 432046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint8_t* ptr_data = static_cast<uint8_t*>(data); 433046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org uint8_t* ptr_data_sorted = 434046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org new(std::nothrow) uint8_t[num_of_elements * size_of_element]; 4356bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org if (ptr_data_sorted == NULL) { 4366bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 4376bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 4386bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 439046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org for (uint32_t i = 0; i < num_of_elements; i++) { 4406bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org memcpy(ptr_data_sorted + i * size_of_element, ptr_data + 4416bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org ptr_sort_key[i].index_ * size_of_element, size_of_element); 4426bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 4436bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org memcpy(ptr_data, ptr_data_sorted, num_of_elements * size_of_element); 4446bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 4456bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org delete[] ptr_sort_key; 4466bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org delete[] ptr_data_sorted; 4476bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 4486bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return 0; 449470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#else 4506bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org // Fall back to std::sort for 64-bit types and floats due to compiler 4516bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org // warnings and errors respectively with spreadsort. 4526bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org switch (key_type) { 4536bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word8: 454046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return IntegerKeySort<int8_t>(data, key, num_of_elements, 455046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4566bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord8: 457046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return IntegerKeySort<uint8_t>(data, key, num_of_elements, 458046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4596bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word16: 460046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return IntegerKeySort<int16_t>(data, key, num_of_elements, 461046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4626bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord16: 463046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return IntegerKeySort<uint16_t>(data, key, num_of_elements, 464046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4656bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word32: 466046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return IntegerKeySort<int32_t>(data, key, num_of_elements, 467046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4686bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord32: 469046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return IntegerKeySort<uint32_t>(data, key, num_of_elements, 470046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4716bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Word64: 472046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return StdKeySort<int64_t>(data, key, num_of_elements, 473046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4746bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_UWord64: 475046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org return StdKeySort<uint64_t>(data, key, num_of_elements, 476046deb9b2050ebdf98a41e2d22f852e104dd365apbos@webrtc.org size_of_element); 4776bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float32: 4786bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return StdKeySort<float>(data, key, num_of_elements, size_of_element); 4796bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org case TYPE_Float64: 4806bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return StdKeySort<double>(data, key, num_of_elements, size_of_element); 4816bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org } 4826bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org assert(false); 4836bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org return -1; 484470e71d3649f6cac4688e83819640b012b5d38bbniklase@google.com#endif 4856bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org} 4866bc5d4dc070e1452536d78bcf4ee91a4c97b6521phoglund@webrtc.org 487d900e8bea84c474696bf0219aed1353ce65ffd8epbos@webrtc.org} // namespace webrtc 488