HomeFreeBSD

Add <sys/queue_mergesort.h>

Description

Add <sys/queue_mergesort.h>

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
Reviewed by: jhb (previous version)
Sponsored by: https://www.patreon.com/cperciva
Differential Revision: https://reviews.freebsd.org/D41073

Details

Provenance
cpercivaAuthored on Jul 18 2023, 12:07 AM
Reviewer
jhb
Differential Revision
D41073: Add <sys/queue_mergesort.h>
Parents
rG79fafc09740a: queue.h: Define {LIST,TAILQ}_REMOVE_HEAD
Branches
Unknown
Tags
Unknown