# HG changeset patch
# User kbarrett
# Date 1502153929 14400
# Node ID 58f648e29a2641f432e470d9777b14e42e72f63f
# Parent  e2bb2b8ff65a8058b9d25895f6867b1db8624634
8185757: QuickSort array size should be size_t
Summary: Changed array size type, propogate effects.
Reviewed-by: tschatzl, coleenp

diff -r e2bb2b8ff65a -r 58f648e29a26 hotspot/src/share/vm/gc/g1/g1CollectionSet.cpp
--- a/hotspot/src/share/vm/gc/g1/g1CollectionSet.cpp	Mon Aug 07 18:50:14 2017 -0400
+++ b/hotspot/src/share/vm/gc/g1/g1CollectionSet.cpp	Mon Aug 07 20:58:49 2017 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2016, 2017, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -505,7 +505,7 @@
   double non_young_end_time_sec = os::elapsedTime();
   phase_times()->record_non_young_cset_choice_time_ms((non_young_end_time_sec - non_young_start_time_sec) * 1000.0);
 
-  QuickSort::sort<uint>(_collection_set_regions, (int)_collection_set_cur_length, compare_region_idx, true);
+  QuickSort::sort(_collection_set_regions, _collection_set_cur_length, compare_region_idx, true);
 }
 
 #ifdef ASSERT
