1 /*
2  * Copyright (c) 2011, 2019, 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_UTILITIES_QUICKSORT_HPP
26 #define SHARE_UTILITIES_QUICKSORT_HPP
27 
28 #include "memory/allocation.hpp"
29 #include "runtime/globals.hpp"
30 #include "utilities/debug.hpp"
31 
32 class QuickSort : AllStatic {
33 
34  private:
35   template<class T>
swap(T * array,size_t x,size_t y)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>
find_pivot(T * array,size_t length,C comparator)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>
partition(T * array,size_t pivot,size_t length,C comparator)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>
inner_sort(T * array,size_t length,C comparator)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>
sort(T * array,size_t length,C comparator,bool idempotent)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_UTILITIES_QUICKSORT_HPP
131