1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/vm/utilities/quickSort.hpp Wed Apr 27 01:25:04 2016 +0800 1.3 @@ -0,0 +1,138 @@ 1.4 +/* 1.5 + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1.23 + * or visit www.oracle.com if you need additional information or have any 1.24 + * questions. 1.25 + * 1.26 + */ 1.27 + 1.28 +#ifndef SHARE_VM_UTILITIES_QUICKSORT_HPP 1.29 +#define SHARE_VM_UTILITIES_QUICKSORT_HPP 1.30 + 1.31 +#include "memory/allocation.hpp" 1.32 +#include "runtime/globals.hpp" 1.33 +#include "utilities/debug.hpp" 1.34 + 1.35 +class QuickSort : AllStatic { 1.36 + 1.37 + private: 1.38 + template<class T> 1.39 + static void swap(T* array, int x, int y) { 1.40 + T tmp = array[x]; 1.41 + array[x] = array[y]; 1.42 + array[y] = tmp; 1.43 + } 1.44 + 1.45 + // As pivot we use the median of the first, last and middle elements. 1.46 + // We swap in these three values at the right place in the array. This 1.47 + // means that this method not only returns the index of the pivot 1.48 + // element. It also alters the array so that: 1.49 + // array[first] <= array[middle] <= array[last] 1.50 + // A side effect of this is that arrays of length <= 3 are sorted. 1.51 + template<class T, class C> 1.52 + static int find_pivot(T* array, int length, C comparator) { 1.53 + assert(length > 1, "length of array must be > 0"); 1.54 + 1.55 + int middle_index = length / 2; 1.56 + int last_index = length - 1; 1.57 + 1.58 + if (comparator(array[0], array[middle_index]) == 1) { 1.59 + swap(array, 0, middle_index); 1.60 + } 1.61 + if (comparator(array[0], array[last_index]) == 1) { 1.62 + swap(array, 0, last_index); 1.63 + } 1.64 + if (comparator(array[middle_index], array[last_index]) == 1) { 1.65 + swap(array, middle_index, last_index); 1.66 + } 1.67 + // Now the value in the middle of the array is the median 1.68 + // of the fist, last and middle values. Use this as pivot. 1.69 + return middle_index; 1.70 + } 1.71 + 1.72 + template<class T, class C, bool idempotent> 1.73 + static int partition(T* array, int pivot, int length, C comparator) { 1.74 + int left_index = -1; 1.75 + int right_index = length; 1.76 + T pivot_val = array[pivot]; 1.77 + 1.78 + while (true) { 1.79 + do { 1.80 + left_index++; 1.81 + } while (comparator(array[left_index], pivot_val) == -1); 1.82 + do { 1.83 + right_index--; 1.84 + } while (comparator(array[right_index], pivot_val) == 1); 1.85 + 1.86 + if (left_index < right_index) { 1.87 + if (!idempotent || comparator(array[left_index], array[right_index]) != 0) { 1.88 + swap(array, left_index, right_index); 1.89 + } 1.90 + } else { 1.91 + return right_index; 1.92 + } 1.93 + } 1.94 + 1.95 + ShouldNotReachHere(); 1.96 + return 0; 1.97 + } 1.98 + 1.99 + template<class T, class C, bool idempotent> 1.100 + static void inner_sort(T* array, int length, C comparator) { 1.101 + if (length < 2) { 1.102 + return; 1.103 + } 1.104 + int pivot = find_pivot(array, length, comparator); 1.105 + if (length < 4) { 1.106 + // arrays up to length 3 will be sorted after finding the pivot 1.107 + return; 1.108 + } 1.109 + int split = partition<T, C, idempotent>(array, pivot, length, comparator); 1.110 + int first_part_length = split + 1; 1.111 + inner_sort<T, C, idempotent>(array, first_part_length, comparator); 1.112 + inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator); 1.113 + } 1.114 + 1.115 + public: 1.116 + // The idempotent parameter prevents the sort from 1.117 + // reordering a previous valid sort by not swapping 1.118 + // fields that compare as equal. This requires extra 1.119 + // calls to the comparator, so the performance 1.120 + // impact depends on the comparator. 1.121 + template<class T, class C> 1.122 + static void sort(T* array, int length, C comparator, bool idempotent) { 1.123 + // Switch "idempotent" from function paramter to template parameter 1.124 + if (idempotent) { 1.125 + inner_sort<T, C, true>(array, length, comparator); 1.126 + } else { 1.127 + inner_sort<T, C, false>(array, length, comparator); 1.128 + } 1.129 + } 1.130 + 1.131 + // for unit testing 1.132 +#ifndef PRODUCT 1.133 + static void print_array(const char* prefix, int* array, int length); 1.134 + static bool compare_arrays(int* actual, int* expected, int length); 1.135 + template <class C> static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false); 1.136 + static void test_quick_sort(); 1.137 +#endif 1.138 +}; 1.139 + 1.140 + 1.141 +#endif //SHARE_VM_UTILITIES_QUICKSORT_HPP