Mercurial > hg > truffle
comparison src/share/vm/utilities/quickSort.hpp @ 3779:04760e41b01e
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 |