There are various places in HotSpot where an array of values needs to be sorted, some of which use the C qsort library function. This has various problems.
To use qsort correctly requires passing a C linkage comparison function. Some callers properly go to the trouble of creating such a function by declaring the comparison function appropriately (using extern "C"). But other callers don't do that. Instead, there's this:
// Need the correct linkage to call qsort without warnings
extern "C" {
typedef int (*_sort_Fn)(const void *, const void *);
}
and then cast(!) a C++ function to _sort_Fn, which is certainly technically incorrect, though apparently happens to work on supported platforms.
(Many of these are indirectly using qsort and a cast of the comparison function via GrowableArray::sort.)
We also have this comment for LayoutRawBlock::compare_size_inverted:
// qsort() on Windows reverse the order of fields with the same size
// the extension of the comparison function below preserves this order
This suggests this code wants a stable sort, and (some version of) the Windows qsort apparently isn't, which is permitted. (And this code assumes all others are stable, which isn't a valid assumption.) I found a couple other places that seem to be wanting a stable sort and are going to some extra effort to get it.
Using the C qsort function requires the element type of the array to be trivial. That's a non-obvious requirement, especially for GrowableArray.
Much of this could be dealt with by using the existing QuickSort::sort utility, which is entirely C++, and may be able to inline the comparison function.
(An alternative would be to use one of the Standard Library sorting algorithms, but HotSpot code mostly avoids using the Standard Library.)
To use qsort correctly requires passing a C linkage comparison function. Some callers properly go to the trouble of creating such a function by declaring the comparison function appropriately (using extern "C"). But other callers don't do that. Instead, there's this:
// Need the correct linkage to call qsort without warnings
extern "C" {
typedef int (*_sort_Fn)(const void *, const void *);
}
and then cast(!) a C++ function to _sort_Fn, which is certainly technically incorrect, though apparently happens to work on supported platforms.
(Many of these are indirectly using qsort and a cast of the comparison function via GrowableArray::sort.)
We also have this comment for LayoutRawBlock::compare_size_inverted:
// qsort() on Windows reverse the order of fields with the same size
// the extension of the comparison function below preserves this order
This suggests this code wants a stable sort, and (some version of) the Windows qsort apparently isn't, which is permitted. (And this code assumes all others are stable, which isn't a valid assumption.) I found a couple other places that seem to be wanting a stable sort and are going to some extra effort to get it.
Using the C qsort function requires the element type of the array to be trivial. That's a non-obvious requirement, especially for GrowableArray.
Much of this could be dealt with by using the existing QuickSort::sort utility, which is entirely C++, and may be able to inline the comparison function.
(An alternative would be to use one of the Standard Library sorting algorithms, but HotSpot code mostly avoids using the Standard Library.)
- relates to
-
JDK-8333133 Simplify QuickSort::sort
- Resolved