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