Add <sys/queue_mergesort.h>

[cperciva]

Summary

Thie file provides macros for performing mergesorts and merging two
sorted lists implemented by <sys/queue.h>. The mergesort operates
in guaranteed O(n log n) time and uses constant additional space:
3 or 4 pointers (depending on list type) and 4 size_t values. The
merge operates in guaranteed O(n + m) time and uses constant
additional space: 3 pointers.

In memoriam: hselasky
Sponsored by: https://www.patreon.com/cperciva

[jhb]

sys/sys/queue_mergesort.h

39

Arguably you could do shims here for REMOVE_HEAD for LIST and TAILQ btw rather than adding those to the public interface in queue.h. I might slightly prefer that.

55

I might find it more readable to use a pattern of M_<op> like M_FIRST, M_REMOVE_HEAD, for the helper macros rather than MACRO_<abbreviated op>. Especially for things like MACRO_IH vs MACRO_HI

[cperciva]

sys/sys/queue_mergesort.h

39

That was my first thought, but then I figured that _REMOVE_HEAD could be useful elsewhere... and as emaste noticed, there is in fact one place in the tree where we could be using it already. Since LIST_REMOVE_HEAD and TAILQ_REMOVE_HEAD are plausibly useful in code which isn't using queue_mergesort.h I think it's worth exposing them in queue.h.

55

Good point. I'll revise.

[cperciva]

Use clearer macro names, per jhb

[jrtc27]

sys/sys/queue_mergesort.h

57

style(9) is no space after * (applies throughout file)

[jrtc27]

sys/sys/queue_mergesort.h

182

qsort_r was changed to match POSIX and have the thunk argument passed last

[cperciva]

Fixes per jrtc27

style (no space after *) and location of thunk in sort callback