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