]> git.ipfire.org Git - thirdparty/util-linux.git/commit
lists: add list sorting routine
authorDavidlohr Bueso <dave@gnu.org>
Mon, 12 Dec 2011 22:52:26 +0000 (23:52 +0100)
committerKarel Zak <kzak@redhat.com>
Fri, 16 Dec 2011 11:37:07 +0000 (12:37 +0100)
commit5b9df0280a8a9e34421f5ad26e2b6d09336fc8a0
tree4c2cdff2f96420d98d1e059b48de2172d014430c
parentd466c6a1fe66603227b3ff73a21a45abd77ee826
lists: add list sorting routine

We need a list sorting function, just to mention one example user that could
benefit is the lib/tt code to sort columns.

This patch adds list_sort() which uses the Merge Sort algorithm, behaving
nicely in O(nlog(n)), heavily based on the kernel's implementation[1].  The
private data (void *priv) passed to the comparison function as been removed to
adopt a qsort(3)-like syntax, and IMHO we don't really need it anyways.

[1]: http://git.kernel.org/?p=linux/kernel/git/torvalds/linux.git;a=blob;f=lib/list_sort.c;h=d7325c6b103f0be078ff3672c35c468ed35738f1;hb=HEAD

[kzak@redhat.com: - use size_t in list_sort()]

Signed-off-by: Davidlohr Bueso <dave@gnu.org>
Signed-off-by: Karel Zak <kzak@redhat.com>
include/c.h
include/list.h