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