| 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 |