Wed, 14 Dec 2011 12:15:26 +0100
7121373: Clean up CollectedHeap::is_in
Summary: Fixed G1CollectedHeap::is_in, added tests, cleaned up comments and made Space::is_in pure virtual.
Reviewed-by: brutisso, tonyp, jcoomes
brutisso@2976 | 1 | /* |
brutisso@2976 | 2 | * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. |
brutisso@2976 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
brutisso@2976 | 4 | * |
brutisso@2976 | 5 | * This code is free software; you can redistribute it and/or modify it |
brutisso@2976 | 6 | * under the terms of the GNU General Public License version 2 only, as |
brutisso@2976 | 7 | * published by the Free Software Foundation. |
brutisso@2976 | 8 | * |
brutisso@2976 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
brutisso@2976 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
brutisso@2976 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
brutisso@2976 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
brutisso@2976 | 13 | * accompanied this code). |
brutisso@2976 | 14 | * |
brutisso@2976 | 15 | * You should have received a copy of the GNU General Public License version |
brutisso@2976 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
brutisso@2976 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
brutisso@2976 | 18 | * |
brutisso@2976 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
brutisso@2976 | 20 | * or visit www.oracle.com if you need additional information or have any |
brutisso@2976 | 21 | * questions. |
brutisso@2976 | 22 | * |
brutisso@2976 | 23 | */ |
brutisso@2976 | 24 | |
brutisso@2976 | 25 | #ifndef SHARE_VM_UTILITIES_QUICKSORT_HPP |
brutisso@2976 | 26 | #define SHARE_VM_UTILITIES_QUICKSORT_HPP |
brutisso@2976 | 27 | |
brutisso@2976 | 28 | #include "memory/allocation.hpp" |
brutisso@2976 | 29 | #include "runtime/globals.hpp" |
brutisso@2976 | 30 | #include "utilities/debug.hpp" |
brutisso@2976 | 31 | |
brutisso@2976 | 32 | class QuickSort : AllStatic { |
brutisso@2976 | 33 | |
brutisso@2976 | 34 | private: |
brutisso@2976 | 35 | template<class T> |
brutisso@2976 | 36 | static void swap(T* array, int x, int y) { |
brutisso@2976 | 37 | T tmp = array[x]; |
brutisso@2976 | 38 | array[x] = array[y]; |
brutisso@2976 | 39 | array[y] = tmp; |
brutisso@2976 | 40 | } |
brutisso@2976 | 41 | |
brutisso@2976 | 42 | // As pivot we use the median of the first, last and middle elements. |
brutisso@2976 | 43 | // We swap in these three values at the right place in the array. This |
brutisso@2976 | 44 | // means that this method not only returns the index of the pivot |
brutisso@2976 | 45 | // element. It also alters the array so that: |
brutisso@2976 | 46 | // array[first] <= array[middle] <= array[last] |
brutisso@2976 | 47 | // A side effect of this is that arrays of length <= 3 are sorted. |
brutisso@2976 | 48 | template<class T, class C> |
brutisso@2976 | 49 | static int find_pivot(T* array, int length, C comparator) { |
brutisso@2976 | 50 | assert(length > 1, "length of array must be > 0"); |
brutisso@2976 | 51 | |
brutisso@2976 | 52 | int middle_index = length / 2; |
brutisso@2976 | 53 | int last_index = length - 1; |
brutisso@2976 | 54 | |
brutisso@2976 | 55 | if (comparator(array[0], array[middle_index]) == 1) { |
brutisso@2976 | 56 | swap(array, 0, middle_index); |
brutisso@2976 | 57 | } |
brutisso@2976 | 58 | if (comparator(array[0], array[last_index]) == 1) { |
brutisso@2976 | 59 | swap(array, 0, last_index); |
brutisso@2976 | 60 | } |
brutisso@2976 | 61 | if (comparator(array[middle_index], array[last_index]) == 1) { |
brutisso@2976 | 62 | swap(array, middle_index, last_index); |
brutisso@2976 | 63 | } |
brutisso@2976 | 64 | // Now the value in the middle of the array is the median |
brutisso@2976 | 65 | // of the fist, last and middle values. Use this as pivot. |
brutisso@2976 | 66 | return middle_index; |
brutisso@2976 | 67 | } |
brutisso@2976 | 68 | |
brutisso@2976 | 69 | template<class T, class C, bool idempotent> |
brutisso@2976 | 70 | static int partition(T* array, int pivot, int length, C comparator) { |
brutisso@2976 | 71 | int left_index = -1; |
brutisso@2976 | 72 | int right_index = length; |
brutisso@2976 | 73 | T pivot_val = array[pivot]; |
brutisso@2976 | 74 | |
brutisso@2976 | 75 | while (true) { |
brutisso@2976 | 76 | do { |
brutisso@2976 | 77 | left_index++; |
brutisso@2976 | 78 | } while (comparator(array[left_index], pivot_val) == -1); |
brutisso@2976 | 79 | do { |
brutisso@2976 | 80 | right_index--; |
brutisso@2976 | 81 | } while (comparator(array[right_index], pivot_val) == 1); |
brutisso@2976 | 82 | |
brutisso@2976 | 83 | if (left_index < right_index) { |
brutisso@2976 | 84 | if (!idempotent || comparator(array[left_index], array[right_index]) != 0) { |
brutisso@2976 | 85 | swap(array, left_index, right_index); |
brutisso@2976 | 86 | } |
brutisso@2976 | 87 | } else { |
brutisso@2976 | 88 | return right_index; |
brutisso@2976 | 89 | } |
brutisso@2976 | 90 | } |
brutisso@2976 | 91 | |
brutisso@2976 | 92 | ShouldNotReachHere(); |
brutisso@2976 | 93 | return 0; |
brutisso@2976 | 94 | } |
brutisso@2976 | 95 | |
brutisso@2976 | 96 | template<class T, class C, bool idempotent> |
brutisso@2976 | 97 | static void inner_sort(T* array, int length, C comparator) { |
brutisso@2976 | 98 | if (length < 2) { |
brutisso@2976 | 99 | return; |
brutisso@2976 | 100 | } |
brutisso@2976 | 101 | int pivot = find_pivot(array, length, comparator); |
brutisso@2976 | 102 | if (length < 4) { |
brutisso@2976 | 103 | // arrays up to length 3 will be sorted after finding the pivot |
brutisso@2976 | 104 | return; |
brutisso@2976 | 105 | } |
brutisso@2976 | 106 | int split = partition<T, C, idempotent>(array, pivot, length, comparator); |
brutisso@2976 | 107 | int first_part_length = split + 1; |
brutisso@2976 | 108 | inner_sort<T, C, idempotent>(array, first_part_length, comparator); |
brutisso@2976 | 109 | inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator); |
brutisso@2976 | 110 | } |
brutisso@2976 | 111 | |
brutisso@2976 | 112 | public: |
brutisso@2976 | 113 | // The idempotent parameter prevents the sort from |
brutisso@2976 | 114 | // reordering a previous valid sort by not swapping |
brutisso@2976 | 115 | // fields that compare as equal. This requires extra |
brutisso@2976 | 116 | // calls to the comparator, so the performance |
brutisso@2976 | 117 | // impact depends on the comparator. |
brutisso@2976 | 118 | template<class T, class C> |
brutisso@2976 | 119 | static void sort(T* array, int length, C comparator, bool idempotent) { |
brutisso@2976 | 120 | // Switch "idempotent" from function paramter to template parameter |
brutisso@2976 | 121 | if (idempotent) { |
brutisso@2976 | 122 | inner_sort<T, C, true>(array, length, comparator); |
brutisso@2976 | 123 | } else { |
brutisso@2976 | 124 | inner_sort<T, C, false>(array, length, comparator); |
brutisso@2976 | 125 | } |
brutisso@2976 | 126 | } |
brutisso@2976 | 127 | |
brutisso@2976 | 128 | // for unit testing |
brutisso@2976 | 129 | #ifndef PRODUCT |
brutisso@2976 | 130 | static void print_array(const char* prefix, int* array, int length); |
brutisso@2976 | 131 | static bool compare_arrays(int* actual, int* expected, int length); |
brutisso@2976 | 132 | template <class C> static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false); |
stefank@3335 | 133 | static void test_quick_sort(); |
brutisso@2976 | 134 | #endif |
brutisso@2976 | 135 | }; |
brutisso@2976 | 136 | |
brutisso@2976 | 137 | |
brutisso@2976 | 138 | #endif //SHARE_VM_UTILITIES_QUICKSORT_HPP |