Mercurial > hg > truffle
annotate src/share/vm/utilities/quickSort.cpp @ 8733:9def4075da6d
8008079: G1: Add nextObject routine to CMBitMapRO and replace nextWord
Summary: Update the task local finger to the start of the next object when marking aborts, in order to avoid the redundant scanning of all 0's when the marking task restarts, if otherwise updating to the next word. In addition, reuse the routine nextObject() in routine iterate().
Reviewed-by: johnc, ysr
Contributed-by: tamao <tao.mao@oracle.com>
| author | tamao |
|---|---|
| date | Tue, 05 Mar 2013 15:36:56 -0800 |
| parents | 3c648b9ad052 |
| children | f2aebc22372a 6f817ce50129 |
| rev | line source |
|---|---|
| 3779 | 1 /* |
| 2 * Copyright (c) 2011, 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" | |
|
4070
6fd81579526f
7102044: G1: VM crashes with assert(old_end != new_end) failed: don't call this otherwise
brutisso
parents:
3981
diff
changeset
|
26 |
|
6fd81579526f
7102044: G1: VM crashes with assert(old_end != new_end) failed: don't call this otherwise
brutisso
parents:
3981
diff
changeset
|
27 /////////////// Unit tests /////////////// |
| 3779 | 28 |
| 29 #ifndef PRODUCT | |
| 30 | |
| 31 #include "runtime/os.hpp" | |
|
4070
6fd81579526f
7102044: G1: VM crashes with assert(old_end != new_end) failed: don't call this otherwise
brutisso
parents:
3981
diff
changeset
|
32 #include "utilities/quickSort.hpp" |
| 3779 | 33 #include <stdlib.h> |
| 34 | |
| 35 static int test_comparator(int a, int b) { | |
| 36 if (a == b) { | |
| 37 return 0; | |
| 38 } | |
| 39 if (a < b) { | |
| 40 return -1; | |
| 41 } | |
| 42 return 1; | |
| 43 } | |
| 44 | |
| 45 static int test_even_odd_comparator(int a, int b) { | |
| 46 bool a_is_odd = (a % 2) == 1; | |
| 47 bool b_is_odd = (b % 2) == 1; | |
| 48 if (a_is_odd == b_is_odd) { | |
| 49 return 0; | |
| 50 } | |
| 51 if (a_is_odd) { | |
| 52 return -1; | |
| 53 } | |
| 54 return 1; | |
| 55 } | |
| 56 | |
| 3981 | 57 extern "C" { |
| 58 static int test_stdlib_comparator(const void* a, const void* b) { | |
| 59 int ai = *(int*)a; | |
| 60 int bi = *(int*)b; | |
| 61 if (ai == bi) { | |
| 62 return 0; | |
| 63 } | |
| 64 if (ai < bi) { | |
| 65 return -1; | |
| 66 } | |
| 67 return 1; | |
| 3779 | 68 } |
| 69 } | |
| 70 | |
| 71 void QuickSort::print_array(const char* prefix, int* array, int length) { | |
| 72 tty->print("%s:", prefix); | |
| 73 for (int i = 0; i < length; i++) { | |
| 74 tty->print(" %d", array[i]); | |
| 75 } | |
| 76 tty->print_cr(""); | |
| 77 } | |
| 78 | |
| 79 bool QuickSort::compare_arrays(int* actual, int* expected, int length) { | |
| 80 for (int i = 0; i < length; i++) { | |
| 81 if (actual[i] != expected[i]) { | |
| 82 print_array("Sorted array ", actual, length); | |
| 83 print_array("Expected array", expected, length); | |
| 84 return false; | |
| 85 } | |
| 86 } | |
| 87 return true; | |
| 88 } | |
| 89 | |
| 90 template <class C> | |
| 91 bool QuickSort::sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent) { | |
| 92 sort<int, C>(arrayToSort, length, comparator, idempotent); | |
| 93 return compare_arrays(arrayToSort, expectedResult, length); | |
| 94 } | |
| 95 | |
| 4708 | 96 void QuickSort::test_quick_sort() { |
| 3779 | 97 { |
| 98 int* test_array = NULL; | |
| 99 int* expected_array = NULL; | |
| 100 assert(sort_and_compare(test_array, expected_array, 0, test_comparator), "Empty array not handled"); | |
| 101 } | |
| 102 { | |
| 103 int test_array[] = {3}; | |
| 104 int expected_array[] = {3}; | |
| 105 assert(sort_and_compare(test_array, expected_array, 1, test_comparator), "Single value array not handled"); | |
| 106 } | |
| 107 { | |
| 108 int test_array[] = {3,2}; | |
| 109 int expected_array[] = {2,3}; | |
| 110 assert(sort_and_compare(test_array, expected_array, 2, test_comparator), "Array with 2 values not correctly sorted"); | |
| 111 } | |
| 112 { | |
| 113 int test_array[] = {3,2,1}; | |
| 114 int expected_array[] = {1,2,3}; | |
| 115 assert(sort_and_compare(test_array, expected_array, 3, test_comparator), "Array with 3 values not correctly sorted"); | |
| 116 } | |
| 117 { | |
| 118 int test_array[] = {4,3,2,1}; | |
| 119 int expected_array[] = {1,2,3,4}; | |
| 120 assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "Array with 4 values not correctly sorted"); | |
| 121 } | |
| 122 { | |
| 123 int test_array[] = {7,1,5,3,6,9,8,2,4,0}; | |
| 124 int expected_array[] = {0,1,2,3,4,5,6,7,8,9}; | |
| 125 assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Array with 10 values not correctly sorted"); | |
| 126 } | |
| 127 { | |
| 128 int test_array[] = {4,4,1,4}; | |
| 129 int expected_array[] = {1,4,4,4}; | |
| 130 assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "3 duplicates not sorted correctly"); | |
| 131 } | |
| 132 { | |
| 133 int test_array[] = {0,1,2,3,4,5,6,7,8,9}; | |
| 134 int expected_array[] = {0,1,2,3,4,5,6,7,8,9}; | |
| 135 assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Already sorted array not correctly sorted"); | |
| 136 } | |
| 137 { | |
| 138 // one of the random arrays that found an issue in the partion method. | |
| 139 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}; | |
| 140 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}; | |
| 141 assert(sort_and_compare(test_array, expected_array, 42, test_comparator), "Not correctly sorted"); | |
| 142 } | |
| 143 { | |
| 144 int test_array[] = {2,8,1,4}; | |
| 145 int expected_array[] = {1,4,2,8}; | |
| 146 assert(sort_and_compare(test_array, expected_array, 4, test_even_odd_comparator), "Even/odd not sorted correctly"); | |
| 147 } | |
| 148 { // Some idempotent tests | |
| 149 { | |
| 150 // An array of lenght 3 is only sorted by find_pivot. Make sure that it is idempotent. | |
| 151 int test_array[] = {1,4,8}; | |
| 152 int expected_array[] = {1,4,8}; | |
| 153 assert(sort_and_compare(test_array, expected_array, 3, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 154 } | |
| 155 { | |
| 156 int test_array[] = {1,7,9,4,8,2}; | |
| 157 int expected_array[] = {1,7,9,4,8,2}; | |
| 158 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 159 } | |
| 160 { | |
| 161 int test_array[] = {1,9,7,4,2,8}; | |
| 162 int expected_array[] = {1,9,7,4,2,8}; | |
| 163 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 164 } | |
| 165 { | |
| 166 int test_array[] = {7,9,1,2,8,4}; | |
| 167 int expected_array[] = {7,9,1,2,8,4}; | |
| 168 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 169 } | |
| 170 { | |
| 171 int test_array[] = {7,1,9,2,4,8}; | |
| 172 int expected_array[] = {7,1,9,2,4,8}; | |
| 173 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 174 } | |
| 175 { | |
| 176 int test_array[] = {9,1,7,4,8,2}; | |
| 177 int expected_array[] = {9,1,7,4,8,2}; | |
| 178 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 179 } | |
| 180 { | |
| 181 int test_array[] = {9,7,1,4,2,8}; | |
| 182 int expected_array[] = {9,7,1,4,2,8}; | |
| 183 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 184 } | |
| 185 } | |
| 186 | |
| 187 // test sorting random arrays | |
| 188 for (int i = 0; i < 1000; i++) { | |
| 189 int length = os::random() % 100; | |
| 190 int* test_array = new int[length]; | |
| 191 int* expected_array = new int[length]; | |
| 192 for (int j = 0; j < length; j++) { | |
| 193 // Choose random values, but get a chance of getting duplicates | |
| 194 test_array[j] = os::random() % (length * 2); | |
| 195 expected_array[j] = test_array[j]; | |
| 196 } | |
| 197 | |
| 198 // Compare sorting to stdlib::qsort() | |
| 199 qsort(expected_array, length, sizeof(int), test_stdlib_comparator); | |
| 200 assert(sort_and_compare(test_array, expected_array, length, test_comparator), "Random array not correctly sorted"); | |
| 201 | |
| 202 // Make sure sorting is idempotent. | |
| 203 // Both test_array and expected_array are sorted by the test_comparator. | |
| 204 // Now sort them once with the test_even_odd_comparator. Then sort the | |
| 205 // test_array one more time with test_even_odd_comparator and verify that | |
| 206 // it is idempotent. | |
| 207 sort(expected_array, length, test_even_odd_comparator, true); | |
| 208 sort(test_array, length, test_even_odd_comparator, true); | |
| 209 assert(compare_arrays(test_array, expected_array, length), "Sorting identical arrays rendered different results"); | |
| 210 sort(test_array, length, test_even_odd_comparator, true); | |
| 211 assert(compare_arrays(test_array, expected_array, length), "Sorting already sorted array changed order of elements - not idempotent"); | |
| 212 | |
| 213 delete[] test_array; | |
| 214 delete[] expected_array; | |
| 215 } | |
| 216 } | |
| 217 | |
| 218 #endif |