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