|Summary:||mergesort_r should exist|
|Component:||bin||Assignee:||freebsd-bugs (Nobody) <bugs>|
|Severity:||Affects Only Me||CC:||brooks, cem|
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 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 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 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.