diff -r e2bb2b8ff65a -r 58f648e29a26 hotspot/src/share/vm/oops/method.cpp
--- a/hotspot/src/share/vm/oops/method.cpp	Mon Aug 07 18:50:14 2017 -0400
+++ b/hotspot/src/share/vm/oops/method.cpp	Mon Aug 07 20:58:49 2017 -0400
@@ -1631,7 +1631,7 @@
   if (length > 1) {
     {
       NoSafepointVerifier nsv;
-      QuickSort::sort<Method*>(methods->data(), length, method_comparator, idempotent);
+      QuickSort::sort(methods->data(), length, method_comparator, idempotent);
     }
     // Reset method ordering
     if (set_idnums) {
diff -r e2bb2b8ff65a -r 58f648e29a26 hotspot/src/share/vm/utilities/quickSort.hpp
--- a/hotspot/src/share/vm/utilities/quickSort.hpp	Mon Aug 07 18:50:14 2017 -0400
+++ b/hotspot/src/share/vm/utilities/quickSort.hpp	Mon Aug 07 20:58:49 2017 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2011, 2017, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -33,7 +33,7 @@
 
  private:
   template<class T>
-  static void swap(T* array, int x, int y) {
+  static void swap(T* array, size_t x, size_t y) {
     T tmp = array[x];
     array[x] = array[y];
     array[y] = tmp;
@@ -46,19 +46,19 @@
   //     array[first] <= array[middle] <= array[last]
   // A side effect of this is that arrays of length <= 3 are sorted.
   template<class T, class C>
-  static int find_pivot(T* array, int length, C comparator) {
+  static size_t find_pivot(T* array, size_t length, C comparator) {
     assert(length > 1, "length of array must be > 0");
 
-    int middle_index = length / 2;
-    int last_index = length - 1;
+    size_t middle_index = length / 2;
+    size_t last_index = length - 1;
 
-    if (comparator(array[0], array[middle_index]) == 1) {
+    if (comparator(array[0], array[middle_index]) > 0) {
       swap(array, 0, middle_index);
     }
-    if (comparator(array[0], array[last_index]) == 1) {
+    if (comparator(array[0], array[last_index]) > 0) {
       swap(array, 0, last_index);
     }
-    if (comparator(array[middle_index], array[last_index]) == 1) {
+    if (comparator(array[middle_index], array[last_index]) > 0) {
       swap(array, middle_index, last_index);
     }
     // Now the value in the middle of the array is the median
@@ -66,19 +66,19 @@
     return middle_index;
   }
 
-  template<class T, class C, bool idempotent>
-  static int partition(T* array, int pivot, int length, C comparator) {
-    int left_index = -1;
-    int right_index = length;
+  template<bool idempotent, class T, class C>
+  static size_t partition(T* array, size_t pivot, size_t length, C comparator) {
+    size_t left_index = 0;
+    size_t right_index = length - 1;
     T pivot_val = array[pivot];
 
-    while (true) {
-      do {
-        left_index++;
-      } while (comparator(array[left_index], pivot_val) == -1);
-      do {
-        right_index--;
-      } while (comparator(array[right_index], pivot_val) == 1);
+    for ( ; true; ++left_index, --right_index) {
+      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {
+        assert(left_index < length, "reached end of partition");
+      }
+      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {
+        assert(right_index > 0, "reached start of partition");
+      }
 
       if (left_index < right_index) {
         if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {
@@ -93,20 +93,20 @@
     return 0;
   }
 
-  template<class T, class C, bool idempotent>
-  static void inner_sort(T* array, int length, C comparator) {
+  template<bool idempotent, class T, class C>
+  static void inner_sort(T* array, size_t length, C comparator) {
     if (length < 2) {
       return;
     }
-    int pivot = find_pivot(array, length, comparator);
+    size_t pivot = find_pivot(array, length, comparator);
     if (length < 4) {
       // arrays up to length 3 will be sorted after finding the pivot
       return;
     }
-    int split = partition<T, C, idempotent>(array, pivot, length, comparator);
-    int first_part_length = split + 1;
-    inner_sort<T, C, idempotent>(array, first_part_length, comparator);
-    inner_sort<T, C, idempotent>(&array[first_part_length], length - first_part_length, comparator);
+    size_t split = partition<idempotent>(array, pivot, length, comparator);
+    size_t first_part_length = split + 1;
+    inner_sort<idempotent>(array, first_part_length, comparator);
+    inner_sort<idempotent>(&array[first_part_length], length - first_part_length, comparator);
   }
 
  public:
@@ -116,12 +116,12 @@
   // calls to the comparator, so the performance
   // impact depends on the comparator.
   template<class T, class C>
-  static void sort(T* array, int length, C comparator, bool idempotent) {
+  static void sort(T* array, size_t length, C comparator, bool idempotent) {
     // Switch "idempotent" from function paramter to template parameter
     if (idempotent) {
-      inner_sort<T, C, true>(array, length, comparator);
+      inner_sort<true>(array, length, comparator);
     } else {
-      inner_sort<T, C, false>(array, length, comparator);
+      inner_sort<false>(array, length, comparator);
     }
   }
 };
diff -r e2bb2b8ff65a -r 58f648e29a26 hotspot/test/native/utilities/test_quicksort.cpp
--- a/hotspot/test/native/utilities/test_quicksort.cpp	Mon Aug 07 18:50:14 2017 -0400
+++ b/hotspot/test/native/utilities/test_quicksort.cpp	Mon Aug 07 20:58:49 2017 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2011, 2017, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -38,8 +38,8 @@
   return 1;
 }
 
-static bool compare_arrays(int* actual, int* expected, int length) {
-  for (int i = 0; i < length; i++) {
+static bool compare_arrays(int* actual, int* expected, size_t length) {
+  for (size_t i = 0; i < length; i++) {
     if (actual[i] != expected[i]) {
       return false;
     }
@@ -48,8 +48,8 @@
 }
 
 template <class C>
-static bool sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent = false) {
-  QuickSort::sort<int, C>(arrayToSort, length, comparator, idempotent);
+static bool sort_and_compare(int* arrayToSort, int* expectedResult, size_t length, C comparator, bool idempotent = false) {
+  QuickSort::sort(arrayToSort, length, comparator, idempotent);
   return compare_arrays(arrayToSort, expectedResult, length);
 }
 
@@ -174,10 +174,10 @@
 
 TEST(QuickSort, random) {
   for (int i = 0; i < 1000; i++) {
-    int length = os::random() % 100;
+    size_t length = os::random() % 100;
     int* test_array = NEW_C_HEAP_ARRAY(int, length, mtInternal);
     int* expected_array = NEW_C_HEAP_ARRAY(int, length, mtInternal);
-    for (int j = 0; j < length; j++) {
+    for (size_t j = 0; j < length; j++) {
         // Choose random values, but get a chance of getting duplicates
         test_array[j] = os::random() % (length * 2);
         expected_array[j] = test_array[j];