| OLD | NEW |
|---|
| (Empty) |
| 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/base/timeutils.h" | |
| 17 #include "webrtc/system_wrappers/include/sort.h" | |
| 18 | |
| 19 // Excellent work polluting the global namespace Visual Studio... | |
| 20 #undef max | |
| 21 #undef min | |
| 22 #include <limits> | |
| 23 | |
| 24 template<typename KeyType> | |
| 25 struct LotsOfData | |
| 26 { | |
| 27 KeyType key; | |
| 28 char data[64]; | |
| 29 }; | |
| 30 | |
| 31 template<typename DataType> | |
| 32 int 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 | |
| 48 template<typename DataType, typename KeyType> | |
| 49 int 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 | |
| 65 template<typename DataType> | |
| 66 struct KeyLessThan | |
| 67 { | |
| 68 bool operator()(const DataType &dataX, const DataType &dataY) const | |
| 69 { | |
| 70 return dataX.key < dataY.key; | |
| 71 } | |
| 72 }; | |
| 73 | |
| 74 const 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 | |
| 104 template<typename Type> | |
| 105 Type 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 | |
| 127 template<typename KeyType> | |
| 128 void 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 int64_t 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 int64_t t0 = rtc::TimeNanos(); | |
| 163 if (keySort) | |
| 164 { | |
| 165 retVal = webrtc::KeySort(data, key, DataLength, sizeof(LotsOfData<Ke
yType>), | |
| 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 int64_t t1 = rtc::TimeNanos(); | |
| 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[i
ndex].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 / rtc::kNumNanosecsPerMillisec; | |
| 240 printf("Execute time: %.2f s\n\n", (float)executeTime / 1000); | |
| 241 } | |
| 242 | |
| 243 int 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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2546863003:
Delete unused spreadsort implementation. (Closed)
