SortTest.cpp revision e0e7cfe44bb9d66d76120a79e5275c294bacaa22 
1
2/*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8#include "Test.h"
9#include "SkRandom.h"
10#include "SkTSort.h"
11
12extern "C" {
13    static int compare_int(const void* a, const void* b) {
14        return *(const int*)a - *(const int*)b;
15    }
16}
17
18static void rand_array(SkRandom& rand, int array[], int n) {
19    for (int j = 0; j < n; j++) {
20        array[j] = rand.nextS() & 0xFF;
21    }
22}
23
24static void check_sort(skiatest::Reporter* reporter, const char label[],
25                       const int array[], const int reference[], int n) {
26    for (int j = 0; j < n; ++j) {
27        if (array[j] != reference[j]) {
28            SkString str;
29            str.printf("%sSort [%d] failed %d %d", label, n, array[j], reference[j]);
30            reporter->reportFailed(str);
31        }
32    }
33}
34
35static void TestSort(skiatest::Reporter* reporter) {
36    /** An array of random numbers to be sorted. */
37    int randomArray[500];
38    /** The reference sort of the random numbers. */
39    int sortedArray[SK_ARRAY_COUNT(randomArray)];
40    /** The random numbers are copied into this array, sorted by an SkSort,
41        then this array is compared against the reference sort. */
42    int workingArray[SK_ARRAY_COUNT(randomArray)];
43    SkRandom    rand;
44
45    for (int i = 0; i < 10000; i++) {
46        int count = rand.nextRangeU(1, SK_ARRAY_COUNT(randomArray));
47        rand_array(rand, randomArray, count);
48
49        // Use qsort as the reference sort.
50        memcpy(sortedArray, randomArray, sizeof(randomArray));
51        qsort(sortedArray, count, sizeof(sortedArray[0]), compare_int);
52
53        memcpy(workingArray, randomArray, sizeof(randomArray));
54        SkTHeapSort<int>(workingArray, count);
55        check_sort(reporter, "Heap", workingArray, sortedArray, count);
56
57        memcpy(workingArray, randomArray, sizeof(randomArray));
58        SkTQSort<int>(workingArray, workingArray + count - 1);
59        check_sort(reporter, "Quick", workingArray, sortedArray, count);
60    }
61}
62
63// need tests for SkStrSearch
64
65#include "TestClassDef.h"
66DEFINE_TESTCLASS("Sort", SortTestClass, TestSort)
67