1 /*

     2  * Copyright (c) 2011, 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 

    32 class QuickSort : AllStatic {

    33 

    34  private:

    35   template<class T>

    36   static void swap(T* array, int x, int 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 int find_pivot(T* array, int length, C comparator) {

    50     assert(length > 1, "length of array must be > 0");

    51 

    52     int middle_index = length / 2;

    53     int last_index = length - 1;

    54 

    55     if (comparator(array[0], array[middle_index]) == 1) {

    56       swap(array, 0, middle_index);

    57     }

    58     if (comparator(array[0], array[last_index]) == 1) {

    59       swap(array, 0, last_index);

    60     }

    61     if (comparator(array[middle_index], array[last_index]) == 1) {

    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<class T, class C, bool idempotent>

    70   static int partition(T* array, int pivot, int length, C comparator) {

    71     int left_index = -1;

    72     int right_index = length;

    73     T pivot_val = array[pivot];

    74 

    75     while (true) {

    76       do {

    77         left_index++;

    78       } while (comparator(array[left_index], pivot_val) == -1);

    79       do {

    80         right_index--;

    81       } while (comparator(array[right_index], pivot_val) == 1);

    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<class T, class C, bool idempotent>

    97   static void inner_sort(T* array, int length, C comparator) {

    98     if (length < 2) {

    99       return;

   100     }

   101     int 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     int split = partition<T, C, idempotent>(array, pivot, length, comparator);

   107     int first_part_length = split + 1;

   108     inner_sort<T, C, idempotent>(array, first_part_length, comparator);

   109     inner_sort<T, C, 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, int length, C comparator, bool idempotent) {

   120     // Switch "idempotent" from function paramter to template parameter

   121     if (idempotent) {

   122       inner_sort<T, C, true>(array, length, comparator);

   123     } else {

   124       inner_sort<T, C, false>(array, length, comparator);

   125     }

   126   }

   127 

   128   // for unit testing

   129 #ifndef PRODUCT

   130   static void print_array(const char* prefix, int* array, int length);

   131   static bool compare_arrays(int* actual, int* expected, int length);

   132   template <class C> static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false);

   133   static bool test_quick_sort();

   134 #endif

   135 };

   136 

   137 

   138 #endif //SHARE_VM_UTILITIES_QUICKSORT_HPP