1 /* 2 * Copyright (c) 2011, 2019, 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_UTILITIES_QUICKSORT_HPP 26 #define SHARE_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> swap(T * array,size_t x,size_t y)36 static void swap(T* array, size_t x, size_t 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> find_pivot(T * array,size_t length,C comparator)49 static size_t find_pivot(T* array, size_t length, C comparator) { 50 assert(length > 1, "length of array must be > 0"); 51 52 size_t middle_index = length / 2; 53 size_t last_index = length - 1; 54 55 if (comparator(array[0], array[middle_index]) > 0) { 56 swap(array, 0, middle_index); 57 } 58 if (comparator(array[0], array[last_index]) > 0) { 59 swap(array, 0, last_index); 60 } 61 if (comparator(array[middle_index], array[last_index]) > 0) { 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<bool idempotent, class T, class C> partition(T * array,size_t pivot,size_t length,C comparator)70 static size_t partition(T* array, size_t pivot, size_t length, C comparator) { 71 size_t left_index = 0; 72 size_t right_index = length - 1; 73 T pivot_val = array[pivot]; 74 75 for ( ; true; ++left_index, --right_index) { 76 for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) { 77 assert(left_index < length, "reached end of partition"); 78 } 79 for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) { 80 assert(right_index > 0, "reached start of partition"); 81 } 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<bool idempotent, class T, class C> inner_sort(T * array,size_t length,C comparator)97 static void inner_sort(T* array, size_t length, C comparator) { 98 if (length < 2) { 99 return; 100 } 101 size_t 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 size_t split = partition<idempotent>(array, pivot, length, comparator); 107 size_t first_part_length = split + 1; 108 inner_sort<idempotent>(array, first_part_length, comparator); 109 inner_sort<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> sort(T * array,size_t length,C comparator,bool idempotent)119 static void sort(T* array, size_t length, C comparator, bool idempotent) { 120 // Switch "idempotent" from function paramter to template parameter 121 if (idempotent) { 122 inner_sort<true>(array, length, comparator); 123 } else { 124 inner_sort<false>(array, length, comparator); 125 } 126 } 127 }; 128 129 130 #endif // SHARE_UTILITIES_QUICKSORT_HPP 131