Mercurial > hg > graal-compiler
view src/share/vm/utilities/quickSort.hpp @ 17106:3d6132d71975
Compiler warning removed (unused import)
author | Stefan Anzinger <stefan.anzinger@oracle.com> |
---|---|
date | Fri, 12 Sep 2014 15:24:00 -0700 |
parents | 3c648b9ad052 |
children |
line wrap: on
line source
/* * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #ifndef SHARE_VM_UTILITIES_QUICKSORT_HPP #define SHARE_VM_UTILITIES_QUICKSORT_HPP #include "memory/allocation.hpp" #include "runtime/globals.hpp" #include "utilities/debug.hpp" class QuickSort : AllStatic { private: template<class T> static void swap(T* array, int x, int y) { T tmp = array[x]; array[x] = array[y]; array[y] = tmp; } // As pivot we use the median of the first, last and middle elements. // We swap in these three values at the right place in the array. This // means that this method not only returns the index of the pivot // element. It also alters the array so that: // array[first] <= array[middle] <= array[last] // A side effect of this is that arrays of length <= 3 are sorted. template<class T, class C> static int find_pivot(T* array, int length, C comparator) { assert(length > 1, "length of array must be > 0"); int middle_index = length / 2; int last_index = length - 1; if (comparator(array[0], array[middle_index]) == 1) { swap(array, 0, middle_index); } if (comparator(array[0], array[last_index]) == 1) { swap(array, 0, last_index); } if (comparator(array[middle_index], array[last_index]) == 1) { swap(array, middle_index, last_index); } // Now the value in the middle of the array is the median // of the fist, last and middle values. Use this as pivot. return middle_index; } template<class T, class C, bool idempotent> static int partition(T* array, int pivot, int length, C comparator) { int left_index = -1; int right_index = length; T pivot_val = array[pivot]; while (true) { do { left_index++; } while (comparator(array[left_index], pivot_val) == -1); do { right_index--; } while (comparator(array[right_index], pivot_val) == 1); if (left_index < right_index) { if (!idempotent || comparator(array[left_index], array[right_index]) != 0) { swap(array, left_index, right_index); } } else { return right_index; } } ShouldNotReachHere(); return 0; } template<class T, class C, bool idempotent> static void inner_sort(T* array, int length, C comparator) { if (length < 2) { return; } int pivot = find_pivot(array, length, comparator); if (length < 4) { // arrays up to length 3 will be sorted after finding the pivot return; } int split = partition<T, C, idempotent>(array, pivot, length, comparator); int first_part_length = split + 1; inner_sort<T, C, idempotent>(array, first_part_length, comparator); inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator); } public: // The idempotent parameter prevents the sort from // reordering a previous valid sort by not swapping // fields that compare as equal. This requires extra // calls to the comparator, so the performance // impact depends on the comparator. template<class T, class C> static void sort(T* array, int length, C comparator, bool idempotent) { // Switch "idempotent" from function paramter to template parameter if (idempotent) { inner_sort<T, C, true>(array, length, comparator); } else { inner_sort<T, C, false>(array, length, comparator); } } // for unit testing #ifndef PRODUCT static void print_array(const char* prefix, int* array, int length); static bool compare_arrays(int* actual, int* expected, int length); template <class C> static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false); static void test_quick_sort(); #endif }; #endif //SHARE_VM_UTILITIES_QUICKSORT_HPP