blob: 65c48639a2d70332419b1a90c1660dbfd4212d08 [file] [log] [blame]
epoger@google.comec3ed6a2011-07-28 14:26:00 +00001
2/*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
reed@android.com5e5adfd2009-03-07 03:39:23 +00008#include "Test.h"
9#include "SkRandom.h"
mike@reedtribe.orge60b9102012-07-09 01:53:07 +000010#include "SkChecksum.h"
reed@android.comeff416b2009-03-18 03:08:15 +000011#include "SkTSort.h"
reed@android.com5e5adfd2009-03-07 03:39:23 +000012
mike@reedtribe.orge60b9102012-07-09 01:53:07 +000013// assert that as we change values (from 0 to non-zero) in our buffer, we
14// get a different value
15static void test_checksum(skiatest::Reporter* reporter, size_t size) {
16 SkAutoMalloc storage(size);
17 uint32_t* ptr = (uint32_t*)storage.get();
18 char* cptr = (char*)ptr;
19
20 sk_bzero(ptr, size);
21 uint32_t prev = 0;
22 for (size_t i = 0; i < size; ++i) {
23 cptr[i] = 0x5B; // just need some non-zero value here
24 uint32_t curr = SkChecksum::Compute(ptr, size);
25 REPORTER_ASSERT(reporter, prev != curr);
26 prev = curr;
27 }
28}
29
30static void test_checksum(skiatest::Reporter* reporter) {
31 REPORTER_ASSERT(reporter, SkChecksum::Compute(NULL, 0) == 0);
32
33 for (size_t size = 4; size <= 1000; size += 4) {
34 test_checksum(reporter, size);
35 }
36}
37
reed@android.com5e5adfd2009-03-07 03:39:23 +000038extern "C" {
caryclark@google.com42639cd2012-06-06 12:03:39 +000039 static int compare_int(const void* a, const void* b) {
reed@android.com5e5adfd2009-03-07 03:39:23 +000040 return *(const int*)a - *(const int*)b;
41 }
42}
43
reed@android.comeff416b2009-03-18 03:08:15 +000044static void rand_array(SkRandom& rand, int array[], int n) {
45 for (int j = 0; j < n; j++) {
46 array[j] = rand.nextS() & 0xFF;
47 }
48}
49
50static void check_sort(skiatest::Reporter* reporter, const char label[],
51 const int array[], int n) {
52 for (int j = 1; j < n; j++) {
53 if (array[j-1] > array[j]) {
54 SkString str;
55 str.printf("%sSort [%d] failed %d %d", label, n,
56 array[j-1], array[j]);
57 reporter->reportFailed(str);
58 }
59 }
60}
61
reed@android.com5e5adfd2009-03-07 03:39:23 +000062static void TestSort(skiatest::Reporter* reporter) {
reed@android.comeff416b2009-03-18 03:08:15 +000063 int array[500];
reed@android.com5e5adfd2009-03-07 03:39:23 +000064 SkRandom rand;
65
reed@android.comeff416b2009-03-18 03:08:15 +000066 for (int i = 0; i < 10000; i++) {
67 int count = rand.nextRangeU(1, SK_ARRAY_COUNT(array));
68
69 rand_array(rand, array, count);
reed@android.comeff416b2009-03-18 03:08:15 +000070 SkTHeapSort<int>(array, count);
71 check_sort(reporter, "Heap", array, count);
rileya@google.com5ee3f672012-08-28 14:40:49 +000072
73 rand_array(rand, array, count);
74 SkTQSort<int>(array, array + count - 1);
75 check_sort(reporter, "Quick", array, count);
reed@android.com5e5adfd2009-03-07 03:39:23 +000076 }
caryclark@google.com42639cd2012-06-06 12:03:39 +000077 if (false) { // avoid bit rot, suppress warning
78 compare_int(array, array);
79 }
rmistry@google.comd6176b02012-08-23 18:14:13 +000080
mike@reedtribe.orge60b9102012-07-09 01:53:07 +000081 test_checksum(reporter);
reed@android.com5e5adfd2009-03-07 03:39:23 +000082}
83
84// need tests for SkStrSearch
85
86#include "TestClassDef.h"
87DEFINE_TESTCLASS("Sort", SortTestClass, TestSort)