Bug 214248 - mergesort_r should exist
Summary: mergesort_r should exist
Status: New
Alias: None
Product: Base System
Classification: Unclassified
Component: bin (show other bugs)
Version: CURRENT
Hardware: Any Any
: --- Affects Only Me
Assignee: freebsd-bugs (Nobody)
Depends on:
Reported: 2016-11-05 17:43 UTC by Dave
Modified: 2018-02-22 21:49 UTC (History)
2 users (show)

See Also:


Note You need to log in before you can comment on or make changes to this bug.
Description Dave 2016-11-05 17:43:48 UTC
For the same reason that there is a qsort_r there should be a mergesort_r and _r variants of the other sorts.

qsort_r is needed when using it from a foreign language like Swift. Mergesort is superior in many respects but cannot be used because there is no mergesort_r.
Comment 1 Conrad Meyer freebsd_committer 2017-01-14 05:16:44 UTC
Yeah, agreed.

It looks like we're moving towards standardizing qsort_r on thunk-last (the opposite of the current qsort_r), so that the non-thunk version can share code with the thunk version.  See http://austingroupbugs.net/view.php?id=900 and https://reviews.freebsd.org/D9169 .  I'd add it similarly to mergesort.
Comment 2 Brooks Davis freebsd_committer 2017-01-16 17:38:26 UTC
We should also replace our mergesort with a version that doesn't have have the limitation that width be >= sizeof(void *) / 2.  As things stand, you can't sort char's on any platform and shorts on 64-bit platform.  For any usable fatpointer scheme you can't sort any primitive type.

In CheriBSD I've replaced mergesort with timsort from https://github.com/patperry/timsort.  It does have a timsort_r, but it would need to be modified to take qsort compatible comparison functions (which I believe just requires reverting a change).
Comment 3 Conrad Meyer freebsd_committer 2017-01-16 17:47:24 UTC
(In reply to Brooks Davis from comment #2)
I believe removing that limitation (or adding timsort) is an orthogonal concern to just adding an _r variant.
Comment 4 Brooks Davis freebsd_committer 2017-01-16 19:43:07 UTC
(In reply to Conrad Meyer from comment #3)
Agreed.  Just wanted to comment in case adding _r requires significant code changes.  If so, it might be time to fix other problems that make our mergesort unsuitable as a qsort replacement.