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 "runtime/globals.hpp" 29 #include "utilities/debug.hpp" 30 31 class quicksort { 32 33 private: 34 template<class T> 35 static void swap(T* array, int x, int y) { 36 T tmp = array[x]; 37 array[x] = array[y]; 38 array[y] = tmp; 39 } 40 41 // As pivot we use the median of the first, last and middle elements. 42 // We swap in these three values at the right place in the array. This 43 // means that this method not only returns the index of the pivot 44 // element. It also alters the array so that: 45 // array[first] <= array[middle] <= array[last] 46 // A side effect of this is that arrays of length <= 3 are sorted. 47 template<class T, class C> 48 static int find_pivot(T* array, int length, C comparer) { 49 assert(length > 1, "length of array must be > 0"); 50 51 int middle_index = length / 2; 52 int last_index = length - 1; 53 54 if (comparer(array[0], array[middle_index]) == 1) { 55 swap(array, 0, middle_index); 56 } 57 if (comparer(array[0], array[last_index]) == 1) { 58 swap(array, 0, last_index); 59 } 60 if (comparer(array[middle_index], array[last_index]) == 1) { 61 swap(array, middle_index, last_index); 62 } 63 // Now the value in the middle of the array is the median 64 // of the fist, last and middle values. Use this as pivot. 65 return middle_index; 66 } 67 68 template<class T, class C, bool idempotent> 69 static int partition(T* array, int pivot, int length, C comparer) { 70 int left_index = -1; 71 int right_index = length; 72 T pivot_val = array[pivot]; 73 74 while (true) { 75 do { 76 left_index++; 77 } while (comparer(array[left_index], pivot_val) == -1); 78 do { 79 right_index--; 80 } while (comparer(array[right_index], pivot_val) == 1); 81 82 if (left_index < right_index) { 83 if (!idempotent || comparer(array[left_index], array[right_index]) != 0) { 84 swap(array, left_index, right_index); 85 } 86 } else { 87 return right_index; 88 } 89 } 90 91 ShouldNotReachHere(); 92 return 0; 93 } 94 95 public: 96 // The idempotent parameter prevents the sort from 97 // reordering a previous valid sort by not swapping 98 // fields that compare as equal. This requires extra 99 // calls to the comparer, so the performance 100 // impact depends on the comparer. 101 template<class T, class C, bool idempotent> 102 static void sort(T* array, int length, C comparer) { 103 if (length < 2) { 104 return; 105 } 106 int pivot = find_pivot(array, length, comparer); 107 if (length < 4) { 108 // arrays up to length 3 will be sorted after finding the pivot 109 return; 110 } 111 int split = partition<T, C, idempotent>(array, pivot, length, comparer); 112 int first_part_length = split + 1; 113 sort<T, C, idempotent>(array, first_part_length, comparer); 114 sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparer); 115 } 116 117 // for unit testing 118 #ifndef PRODUCT 119 static void print_array(const char* prefix, int* array, int length); 120 static bool compare_arrays(int* actual, int* expected, int length); 121 template <class C> static bool sortAndCompare(int* arrayToSort, int* expectedResult, int length, C comparer, bool idempotent = false); 122 static bool testQuicksort(); 123 #endif 124 }; 125 126 127 #endif //SHARE_VM_UTILITIES_QUICKSORT_HPP