From 5b9df0280a8a9e34421f5ad26e2b6d09336fc8a0 Mon Sep 17 00:00:00 2001 From: Davidlohr Bueso Date: Mon, 12 Dec 2011 23:52:26 +0100 Subject: 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 Signed-off-by: Karel Zak --- include/c.h | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'include/c.h') diff --git a/include/c.h b/include/c.h index c4a95aa2b..073615ef3 100644 --- a/include/c.h +++ b/include/c.h @@ -104,6 +104,14 @@ _max1 > _max2 ? _max1 : _max2; }) #endif +#ifndef offsetof +#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) +#endif + +#define container_of(ptr, type, member) ({ \ + const __typeof__( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );}) + #ifndef HAVE_PROGRAM_INVOCATION_SHORT_NAME # ifdef HAVE___PROGNAME extern char *__progname; -- cgit v1.2.3-55-g7522