Bug 214248

Summary: mergesort_r should exist
Product: Base System Reporter: Dave
Component: binAssignee: freebsd-bugs (Nobody) <bugs>
Status: New ---    
Severity: Affects Only Me CC: brooks, cem
Priority: ---    
Version: CURRENT   
Hardware: Any   
OS: Any   

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.