OLD | NEW |
(Empty) | |
| 1 /* Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
| 2 * Use of this source code is governed by a BSD-style license that can be |
| 3 * found in the LICENSE file. |
| 4 */ |
| 5 |
| 6 #include "quick_sort_test.h" |
| 7 #include "cgpt_test.h" |
| 8 #include "quick_sort.h" |
| 9 #include "utility.h" |
| 10 |
| 11 #define MAX_NUMBER_OF_TEST_ELEMENTS 16 |
| 12 |
| 13 /* callback function for QuickSort. |
| 14 * To get ascent results, this function returns 1 if a < b. |
| 15 * Returns 0 if a >= b. */ |
| 16 int ascent_compare(const void *a_, const void *b_) { |
| 17 const int *a = a_; |
| 18 const int *b = b_; |
| 19 if (*a < *b) return 1; |
| 20 return 0; |
| 21 } |
| 22 |
| 23 /* Used to verify if an array is sorted as ascent which means |
| 24 * 'a' (previous element) is smaller than 'b' (back element). |
| 25 * Returns 1 for ture, 0 for false. */ |
| 26 int ascent_verify(const int a, const int b) { |
| 27 return (a <= b) ? 1 : 0; |
| 28 } |
| 29 |
| 30 /* callback function for QuickSort. |
| 31 * To get descent results, this function returns 1 if a > b. |
| 32 * Returns 0 if a <= b. */ |
| 33 int descent_compare(const void *a_, const void *b_) { |
| 34 const int *a = a_; |
| 35 const int *b = b_; |
| 36 if (*a > *b) return 1; |
| 37 return 0; |
| 38 } |
| 39 |
| 40 /* Used to verify if an array is sorted as descent which means |
| 41 * 'a' (previous element) is lager than 'b' (back element). |
| 42 * Returns 1 for ture, 0 for false. */ |
| 43 int descent_verify(const int a, const int b) { |
| 44 return (a >= b) ? 1 : 0; |
| 45 } |
| 46 |
| 47 /* We provide 2 ways to sort the array. One for ascent, and another for descent. |
| 48 */ |
| 49 struct { |
| 50 int (*compare)(const void *a, const void *b); |
| 51 int (*verify)(const int a, const int b); |
| 52 } directions[] = { |
| 53 { ascent_compare, ascent_verify, }, |
| 54 { descent_compare, descent_verify, }, |
| 55 }; |
| 56 |
| 57 /* Here are the fixed patterns to test. Especially those corner cases that |
| 58 * random test cannot easily reproduce. */ |
| 59 struct { |
| 60 int number; /* number of integers saved in array */ |
| 61 int unsorted[MAX_NUMBER_OF_TEST_ELEMENTS]; |
| 62 } test_data[] = { |
| 63 {0, {}, }, |
| 64 {1, {0, }, }, |
| 65 {2, {1, 1,}, }, |
| 66 {2, {1, 2,}, }, |
| 67 {2, {2, 1,}, }, |
| 68 {3, {1, 3, 2}, }, |
| 69 {3, {2, 1, 3}, }, |
| 70 {4, {1, 1, 3, 2}, }, |
| 71 {4, {3, 1, 2, 2}, }, |
| 72 {4, {1, 3, 3, 2}, }, |
| 73 {5, {1, 2, 3, 4, 5}, }, |
| 74 {5, {5, 5, 5, 3, 3}, }, |
| 75 {5, {5, 1, 3, 2, 4}, }, |
| 76 {5, {4, 5, 2, 3, 1}, }, |
| 77 {6, {5, 4, 3, 2, 1, 6}, }, |
| 78 {7, {5, 4, 3, 2, 1, 6, 7}, }, |
| 79 {7, {2, 5, 4, 6, 7, 1, 3}, }, |
| 80 {7, {7, 6, 1, 5, 3, 4, 2}, }, |
| 81 }; |
| 82 |
| 83 int TestQuickSortFixed() { |
| 84 int data; |
| 85 int dir; |
| 86 int sorted[MAX_NUMBER_OF_TEST_ELEMENTS]; |
| 87 |
| 88 for (dir = 0; dir < ARRAY_SIZE(directions); ++dir) { |
| 89 for (data = 0; data < ARRAY_SIZE(test_data); ++data) { |
| 90 int i; |
| 91 for (i = 0; i < test_data[data].number; ++i) |
| 92 sorted[i] = test_data[data].unsorted[i]; |
| 93 |
| 94 QuickSort(sorted, test_data[data].number, sizeof(int), |
| 95 directions[dir].compare); |
| 96 |
| 97 for (i = 0; i < test_data[data].number - 1; ++i) |
| 98 EXPECT(directions[dir].verify(sorted[i], sorted[i + 1])); |
| 99 } |
| 100 } |
| 101 |
| 102 return TEST_OK; |
| 103 } |
| 104 |
| 105 /* Random test. We don't really need a truely random test. A pseudo-random |
| 106 * pattern with large 'try_num' is good enough to test. |
| 107 */ |
| 108 static uint32_t Random() { |
| 109 static uint32_t seed = 0x600613; /* 'GOOGLE' :-) */ |
| 110 return (seed = seed * 701 + 179); |
| 111 } |
| 112 |
| 113 int TestQuickSortRandom() { |
| 114 int try_num; |
| 115 int i, dir; |
| 116 |
| 117 for (dir = 0; dir < ARRAY_SIZE(directions); ++dir) { |
| 118 for (try_num = 100000; try_num > 0; --try_num) { |
| 119 int number_of_elements; |
| 120 int *p; |
| 121 |
| 122 number_of_elements = Random() % 181; |
| 123 p = Malloc(sizeof(int) * number_of_elements); |
| 124 for (i = 0; i < number_of_elements; ++i) |
| 125 p[i] = Random() % 173; |
| 126 |
| 127 QuickSort(p, number_of_elements, sizeof(int), directions[dir].compare); |
| 128 |
| 129 for (i = 0; i < number_of_elements - 1; ++i) |
| 130 EXPECT(directions[dir].verify(p[i], p[i + 1])); |
| 131 |
| 132 Free(p); |
| 133 } |
| 134 } |
| 135 |
| 136 return TEST_OK; |
| 137 } |
OLD | NEW |