1/*
2 * Copyright (c) 2011, 2017, 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_VM_UTILITIES_QUICKSORT_HPP
26#define SHARE_VM_UTILITIES_QUICKSORT_HPP
27
28#include "memory/allocation.hpp"
29#include "runtime/globals.hpp"
30#include "utilities/debug.hpp"
31
32class QuickSort : AllStatic {
33
34 private:
35  template<class T>
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>
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>
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>
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>
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_VM_UTILITIES_QUICKSORT_HPP
131