1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7e4fafb146e85cdfcf9d5418597b6818aa0754adatfarina@chromium.org 85e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com#include "SkRandom.h" 9eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com#include "SkTSort.h" 108f6884aab8aecd7657cf3f9cdbc682f0deca29c5tfarina@chromium.org#include "Test.h" 115e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com 125e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.comextern "C" { 1342639cddc33746b351bbf07c540711eefffe191acaryclark@google.com static int compare_int(const void* a, const void* b) { 145e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com return *(const int*)a - *(const int*)b; 155e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com } 165e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com} 175e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com 18e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.orgstatic void rand_array(SkRandom& rand, int array[], int n) { 19eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com for (int j = 0; j < n; j++) { 20eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com array[j] = rand.nextS() & 0xFF; 21eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com } 22eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com} 23eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com 24eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.comstatic void check_sort(skiatest::Reporter* reporter, const char label[], 257c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com const int array[], const int reference[], int n) { 267c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com for (int j = 0; j < n; ++j) { 277c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com if (array[j] != reference[j]) { 28a9325fa237dde2654bc841c2bb0a05fc3e57696ahalcanary@google.com ERRORF(reporter, "%sSort [%d] failed %d %d", 29a9325fa237dde2654bc841c2bb0a05fc3e57696ahalcanary@google.com label, n, array[j], reference[j]); 30eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com } 31eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com } 32eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com} 33eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com 34e4fafb146e85cdfcf9d5418597b6818aa0754adatfarina@chromium.orgDEF_TEST(Sort, reporter) { 357c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com /** An array of random numbers to be sorted. */ 367c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com int randomArray[500]; 377c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com /** The reference sort of the random numbers. */ 387c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com int sortedArray[SK_ARRAY_COUNT(randomArray)]; 397c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com /** The random numbers are copied into this array, sorted by an SkSort, 407c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com then this array is compared against the reference sort. */ 417c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com int workingArray[SK_ARRAY_COUNT(randomArray)]; 42e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom rand; 435e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com 44eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com for (int i = 0; i < 10000; i++) { 457c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com int count = rand.nextRangeU(1, SK_ARRAY_COUNT(randomArray)); 467c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com rand_array(rand, randomArray, count); 474024f32d99b63a599c544a49f526e53c25135159skia.committer@gmail.com 487c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com // Use qsort as the reference sort. 497c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com memcpy(sortedArray, randomArray, sizeof(randomArray)); 507c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com qsort(sortedArray, count, sizeof(sortedArray[0]), compare_int); 51eff416bec1bc08685af1dc4265b9d860e43b8240reed@android.com 527c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com memcpy(workingArray, randomArray, sizeof(randomArray)); 537c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com SkTHeapSort<int>(workingArray, count); 547c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com check_sort(reporter, "Heap", workingArray, sortedArray, count); 555ee3f67ce35f19f6e5ef44b67db62e964f77d69drileya@google.com 567c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com memcpy(workingArray, randomArray, sizeof(randomArray)); 577c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com SkTQSort<int>(workingArray, workingArray + count - 1); 587c56c16322ff64de969450cc6dc30605e8537a02bungeman@google.com check_sort(reporter, "Quick", workingArray, sortedArray, count); 5942639cddc33746b351bbf07c540711eefffe191acaryclark@google.com } 605e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com} 615e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com 625e5adfd12cc2cb194db971708cd7f34ff47e10b4reed@android.com// need tests for SkStrSearch 63