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