Mercurial > jdk8-mips64-public > hotspot / changeset

     1.1 --- a/src/share/vm/oops/methodOop.cpp	Fri Jun 24 12:38:49 2011 -0400
     1.2 +++ b/src/share/vm/oops/methodOop.cpp	Tue Jun 28 14:23:27 2011 +0200
     1.3 @@ -49,6 +49,7 @@
     1.4  #include "runtime/relocator.hpp"
     1.5  #include "runtime/sharedRuntime.hpp"
     1.6  #include "runtime/signature.hpp"
     1.7 +#include "utilities/quickSort.hpp"
     1.8  #include "utilities/xmlstream.hpp"
     1.9  
    1.10  
    1.11 @@ -1204,41 +1205,6 @@
    1.12    if (WizardMode) signature()->print_symbol_on(st);
    1.13  }
    1.14  
    1.15 -
    1.16 -extern "C" {
    1.17 -  static int method_compare(methodOop* a, methodOop* b) {
    1.18 -    return (*a)->name()->fast_compare((*b)->name());
    1.19 -  }
    1.20 -
    1.21 -  // Prevent qsort from reordering a previous valid sort by
    1.22 -  // considering the address of the methodOops if two methods
    1.23 -  // would otherwise compare as equal.  Required to preserve
    1.24 -  // optimal access order in the shared archive.  Slower than
    1.25 -  // method_compare, only used for shared archive creation.
    1.26 -  static int method_compare_idempotent(methodOop* a, methodOop* b) {
    1.27 -    int i = method_compare(a, b);
    1.28 -    if (i != 0) return i;
    1.29 -    return ( a < b ? -1 : (a == b ? 0 : 1));
    1.30 -  }
    1.31 -
    1.32 -  // We implement special compare versions for narrow oops to avoid
    1.33 -  // testing for UseCompressedOops on every comparison.
    1.34 -  static int method_compare_narrow(narrowOop* a, narrowOop* b) {
    1.35 -    methodOop m = (methodOop)oopDesc::load_decode_heap_oop(a);
    1.36 -    methodOop n = (methodOop)oopDesc::load_decode_heap_oop(b);
    1.37 -    return m->name()->fast_compare(n->name());
    1.38 -  }
    1.39 -
    1.40 -  static int method_compare_narrow_idempotent(narrowOop* a, narrowOop* b) {
    1.41 -    int i = method_compare_narrow(a, b);
    1.42 -    if (i != 0) return i;
    1.43 -    return ( a < b ? -1 : (a == b ? 0 : 1));
    1.44 -  }
    1.45 -
    1.46 -  typedef int (*compareFn)(const void*, const void*);
    1.47 -}
    1.48 -
    1.49 -
    1.50  // This is only done during class loading, so it is OK to assume method_idnum matches the methods() array
    1.51  static void reorder_based_on_method_index(objArrayOop methods,
    1.52                                            objArrayOop annotations,
    1.53 @@ -1262,6 +1228,14 @@
    1.54    }
    1.55  }
    1.56  
    1.57 +// Comparer for sorting an object array containing
    1.58 +// methodOops.
    1.59 +template <class T>
    1.60 +static int method_comparator(T a, T b) {
    1.61 +  methodOop m = (methodOop)oopDesc::decode_heap_oop_not_null(a);
    1.62 +  methodOop n = (methodOop)oopDesc::decode_heap_oop_not_null(b);
    1.63 +  return m->name()->fast_compare(n->name());
    1.64 +}
    1.65  
    1.66  // This is only done during class loading, so it is OK to assume method_idnum matches the methods() array
    1.67  void methodOopDesc::sort_methods(objArrayOop methods,
    1.68 @@ -1284,30 +1258,19 @@
    1.69          m->set_method_idnum(i);
    1.70        }
    1.71      }
    1.72 -
    1.73 -    // Use a simple bubble sort for small number of methods since
    1.74 -    // qsort requires a functional pointer call for each comparison.
    1.75 -    if (length < 8) {
    1.76 -      bool sorted = true;
    1.77 -      for (int i=length-1; i>0; i--) {
    1.78 -        for (int j=0; j<i; j++) {
    1.79 -          methodOop m1 = (methodOop)methods->obj_at(j);
    1.80 -          methodOop m2 = (methodOop)methods->obj_at(j+1);
    1.81 -          if ((uintptr_t)m1->name() > (uintptr_t)m2->name()) {
    1.82 -            methods->obj_at_put(j, m2);
    1.83 -            methods->obj_at_put(j+1, m1);
    1.84 -            sorted = false;
    1.85 -          }
    1.86 -        }
    1.87 -        if (sorted) break;
    1.88 -          sorted = true;
    1.89 +    {
    1.90 +      No_Safepoint_Verifier nsv;
    1.91 +      if (UseCompressedOops) {
    1.92 +        QuickSort::sort<narrowOop>((narrowOop*)(methods->base()), length, method_comparator<narrowOop>, idempotent);
    1.93 +      } else {
    1.94 +        QuickSort::sort<oop>((oop*)(methods->base()), length, method_comparator<oop>, idempotent);
    1.95        }
    1.96 -    } else {
    1.97 -      compareFn compare =
    1.98 -        (UseCompressedOops ?
    1.99 -         (compareFn) (idempotent ? method_compare_narrow_idempotent : method_compare_narrow):
   1.100 -         (compareFn) (idempotent ? method_compare_idempotent : method_compare));
   1.101 -      qsort(methods->base(), length, heapOopSize, compare);
   1.102 +      if (UseConcMarkSweepGC) {
   1.103 +        // For CMS we need to dirty the cards for the array
   1.104 +        BarrierSet* bs = Universe::heap()->barrier_set();
   1.105 +        assert(bs->has_write_ref_array_opt(), "Barrier set must have ref array opt");
   1.106 +        bs->write_ref_array(methods->base(), length);
   1.107 +      }
   1.108      }
   1.109  
   1.110      // Sort annotations if necessary

     2.1 --- a/src/share/vm/prims/jni.cpp	Fri Jun 24 12:38:49 2011 -0400
     2.2 +++ b/src/share/vm/prims/jni.cpp	Tue Jun 28 14:23:27 2011 +0200
     2.3 @@ -3296,6 +3296,19 @@
     2.4    return ret;
     2.5  }
     2.6  
     2.7 +#ifndef PRODUCT
     2.8 +
     2.9 +#include "utilities/quickSort.hpp"
    2.10 +
    2.11 +void execute_internal_vm_tests() {
    2.12 +  if (ExecuteInternalVMTests) {
    2.13 +    assert(QuickSort::test_quick_sort(), "test_quick_sort failed");
    2.14 +    tty->print_cr("All tests passed");
    2.15 +  }
    2.16 +}
    2.17 +
    2.18 +#endif
    2.19 +
    2.20  HS_DTRACE_PROBE_DECL3(hotspot_jni, CreateJavaVM__entry, vm, penv, args);
    2.21  DT_RETURN_MARK_DECL(CreateJavaVM, jint);
    2.22  
    2.23 @@ -3386,6 +3399,7 @@
    2.24    }
    2.25  
    2.26    NOT_PRODUCT(test_error_handler(ErrorHandlerTest));
    2.27 +  NOT_PRODUCT(execute_internal_vm_tests());
    2.28    return result;
    2.29  }
    2.30  

     3.1 --- a/src/share/vm/runtime/globals.hpp	Fri Jun 24 12:38:49 2011 -0400
     3.2 +++ b/src/share/vm/runtime/globals.hpp	Tue Jun 28 14:23:27 2011 +0200
     3.3 @@ -1944,6 +1944,9 @@
     3.4            "Number of ObjArray elements to push onto the marking stack"      \
     3.5            "before pushing a continuation entry")                            \
     3.6                                                                              \
     3.7 +  notproduct(bool, ExecuteInternalVMTests, false,                           \
     3.8 +          "Enable execution of internal VM tests.")                         \
     3.9 +                                                                            \
    3.10    product_pd(bool, UseTLAB, "Use thread-local object allocation")           \
    3.11                                                                              \
    3.12    product_pd(bool, ResizeTLAB,                                              \

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/share/vm/utilities/quickSort.cpp	Tue Jun 28 14:23:27 2011 +0200
     4.3 @@ -0,0 +1,218 @@
     4.4 +/*
     4.5 + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
     4.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     4.7 + *
     4.8 + * This code is free software; you can redistribute it and/or modify it
     4.9 + * under the terms of the GNU General Public License version 2 only, as
    4.10 + * published by the Free Software Foundation.
    4.11 + *
    4.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
    4.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    4.14 + * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    4.15 + * version 2 for more details (a copy is included in the LICENSE file that
    4.16 + * accompanied this code).
    4.17 + *
    4.18 + * You should have received a copy of the GNU General Public License version
    4.19 + * 2 along with this work; if not, write to the Free Software Foundation,
    4.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
    4.21 + *
    4.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
    4.23 + * or visit www.oracle.com if you need additional information or have any
    4.24 + * questions.
    4.25 + *
    4.26 + */
    4.27 +
    4.28 +#include "precompiled.hpp"
    4.29 +#include "utilities/quickSort.hpp"
    4.30 +
    4.31 +#ifndef PRODUCT
    4.32 +
    4.33 +// Unit tests
    4.34 +
    4.35 +#include "runtime/os.hpp"
    4.36 +#include <stdlib.h>
    4.37 +
    4.38 +static int test_comparator(int a, int b) {
    4.39 +  if (a == b) {
    4.40 +    return 0;
    4.41 +  }
    4.42 +  if (a < b) {
    4.43 +    return -1;
    4.44 +  }
    4.45 +  return 1;
    4.46 +}
    4.47 +
    4.48 +static int test_even_odd_comparator(int a, int b) {
    4.49 +  bool a_is_odd = (a % 2) == 1;
    4.50 +  bool b_is_odd = (b % 2) == 1;
    4.51 +  if (a_is_odd == b_is_odd) {
    4.52 +    return 0;
    4.53 +  }
    4.54 +  if (a_is_odd) {
    4.55 +    return -1;
    4.56 +  }
    4.57 +  return 1;
    4.58 +}
    4.59 +
    4.60 +static int test_stdlib_comparator(const void* a, const void* b) {
    4.61 +  int ai = *(int*)a;
    4.62 +  int bi = *(int*)b;
    4.63 +  if (ai == bi) {
    4.64 +    return 0;
    4.65 +  }
    4.66 +  if (ai < bi) {
    4.67 +    return -1;
    4.68 +  }
    4.69 +  return 1;
    4.70 +}
    4.71 +
    4.72 +void QuickSort::print_array(const char* prefix, int* array, int length) {
    4.73 +  tty->print("%s:", prefix);
    4.74 +  for (int i = 0; i < length; i++) {
    4.75 +    tty->print(" %d", array[i]);
    4.76 +  }
    4.77 +  tty->print_cr("");
    4.78 +}
    4.79 +
    4.80 +bool QuickSort::compare_arrays(int* actual, int* expected, int length) {
    4.81 +  for (int i = 0; i < length; i++) {
    4.82 +    if (actual[i] != expected[i]) {
    4.83 +      print_array("Sorted array  ", actual, length);
    4.84 +      print_array("Expected array", expected, length);
    4.85 +      return false;
    4.86 +    }
    4.87 +  }
    4.88 +  return true;
    4.89 +}
    4.90 +
    4.91 +template <class C>
    4.92 +bool QuickSort::sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent) {
    4.93 +  sort<int, C>(arrayToSort, length, comparator, idempotent);
    4.94 +  return compare_arrays(arrayToSort, expectedResult, length);
    4.95 +}
    4.96 +
    4.97 +bool QuickSort::test_quick_sort() {
    4.98 +  tty->print_cr("test_quick_sort\n");
    4.99 +  {
   4.100 +    int* test_array = NULL;
   4.101 +    int* expected_array = NULL;
   4.102 +    assert(sort_and_compare(test_array, expected_array, 0, test_comparator), "Empty array not handled");
   4.103 +  }
   4.104 +  {
   4.105 +    int test_array[] = {3};
   4.106 +    int expected_array[] = {3};
   4.107 +    assert(sort_and_compare(test_array, expected_array, 1, test_comparator), "Single value array not handled");
   4.108 +  }
   4.109 +  {
   4.110 +    int test_array[] = {3,2};
   4.111 +    int expected_array[] = {2,3};
   4.112 +    assert(sort_and_compare(test_array, expected_array, 2, test_comparator), "Array with 2 values not correctly sorted");
   4.113 +  }
   4.114 +  {
   4.115 +    int test_array[] = {3,2,1};
   4.116 +    int expected_array[] = {1,2,3};
   4.117 +    assert(sort_and_compare(test_array, expected_array, 3, test_comparator), "Array with 3 values not correctly sorted");
   4.118 +  }
   4.119 +  {
   4.120 +    int test_array[] = {4,3,2,1};
   4.121 +    int expected_array[] = {1,2,3,4};
   4.122 +    assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "Array with 4 values not correctly sorted");
   4.123 +  }
   4.124 +  {
   4.125 +    int test_array[] = {7,1,5,3,6,9,8,2,4,0};
   4.126 +    int expected_array[] = {0,1,2,3,4,5,6,7,8,9};
   4.127 +    assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Array with 10 values not correctly sorted");
   4.128 +  }
   4.129 +  {
   4.130 +    int test_array[] = {4,4,1,4};
   4.131 +    int expected_array[] = {1,4,4,4};
   4.132 +    assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "3 duplicates not sorted correctly");
   4.133 +  }
   4.134 +  {
   4.135 +    int test_array[] = {0,1,2,3,4,5,6,7,8,9};
   4.136 +    int expected_array[] = {0,1,2,3,4,5,6,7,8,9};
   4.137 +    assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Already sorted array not correctly sorted");
   4.138 +  }
   4.139 +  {
   4.140 +    // one of the random arrays that found an issue in the partion method.
   4.141 +    int test_array[] = {76,46,81,8,64,56,75,11,51,55,11,71,59,27,9,64,69,75,21,25,39,40,44,32,7,8,40,41,24,78,24,74,9,65,28,6,40,31,22,13,27,82};
   4.142 +    int expected_array[] = {6,7,8,8,9,9,11,11,13,21,22,24,24,25,27,27,28,31,32,39,40,40,40,41,44,46,51,55,56,59,64,64,65,69,71,74,75,75,76,78,81,82};
   4.143 +    assert(sort_and_compare(test_array, expected_array, 42, test_comparator), "Not correctly sorted");
   4.144 +  }
   4.145 +  {
   4.146 +    int test_array[] = {2,8,1,4};
   4.147 +    int expected_array[] = {1,4,2,8};
   4.148 +    assert(sort_and_compare(test_array, expected_array, 4, test_even_odd_comparator), "Even/odd not sorted correctly");
   4.149 +  }
   4.150 +  {  // Some idempotent tests
   4.151 +    {
   4.152 +      // An array of lenght 3 is only sorted by find_pivot. Make sure that it is idempotent.
   4.153 +      int test_array[] = {1,4,8};
   4.154 +      int expected_array[] = {1,4,8};
   4.155 +      assert(sort_and_compare(test_array, expected_array, 3, test_even_odd_comparator, true), "Even/odd not idempotent");
   4.156 +    }
   4.157 +    {
   4.158 +      int test_array[] = {1,7,9,4,8,2};
   4.159 +      int expected_array[] = {1,7,9,4,8,2};
   4.160 +      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
   4.161 +    }
   4.162 +    {
   4.163 +      int test_array[] = {1,9,7,4,2,8};
   4.164 +      int expected_array[] = {1,9,7,4,2,8};
   4.165 +      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
   4.166 +    }
   4.167 +    {
   4.168 +      int test_array[] = {7,9,1,2,8,4};
   4.169 +      int expected_array[] = {7,9,1,2,8,4};
   4.170 +      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
   4.171 +    }
   4.172 +    {
   4.173 +      int test_array[] = {7,1,9,2,4,8};
   4.174 +      int expected_array[] = {7,1,9,2,4,8};
   4.175 +      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
   4.176 +    }
   4.177 +    {
   4.178 +      int test_array[] = {9,1,7,4,8,2};
   4.179 +      int expected_array[] = {9,1,7,4,8,2};
   4.180 +      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
   4.181 +    }
   4.182 +    {
   4.183 +      int test_array[] = {9,7,1,4,2,8};
   4.184 +      int expected_array[] = {9,7,1,4,2,8};
   4.185 +      assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent");
   4.186 +    }
   4.187 +  }
   4.188 +
   4.189 +  // test sorting random arrays
   4.190 +  for (int i = 0; i < 1000; i++) {
   4.191 +    int length = os::random() % 100;
   4.192 +    int* test_array = new int[length];
   4.193 +    int* expected_array = new int[length];
   4.194 +    for (int j = 0; j < length; j++) {
   4.195 +        // Choose random values, but get a chance of getting duplicates
   4.196 +        test_array[j] = os::random() % (length * 2);
   4.197 +        expected_array[j] = test_array[j];
   4.198 +    }
   4.199 +
   4.200 +    // Compare sorting to stdlib::qsort()
   4.201 +    qsort(expected_array, length, sizeof(int), test_stdlib_comparator);
   4.202 +    assert(sort_and_compare(test_array, expected_array, length, test_comparator), "Random array not correctly sorted");
   4.203 +
   4.204 +    // Make sure sorting is idempotent.
   4.205 +    // Both test_array and expected_array are sorted by the test_comparator.
   4.206 +    // Now sort them once with the test_even_odd_comparator. Then sort the
   4.207 +    // test_array one more time with test_even_odd_comparator and verify that
   4.208 +    // it is idempotent.
   4.209 +    sort(expected_array, length, test_even_odd_comparator, true);
   4.210 +    sort(test_array, length, test_even_odd_comparator, true);
   4.211 +    assert(compare_arrays(test_array, expected_array, length), "Sorting identical arrays rendered different results");
   4.212 +    sort(test_array, length, test_even_odd_comparator, true);
   4.213 +    assert(compare_arrays(test_array, expected_array, length), "Sorting already sorted array changed order of elements - not idempotent");
   4.214 +
   4.215 +    delete[] test_array;
   4.216 +    delete[] expected_array;
   4.217 +  }
   4.218 +  return true;
   4.219 +}
   4.220 +
   4.221 +#endif

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/share/vm/utilities/quickSort.hpp	Tue Jun 28 14:23:27 2011 +0200
     5.3 @@ -0,0 +1,138 @@
     5.4 +/*
     5.5 + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
     5.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     5.7 + *
     5.8 + * This code is free software; you can redistribute it and/or modify it
     5.9 + * under the terms of the GNU General Public License version 2 only, as
    5.10 + * published by the Free Software Foundation.
    5.11 + *
    5.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
    5.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    5.14 + * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    5.15 + * version 2 for more details (a copy is included in the LICENSE file that
    5.16 + * accompanied this code).
    5.17 + *
    5.18 + * You should have received a copy of the GNU General Public License version
    5.19 + * 2 along with this work; if not, write to the Free Software Foundation,
    5.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
    5.21 + *
    5.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
    5.23 + * or visit www.oracle.com if you need additional information or have any
    5.24 + * questions.
    5.25 + *
    5.26 + */
    5.27 +
    5.28 +#ifndef SHARE_VM_UTILITIES_QUICKSORT_HPP
    5.29 +#define SHARE_VM_UTILITIES_QUICKSORT_HPP
    5.30 +
    5.31 +#include "memory/allocation.hpp"
    5.32 +#include "runtime/globals.hpp"
    5.33 +#include "utilities/debug.hpp"
    5.34 +
    5.35 +class QuickSort : AllStatic {
    5.36 +
    5.37 + private:
    5.38 +  template<class T>
    5.39 +  static void swap(T* array, int x, int y) {
    5.40 +    T tmp = array[x];
    5.41 +    array[x] = array[y];
    5.42 +    array[y] = tmp;
    5.43 +  }
    5.44 +
    5.45 +  // As pivot we use the median of the first, last and middle elements.
    5.46 +  // We swap in these three values at the right place in the array. This
    5.47 +  // means that this method not only returns the index of the pivot
    5.48 +  // element. It also alters the array so that:
    5.49 +  //     array[first] <= array[middle] <= array[last]
    5.50 +  // A side effect of this is that arrays of length <= 3 are sorted.
    5.51 +  template<class T, class C>
    5.52 +  static int find_pivot(T* array, int length, C comparator) {
    5.53 +    assert(length > 1, "length of array must be > 0");
    5.54 +
    5.55 +    int middle_index = length / 2;
    5.56 +    int last_index = length - 1;
    5.57 +
    5.58 +    if (comparator(array[0], array[middle_index]) == 1) {
    5.59 +      swap(array, 0, middle_index);
    5.60 +    }
    5.61 +    if (comparator(array[0], array[last_index]) == 1) {
    5.62 +      swap(array, 0, last_index);
    5.63 +    }
    5.64 +    if (comparator(array[middle_index], array[last_index]) == 1) {
    5.65 +      swap(array, middle_index, last_index);
    5.66 +    }
    5.67 +    // Now the value in the middle of the array is the median
    5.68 +    // of the fist, last and middle values. Use this as pivot.
    5.69 +    return middle_index;
    5.70 +  }
    5.71 +
    5.72 +  template<class T, class C, bool idempotent>
    5.73 +  static int partition(T* array, int pivot, int length, C comparator) {
    5.74 +    int left_index = -1;
    5.75 +    int right_index = length;
    5.76 +    T pivot_val = array[pivot];
    5.77 +
    5.78 +    while (true) {
    5.79 +      do {
    5.80 +        left_index++;
    5.81 +      } while (comparator(array[left_index], pivot_val) == -1);
    5.82 +      do {
    5.83 +        right_index--;
    5.84 +      } while (comparator(array[right_index], pivot_val) == 1);
    5.85 +
    5.86 +      if (left_index < right_index) {
    5.87 +        if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {
    5.88 +          swap(array, left_index, right_index);
    5.89 +        }
    5.90 +      } else {
    5.91 +        return right_index;
    5.92 +      }
    5.93 +    }
    5.94 +
    5.95 +    ShouldNotReachHere();
    5.96 +    return 0;
    5.97 +  }
    5.98 +
    5.99 +  template<class T, class C, bool idempotent>
   5.100 +  static void inner_sort(T* array, int length, C comparator) {
   5.101 +    if (length < 2) {
   5.102 +      return;
   5.103 +    }
   5.104 +    int pivot = find_pivot(array, length, comparator);
   5.105 +    if (length < 4) {
   5.106 +      // arrays up to length 3 will be sorted after finding the pivot
   5.107 +      return;
   5.108 +    }
   5.109 +    int split = partition<T, C, idempotent>(array, pivot, length, comparator);
   5.110 +    int first_part_length = split + 1;
   5.111 +    inner_sort<T, C, idempotent>(array, first_part_length, comparator);
   5.112 +    inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator);
   5.113 +  }
   5.114 +
   5.115 + public:
   5.116 +  // The idempotent parameter prevents the sort from
   5.117 +  // reordering a previous valid sort by not swapping
   5.118 +  // fields that compare as equal. This requires extra
   5.119 +  // calls to the comparator, so the performance
   5.120 +  // impact depends on the comparator.
   5.121 +  template<class T, class C>
   5.122 +  static void sort(T* array, int length, C comparator, bool idempotent) {
   5.123 +    // Switch "idempotent" from function paramter to template parameter
   5.124 +    if (idempotent) {
   5.125 +      inner_sort<T, C, true>(array, length, comparator);
   5.126 +    } else {
   5.127 +      inner_sort<T, C, false>(array, length, comparator);
   5.128 +    }
   5.129 +  }
   5.130 +
   5.131 +  // for unit testing
   5.132 +#ifndef PRODUCT
   5.133 +  static void print_array(const char* prefix, int* array, int length);
   5.134 +  static bool compare_arrays(int* actual, int* expected, int length);
   5.135 +  template <class C> static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false);
   5.136 +  static bool test_quick_sort();
   5.137 +#endif
   5.138 +};
   5.139 +
   5.140 +
   5.141 +#endif //SHARE_VM_UTILITIES_QUICKSORT_HPP