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 
test_comparator(int a,int b)31 static 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 
compare_arrays(int * actual,int * expected,size_t length)41 static 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 
50 template <class C>
sort_and_compare(int * arrayToSort,int * expectedResult,size_t length,C comparator,bool idempotent=false)51 static 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 
test_even_odd_comparator(int a,int b)56 static 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 
68 extern "C" {
test_stdlib_comparator(const void * a,const void * b)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 
TEST(QuickSort,quicksort)82 TEST(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 
TEST(QuickSort,idempotent)136 TEST(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 
TEST(QuickSort,random)175 TEST(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