1/* 2 * Copyright (c) 2011, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25#include "precompiled.hpp" 26#include "memory/allocation.inline.hpp" 27#include "runtime/os.hpp" 28#include "utilities/quickSort.hpp" 29#include "unittest.hpp" 30 31static int test_comparator(int a, int b) { 32 if (a == b) { 33 return 0; 34 } 35 if (a < b) { 36 return -1; 37 } 38 return 1; 39} 40 41static bool compare_arrays(int* actual, int* expected, size_t length) { 42 for (size_t i = 0; i < length; i++) { 43 if (actual[i] != expected[i]) { 44 return false; 45 } 46 } 47 return true; 48} 49 50template <class C> 51static bool sort_and_compare(int* arrayToSort, int* expectedResult, size_t length, C comparator, bool idempotent = false) { 52 QuickSort::sort(arrayToSort, length, comparator, idempotent); 53 return compare_arrays(arrayToSort, expectedResult, length); 54} 55 56static int test_even_odd_comparator(int a, int b) { 57 bool a_is_odd = ((a % 2) == 1); 58 bool b_is_odd = ((b % 2) == 1); 59 if (a_is_odd == b_is_odd) { 60 return 0; 61 } 62 if (a_is_odd) { 63 return -1; 64 } 65 return 1; 66} 67 68extern "C" { 69 static int test_stdlib_comparator(const void* a, const void* b) { 70 int ai = *(int*)a; 71 int bi = *(int*)b; 72 if (ai == bi) { 73 return 0; 74 } 75 if (ai < bi) { 76 return -1; 77 } 78 return 1; 79 } 80} 81 82TEST(QuickSort, quicksort) { 83 { 84 int* test_array = NULL; 85 int* expected_array = NULL; 86 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 0, test_comparator)); 87 } 88 { 89 int test_array[] = {3}; 90 int expected_array[] = {3}; 91 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 1, test_comparator)); 92 } 93 { 94 int test_array[] = {3,2}; 95 int expected_array[] = {2,3}; 96 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 2, test_comparator)); 97 } 98 { 99 int test_array[] = {3,2,1}; 100 int expected_array[] = {1,2,3}; 101 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 3, test_comparator)); 102 } 103 { 104 int test_array[] = {4,3,2,1}; 105 int expected_array[] = {1,2,3,4}; 106 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 4, test_comparator)); 107 } 108 { 109 int test_array[] = {7,1,5,3,6,9,8,2,4,0}; 110 int expected_array[] = {0,1,2,3,4,5,6,7,8,9}; 111 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 10, test_comparator)); 112 } 113 { 114 int test_array[] = {4,4,1,4}; 115 int expected_array[] = {1,4,4,4}; 116 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 4, test_comparator)); 117 } 118 { 119 int test_array[] = {0,1,2,3,4,5,6,7,8,9}; 120 int expected_array[] = {0,1,2,3,4,5,6,7,8,9}; 121 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 10, test_comparator)); 122 } 123 { 124 // one of the random arrays that found an issue in the partition method. 125 int test_array[] = {76,46,81,8,64,56,75,11,51,55,11,71,59,27,9,64,69,75,21,25,39,40,44,32,7,8,40,41,24,78,24,74,9,65,28,6,40,31,22,13,27,82}; 126 int expected_array[] = {6,7,8,8,9,9,11,11,13,21,22,24,24,25,27,27,28,31,32,39,40,40,40,41,44,46,51,55,56,59,64,64,65,69,71,74,75,75,76,78,81,82}; 127 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 42, test_comparator)); 128 } 129 { 130 int test_array[] = {2,8,1,4}; 131 int expected_array[] = {1,4,2,8}; 132 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 4, test_even_odd_comparator)); 133 } 134} 135 136TEST(QuickSort, idempotent) { 137 { 138 // An array of lenght 3 is only sorted by find_pivot. Make sure that it is idempotent. 139 int test_array[] = {1, 4, 8}; 140 int expected_array[] = {1, 4, 8}; 141 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 3, test_even_odd_comparator, true)); 142 } 143 { 144 int test_array[] = {1, 7, 9, 4, 8, 2}; 145 int expected_array[] = {1, 7, 9, 4, 8, 2}; 146 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true)); 147 } 148 { 149 int test_array[] = {1, 9, 7, 4, 2, 8}; 150 int expected_array[] = {1, 9, 7, 4, 2, 8}; 151 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true)); 152 } 153 { 154 int test_array[] = {7, 9, 1, 2, 8, 4}; 155 int expected_array[] = {7, 9, 1, 2, 8, 4}; 156 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true)); 157 } 158 { 159 int test_array[] = {7, 1, 9, 2, 4, 8}; 160 int expected_array[] = {7, 1, 9, 2, 4, 8}; 161 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true)); 162 } 163 { 164 int test_array[] = {9, 1, 7, 4, 8, 2}; 165 int expected_array[] = {9, 1, 7, 4, 8, 2}; 166 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true)); 167 } 168 { 169 int test_array[] = {9, 7, 1, 4, 2, 8}; 170 int expected_array[] = {9, 7, 1, 4, 2, 8}; 171 EXPECT_TRUE(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true)); 172 } 173} 174 175TEST(QuickSort, random) { 176 for (int i = 0; i < 1000; i++) { 177 size_t length = os::random() % 100; 178 int* test_array = NEW_C_HEAP_ARRAY(int, length, mtInternal); 179 int* expected_array = NEW_C_HEAP_ARRAY(int, length, mtInternal); 180 for (size_t j = 0; j < length; j++) { 181 // Choose random values, but get a chance of getting duplicates 182 test_array[j] = os::random() % (length * 2); 183 expected_array[j] = test_array[j]; 184 } 185 186 // Compare sorting to stdlib::qsort() 187 qsort(expected_array, length, sizeof(int), test_stdlib_comparator); 188 EXPECT_TRUE(sort_and_compare(test_array, expected_array, length, test_comparator)); 189 190 // Make sure sorting is idempotent. 191 // Both test_array and expected_array are sorted by the test_comparator. 192 // Now sort them once with the test_even_odd_comparator. Then sort the 193 // test_array one more time with test_even_odd_comparator and verify that 194 // it is idempotent. 195 QuickSort::sort(expected_array, length, test_even_odd_comparator, true); 196 QuickSort::sort(test_array, length, test_even_odd_comparator, true); 197 EXPECT_TRUE(compare_arrays(test_array, expected_array, length)); 198 QuickSort::sort(test_array, length, test_even_odd_comparator, true); 199 EXPECT_TRUE(compare_arrays(test_array, expected_array, length)); 200 201 FREE_C_HEAP_ARRAY(int, test_array); 202 FREE_C_HEAP_ARRAY(int, expected_array); 203 } 204} 205