Mercurial > hg > graal-compiler

comparison src/share/vm/utilities/quickSort.hpp @ 3779:04760e41b01e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
7016112: CMS: crash during promotion testing Summary: Also reviewed by mikael.gerdin@oracle.com; stdlib:qsort() does byte-by-byte swapping on Windows. This leads to pointer shearing. Fix is to implement a quicksort that does full pointer updates. Reviewed-by: never, coleenp, ysr
author brutisso
date Tue, 28 Jun 2011 14:23:27 +0200
parents
children 3c648b9ad052
comparison
equal deleted inserted replaced
3778:5f6f2615433a 3779:04760e41b01e
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 #ifndef SHARE_VM_UTILITIES_QUICKSORT_HPP
26 #define SHARE_VM_UTILITIES_QUICKSORT_HPP
27
28 #include "memory/allocation.hpp"
29 #include "runtime/globals.hpp"
30 #include "utilities/debug.hpp"
31
32 class QuickSort : AllStatic {
33
34 private:
35 template<class T>
36 static void swap(T* array, int x, int y) {
37 T tmp = array[x];
38 array[x] = array[y];
39 array[y] = tmp;
40 }
41
42 // As pivot we use the median of the first, last and middle elements.
43 // We swap in these three values at the right place in the array. This
44 // means that this method not only returns the index of the pivot
45 // element. It also alters the array so that:
46 // array[first] <= array[middle] <= array[last]
47 // A side effect of this is that arrays of length <= 3 are sorted.
48 template<class T, class C>
49 static int find_pivot(T* array, int length, C comparator) {
50 assert(length > 1, "length of array must be > 0");
51
52 int middle_index = length / 2;
53 int last_index = length - 1;
54
55 if (comparator(array[0], array[middle_index]) == 1) {
56 swap(array, 0, middle_index);
57 }
58 if (comparator(array[0], array[last_index]) == 1) {
59 swap(array, 0, last_index);
60 }
61 if (comparator(array[middle_index], array[last_index]) == 1) {
62 swap(array, middle_index, last_index);
63 }
64 // Now the value in the middle of the array is the median
65 // of the fist, last and middle values. Use this as pivot.
66 return middle_index;
67 }
68
69 template<class T, class C, bool idempotent>
70 static int partition(T* array, int pivot, int length, C comparator) {
71 int left_index = -1;
72 int right_index = length;
73 T pivot_val = array[pivot];
74
75 while (true) {
76 do {
77 left_index++;
78 } while (comparator(array[left_index], pivot_val) == -1);
79 do {
80 right_index--;
81 } while (comparator(array[right_index], pivot_val) == 1);
82
83 if (left_index < right_index) {
84 if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {
85 swap(array, left_index, right_index);
86 }
87 } else {
88 return right_index;
89 }
90 }
91
92 ShouldNotReachHere();
93 return 0;
94 }
95
96 template<class T, class C, bool idempotent>
97 static void inner_sort(T* array, int length, C comparator) {
98 if (length < 2) {
99 return;
100 }
101 int pivot = find_pivot(array, length, comparator);
102 if (length < 4) {
103 // arrays up to length 3 will be sorted after finding the pivot
104 return;
105 }
106 int split = partition<T, C, idempotent>(array, pivot, length, comparator);
107 int first_part_length = split + 1;
108 inner_sort<T, C, idempotent>(array, first_part_length, comparator);
109 inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator);
110 }
111
112 public:
113 // The idempotent parameter prevents the sort from
114 // reordering a previous valid sort by not swapping
115 // fields that compare as equal. This requires extra
116 // calls to the comparator, so the performance
117 // impact depends on the comparator.
118 template<class T, class C>
119 static void sort(T* array, int length, C comparator, bool idempotent) {
120 // Switch "idempotent" from function paramter to template parameter
121 if (idempotent) {
122 inner_sort<T, C, true>(array, length, comparator);
123 } else {
124 inner_sort<T, C, false>(array, length, comparator);
125 }
126 }
127
128 // for unit testing
129 #ifndef PRODUCT
130 static void print_array(const char* prefix, int* array, int length);
131 static bool compare_arrays(int* actual, int* expected, int length);
132 template <class C> static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false);
133 static bool test_quick_sort();
134 #endif
135 };
136
137
138 #endif //SHARE_VM_UTILITIES_QUICKSORT_HPP