Note: We no longer publish the latest version of our code here. We primarily use a kumc-bmi github organization. The heron ETL repository, in particular, is not public. Peers in the informatics community should see MultiSiteDev for details on requesting access.

source: webrtc/webrtc/system_wrappers/test/TestSort/TestSort.cc @ 0:4bda6873e34c

pub_scrub_3792 tip
Last change on this file since 0:4bda6873e34c was 0:4bda6873e34c, checked in by Michael Prittie <mprittie@…>, 6 years ago

Scrubbed password for publication.

File size: 7.2 KB
Line 
1/*
2 *  Copyright (c) 2011 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#include <stdio.h>
12#include <string.h>
13
14#include <algorithm>
15
16#include "webrtc/system_wrappers/interface/sort.h"
17#include "webrtc/system_wrappers/interface/tick_util.h"
18
19// Excellent work polluting the global namespace Visual Studio...
20#undef max
21#undef min
22#include <limits>
23
24template<typename KeyType>
25struct LotsOfData
26{
27    KeyType key;
28    char data[64];
29};
30
31template<typename DataType>
32int Compare(const void* dataX, const void* dataY)
33{
34    DataType dataX = (DataType)*(const DataType*)dataX;
35    DataType dataY = (DataType)*(const DataType*)dataY;
36    if (dataX > dataY)
37    {
38        return 1;
39    }
40    else if (dataX < dataY)
41    {
42        return -1;
43    }
44
45    return 0;
46};
47
48template<typename DataType, typename KeyType>
49int CompareKey(const void* dataX, const void* dataY)
50{
51    KeyType keyX = ((const DataType*)dataX)->key;
52    KeyType keyY = ((const DataType*)dataY)->key;
53    if (keyX > keyY)
54    {
55        return 1;
56    }
57    else if (keyX < keyY)
58    {
59        return -1;
60    }
61
62    return 0;
63}
64
65template<typename DataType>
66struct KeyLessThan
67{
68    bool operator()(const DataType &dataX, const DataType &dataY) const
69    {
70        return dataX.key < dataY.key;
71    }
72};
73
74const char* TypeEnumToString(webrtc::Type type)
75{
76    switch (type)
77    {
78        using namespace webrtc;
79        case TYPE_Word8:
80            return "Word8";
81        case TYPE_UWord8:
82            return "UWord8";
83        case TYPE_Word16:
84            return "Word16";
85        case TYPE_UWord16:
86            return "UWord16";
87        case TYPE_Word32:
88            return "Word32";
89        case TYPE_UWord32:
90            return "UWord32";
91        case TYPE_Word64:
92            return "Word64";
93        case TYPE_UWord64:
94            return "UWord64";
95        case TYPE_Float32:
96            return "Float32";
97        case TYPE_Float64:
98            return "Float64";
99        default:
100            return "Unrecognized";
101    }
102}
103
104template<typename Type>
105Type TypedRand()
106{
107    if (std::numeric_limits<Type>::is_integer)
108    {
109        double floatRand = static_cast<double>(rand()) / RAND_MAX;
110        if (std::numeric_limits<Type>::is_signed)
111        {
112            floatRand -= 0.5;
113        }
114
115        // Uniform [-max()/2, max()/2] for signed
116        //         [0, max()] for unsigned
117        return static_cast<Type>(floatRand * std::numeric_limits<Type>::max());
118    }
119    else // Floating point
120    {
121        // Uniform [-0.5, 0.5]
122        // The outer cast is to remove template warnings.
123        return static_cast<Type>((static_cast<Type>(rand()) / RAND_MAX) - 0.5);
124    }
125}
126
127template<typename KeyType>
128void RunSortTest(webrtc::Type sortType, bool keySort)
129{
130    enum { DataLength = 1000 };
131    enum { NumOfTests = 10000 };
132    KeyType key[DataLength];
133    KeyType keyRef[DataLength];
134    LotsOfData<KeyType> data[DataLength];
135    LotsOfData<KeyType> dataRef[DataLength];
136    int32_t retVal = 0;
137
138    if (keySort)
139    {
140        printf("Running %s KeySort() tests...\n", TypeEnumToString(sortType));
141    }
142    else
143    {
144        printf("Running %s Sort() tests...\n", TypeEnumToString(sortType));
145    }
146
147    TickInterval accTicks;
148    for (int i = 0; i < NumOfTests; i++)
149    {
150        for (int j = 0; j < DataLength; j++)
151        {
152            key[j] = TypedRand<KeyType>();
153            data[j].key = key[j];
154            // Write index to payload. We use this later for verification.
155            sprintf(data[j].data, "%d", j);
156        }
157
158        memcpy(dataRef, data, sizeof(data));
159        memcpy(keyRef, key, sizeof(key));
160
161        retVal = 0;
162        TickTime t0 = TickTime::Now();
163        if (keySort)
164        {
165            retVal = webrtc::KeySort(data, key, DataLength, sizeof(LotsOfData<KeyType>),
166                sortType);
167
168            //std::sort(data, data + DataLength, KeyLessThan<KeyType>());
169            //qsort(data, DataLength, sizeof(LotsOfData<KeyType>),
170            //    CompareKey<LotsOfData<KeyType>, KeyType>);
171        }
172        else
173        {
174            retVal = webrtc::Sort(key, DataLength, sortType);
175
176            //std::sort(key, key + DataLength);
177            //qsort(key, DataLength, sizeof(KeyType), Compare<KeyType>);
178        }
179        TickTime t1 = TickTime::Now();
180        accTicks += (t1 - t0);
181
182        if (retVal != 0)
183        {
184            printf("Test failed at iteration %d:\n", i);
185            printf("Sort returned an error. ");
186            printf("It likely does not support the requested type\nExiting...\n");
187            exit(0);
188        }
189
190        // Reference sort.
191        if (!keySort)
192        {
193            std::sort(keyRef, keyRef + DataLength);
194        }
195
196        if (keySort)
197        {
198            for (int j = 0; j < DataLength - 1; j++)
199            {
200                if (data[j].key > data[j + 1].key)
201                {
202                    printf("Test failed at iteration %d:\n", i);
203                    printf("Keys are not monotonically increasing\nExiting...\n");
204                    exit(0);
205                }
206
207                int index = atoi(data[j].data);
208                if (index < 0 || index >= DataLength || data[j].key != dataRef[index].key)
209                {
210                    printf("Test failed at iteration %d:\n", i);
211                    printf("Payload data is corrupt\nExiting...\n");
212                    exit(0);
213                }
214            }
215        }
216        else
217        {
218            for (int j = 0; j < DataLength - 1; j++)
219            {
220                if (key[j] > key[j + 1])
221                {
222                    printf("Test failed at iteration %d:\n", i);
223                    printf("Data is not monotonically increasing\nExiting...\n");
224                    exit(0);
225                }
226            }
227
228            if (memcmp(key, keyRef, sizeof(key)) != 0)
229            {
230                printf("Test failed at iteration %d:\n", i);
231                printf("Sort data differs from std::sort reference\nExiting...\n");
232                exit(0);
233            }
234        }
235    }
236
237    printf("Compliance test passed over %d iterations\n", NumOfTests);
238
239    int64_t executeTime = accTicks.Milliseconds();
240    printf("Execute time: %.2f s\n\n", (float)executeTime / 1000);
241}
242
243int main()
244{
245    // Seed rand().
246    srand(42);
247    bool keySort = false;
248    for (int i = 0; i < 2; i++) {
249        RunSortTest<int8_t>(webrtc::TYPE_Word8, keySort);
250        RunSortTest<uint8_t>(webrtc::TYPE_UWord8, keySort);
251        RunSortTest<int16_t>(webrtc::TYPE_Word16, keySort);
252        RunSortTest<uint16_t>(webrtc::TYPE_UWord16, keySort);
253        RunSortTest<int32_t>(webrtc::TYPE_Word32, keySort);
254        RunSortTest<uint32_t>(webrtc::TYPE_UWord32, keySort);
255        RunSortTest<int64_t>(webrtc::TYPE_Word64, keySort);
256        RunSortTest<uint64_t>(webrtc::TYPE_UWord64, keySort);
257        RunSortTest<float>(webrtc::TYPE_Float32, keySort);
258        RunSortTest<double>(webrtc::TYPE_Float64, keySort);
259
260        keySort = !keySort;
261    }
262
263    printf("All tests passed\n");
264
265    return 0;
266}
Note: See TracBrowser for help on using the repository browser.