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 "runtime/globals.hpp"
  29 #include "utilities/debug.hpp"
  30 
  31 class quicksort {
  32 
  33  private:
  34   template<class T>
  35   static void swap(T* array, int x, int y) {
  36     T tmp = array[x];
  37     array[x] = array[y];
  38     array[y] = tmp;
  39   }
  40 
  41   // As pivot we use the median of the first, last and middle elements.
  42   // We swap in these three values at the right place in the array. This
  43   // means that this method not only returns the index of the pivot
  44   // element. It also alters the array so that:
  45   //     array[first] <= array[middle] <= array[last]
  46   // A side effect of this is that arrays of length <= 3 are sorted.
  47   template<class T, class C>
  48   static int find_pivot(T* array, int length, C comparer) {
  49     assert(length > 1, "length of array must be > 0");
  50 
  51     int middle_index = length / 2;
  52     int last_index = length - 1;
  53 
  54     if (comparer(array[0], array[middle_index]) == 1) {
  55       swap(array, 0, middle_index);
  56     }
  57     if (comparer(array[0], array[last_index]) == 1) {
  58       swap(array, 0, last_index);
  59     }
  60     if (comparer(array[middle_index], array[last_index]) == 1) {
  61       swap(array, middle_index, last_index);
  62     }
  63     // Now the value in the middle of the array is the median
  64     // of the fist, last and middle values. Use this as pivot.
  65     return middle_index;
  66   }
  67   
  68   template<class T, class C, bool idempotent>
  69   static int partition(T* array, int pivot, int length, C comparer) {
  70     int left_index = -1;
  71     int right_index = length;
  72     T pivot_val = array[pivot];
  73 
  74     while (true) {
  75       do {
  76         left_index++;
  77       } while (comparer(array[left_index], pivot_val) == -1);
  78       do {
  79         right_index--;
  80       } while (comparer(array[right_index], pivot_val) == 1);
  81       
  82       if (left_index < right_index) {
  83         if (!idempotent || comparer(array[left_index], array[right_index]) != 0) {
  84           swap(array, left_index, right_index);
  85         }
  86       } else {
  87         return right_index;
  88       }
  89     }
  90 
  91     ShouldNotReachHere();
  92     return 0;
  93   }
  94   
  95  public:
  96    // The idempotent parameter prevents the sort from
  97    // reordering a previous valid sort by not swapping
  98    // fields that compare as equal. This requires extra
  99    // calls to the comparer, so the performance
 100    // impact depends on the comparer.
 101   template<class T, class C, bool idempotent>
 102   static void sort(T* array, int length, C comparer) {
 103     if (length < 2) {
 104       return;
 105     }
 106     int pivot = find_pivot(array, length, comparer);
 107     if (length < 4) {
 108       // arrays up to length 3 will be sorted after finding the pivot
 109       return;
 110     }
 111     int split = partition<T, C, idempotent>(array, pivot, length, comparer);
 112     int first_part_length = split + 1;
 113     sort<T, C, idempotent>(array, first_part_length, comparer);
 114     sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparer); 
 115   }
 116 
 117   // for unit testing
 118 #ifndef PRODUCT
 119   static void print_array(const char* prefix, int* array, int length);
 120   static bool compare_arrays(int* actual, int* expected, int length);
 121   template <class C> static bool sortAndCompare(int* arrayToSort, int* expectedResult, int length, C comparer, bool idempotent = false);
 122   static bool testQuicksort();
 123 #endif
 124 };
 125 
 126 
 127 #endif //SHARE_VM_UTILITIES_QUICKSORT_HPP