12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 |
- /*
- * Copyright 2011 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "include/utils/SkRandom.h"
- #include "src/core/SkTSort.h"
- #include "tests/Test.h"
- #include <stdlib.h>
- extern "C" {
- static int compare_int(const void* a, const void* b) {
- return *(const int*)a - *(const int*)b;
- }
- }
- static void rand_array(SkRandom& rand, int array[], int n) {
- for (int j = 0; j < n; j++) {
- array[j] = rand.nextS() & 0xFF;
- }
- }
- static void check_sort(skiatest::Reporter* reporter, const char label[],
- const int array[], const int reference[], int n) {
- for (int j = 0; j < n; ++j) {
- if (array[j] != reference[j]) {
- ERRORF(reporter, "%sSort [%d] failed %d %d",
- label, n, array[j], reference[j]);
- }
- }
- }
- DEF_TEST(Sort, reporter) {
- /** An array of random numbers to be sorted. */
- int randomArray[500];
- /** The reference sort of the random numbers. */
- int sortedArray[SK_ARRAY_COUNT(randomArray)];
- /** The random numbers are copied into this array, sorted by an SkSort,
- then this array is compared against the reference sort. */
- int workingArray[SK_ARRAY_COUNT(randomArray)];
- SkRandom rand;
- for (int i = 0; i < 10000; i++) {
- int count = rand.nextRangeU(1, SK_ARRAY_COUNT(randomArray));
- rand_array(rand, randomArray, count);
- // Use qsort as the reference sort.
- memcpy(sortedArray, randomArray, sizeof(randomArray));
- qsort(sortedArray, count, sizeof(sortedArray[0]), compare_int);
- memcpy(workingArray, randomArray, sizeof(randomArray));
- SkTHeapSort<int>(workingArray, count);
- check_sort(reporter, "Heap", workingArray, sortedArray, count);
- memcpy(workingArray, randomArray, sizeof(randomArray));
- SkTQSort<int>(workingArray, workingArray + count - 1);
- check_sort(reporter, "Quick", workingArray, sortedArray, count);
- }
- }
- // need tests for SkStrSearch
|