src/hotspot/share/utilities/quickSort.hpp
author mr
Tue, 29 Oct 2019 13:52:04 -0700
changeset 58850 f4290bf1cc21
parent 53244 9807daeb47c4
permissions -rw-r--r--
8233137: runtime/ErrorHandling/VeryEarlyAssertTest.java fails after 8232080 Reviewed-by: stuefe, iignatyev, mchung
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     1
/*
53244
9807daeb47c4 8216167: Update include guards to reflect correct directories
coleenp
parents: 47216
diff changeset
     2
 * Copyright (c) 2011, 2019, Oracle and/or its affiliates. All rights reserved.
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     4
 *
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     7
 * published by the Free Software Foundation.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     8
 *
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
     9
 * This code is distributed in the hope that it will be useful, but WITHOUT
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    10
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    11
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    12
 * version 2 for more details (a copy is included in the LICENSE file that
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    13
 * accompanied this code).
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    14
 *
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    15
 * You should have received a copy of the GNU General Public License version
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    16
 * 2 along with this work; if not, write to the Free Software Foundation,
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    17
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    18
 *
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    20
 * or visit www.oracle.com if you need additional information or have any
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    21
 * questions.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    22
 *
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    23
 */
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    24
53244
9807daeb47c4 8216167: Update include guards to reflect correct directories
coleenp
parents: 47216
diff changeset
    25
#ifndef SHARE_UTILITIES_QUICKSORT_HPP
9807daeb47c4 8216167: Update include guards to reflect correct directories
coleenp
parents: 47216
diff changeset
    26
#define SHARE_UTILITIES_QUICKSORT_HPP
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    27
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    28
#include "memory/allocation.hpp"
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    29
#include "runtime/globals.hpp"
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    30
#include "utilities/debug.hpp"
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    31
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    32
class QuickSort : AllStatic {
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    33
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    34
 private:
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    35
  template<class T>
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    36
  static void swap(T* array, size_t x, size_t y) {
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    37
    T tmp = array[x];
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    38
    array[x] = array[y];
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    39
    array[y] = tmp;
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    40
  }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    41
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    42
  // As pivot we use the median of the first, last and middle elements.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    43
  // We swap in these three values at the right place in the array. This
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    44
  // means that this method not only returns the index of the pivot
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    45
  // element. It also alters the array so that:
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    46
  //     array[first] <= array[middle] <= array[last]
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    47
  // A side effect of this is that arrays of length <= 3 are sorted.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    48
  template<class T, class C>
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    49
  static size_t find_pivot(T* array, size_t length, C comparator) {
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    50
    assert(length > 1, "length of array must be > 0");
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    51
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    52
    size_t middle_index = length / 2;
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    53
    size_t last_index = length - 1;
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    54
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    55
    if (comparator(array[0], array[middle_index]) > 0) {
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    56
      swap(array, 0, middle_index);
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    57
    }
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    58
    if (comparator(array[0], array[last_index]) > 0) {
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    59
      swap(array, 0, last_index);
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    60
    }
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    61
    if (comparator(array[middle_index], array[last_index]) > 0) {
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    62
      swap(array, middle_index, last_index);
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    63
    }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    64
    // Now the value in the middle of the array is the median
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    65
    // of the fist, last and middle values. Use this as pivot.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    66
    return middle_index;
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    67
  }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    68
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    69
  template<bool idempotent, class T, class C>
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    70
  static size_t partition(T* array, size_t pivot, size_t length, C comparator) {
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    71
    size_t left_index = 0;
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    72
    size_t right_index = length - 1;
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    73
    T pivot_val = array[pivot];
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    74
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    75
    for ( ; true; ++left_index, --right_index) {
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    76
      for ( ; comparator(array[left_index], pivot_val) < 0; ++left_index) {
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    77
        assert(left_index < length, "reached end of partition");
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    78
      }
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    79
      for ( ; comparator(array[right_index], pivot_val) > 0; --right_index) {
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    80
        assert(right_index > 0, "reached start of partition");
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    81
      }
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    82
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    83
      if (left_index < right_index) {
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    84
        if (!idempotent || comparator(array[left_index], array[right_index]) != 0) {
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    85
          swap(array, left_index, right_index);
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    86
        }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    87
      } else {
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    88
        return right_index;
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    89
      }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    90
    }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    91
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    92
    ShouldNotReachHere();
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    93
    return 0;
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    94
  }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    95
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    96
  template<bool idempotent, class T, class C>
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
    97
  static void inner_sort(T* array, size_t length, C comparator) {
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    98
    if (length < 2) {
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
    99
      return;
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   100
    }
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   101
    size_t pivot = find_pivot(array, length, comparator);
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   102
    if (length < 4) {
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   103
      // arrays up to length 3 will be sorted after finding the pivot
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   104
      return;
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   105
    }
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   106
    size_t split = partition<idempotent>(array, pivot, length, comparator);
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   107
    size_t first_part_length = split + 1;
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   108
    inner_sort<idempotent>(array, first_part_length, comparator);
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   109
    inner_sort<idempotent>(&array[first_part_length], length - first_part_length, comparator);
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   110
  }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   111
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   112
 public:
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   113
  // The idempotent parameter prevents the sort from
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   114
  // reordering a previous valid sort by not swapping
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   115
  // fields that compare as equal. This requires extra
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   116
  // calls to the comparator, so the performance
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   117
  // impact depends on the comparator.
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   118
  template<class T, class C>
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   119
  static void sort(T* array, size_t length, C comparator, bool idempotent) {
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   120
    // Switch "idempotent" from function paramter to template parameter
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   121
    if (idempotent) {
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   122
      inner_sort<true>(array, length, comparator);
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   123
    } else {
46768
58f648e29a26 8185757: QuickSort array size should be size_t
kbarrett
parents: 35529
diff changeset
   124
      inner_sort<false>(array, length, comparator);
10002
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   125
    }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   126
  }
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   127
};
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   128
2d83be3a0927 7016112: CMS: crash during promotion testing
brutisso
parents:
diff changeset
   129
53244
9807daeb47c4 8216167: Update include guards to reflect correct directories
coleenp
parents: 47216
diff changeset
   130
#endif // SHARE_UTILITIES_QUICKSORT_HPP