* [PATCH] lists: add list sorting routine
@ 2011-12-12 22:52 Davidlohr Bueso
2011-12-12 22:55 ` Davidlohr Bueso
2011-12-16 11:42 ` Karel Zak
0 siblings, 2 replies; 6+ messages in thread
From: Davidlohr Bueso @ 2011-12-12 22:52 UTC (permalink / raw)
To: Karel Zak; +Cc: util-linux
From: Davidlohr Bueso <dave@gnu.org>
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
Signed-off-by: Davidlohr Bueso <dave@gnu.org>
---
include/c.h | 8 +++
include/list.h | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 140 insertions(+), 0 deletions(-)
diff --git a/include/c.h b/include/c.h
index c4a95aa..290303e 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;
diff --git a/include/list.h b/include/list.h
index f7b17fe..afcfeeb 100644
--- a/include/list.h
+++ b/include/list.h
@@ -3,6 +3,7 @@
* Copyright (C) 1999-2008 by Theodore Ts'o
*
* (based on list.h from e2fsprogs)
+ * Merge sort based on kernel's implementation.
*/
#ifndef UTIL_LINUX_LIST_H
@@ -192,6 +193,137 @@ _INLINE_ void list_splice(struct list_head *list, struct list_head *head)
for (pos = (head)->next, pnext = pos->next; pos != (head); \
pos = pnext, pnext = pos->next)
+#define MAX_LIST_LENGTH_BITS 20
+
+/*
+ * Returns a list organized in an intermediate format suited
+ * to chaining of merge() calls: null-terminated, no reserved or
+ * sentinel head node, "prev" links not maintained.
+ */
+static struct list_head *merge(int (*cmp)(struct list_head *a,
+ struct list_head *b),
+ struct list_head *a, struct list_head *b)
+{
+ struct list_head head, *tail = &head;
+
+ while (a && b) {
+ /* if equal, take 'a' -- important for sort stability */
+ if ((*cmp)(a, b) <= 0) {
+ tail->next = a;
+ a = a->next;
+ } else {
+ tail->next = b;
+ b = b->next;
+ }
+ tail = tail->next;
+ }
+ tail->next = a?:b;
+ return head.next;
+}
+
+/*
+ * Combine final list merge with restoration of standard doubly-linked
+ * list structure. This approach duplicates code from merge(), but
+ * runs faster than the tidier alternatives of either a separate final
+ * prev-link restoration pass, or maintaining the prev links
+ * throughout.
+ */
+static void merge_and_restore_back_links(int (*cmp)(struct list_head *a,
+ struct list_head *b),
+ struct list_head *head,
+ struct list_head *a, struct list_head *b)
+{
+ struct list_head *tail = head;
+
+ while (a && b) {
+ /* if equal, take 'a' -- important for sort stability */
+ if ((*cmp)(a, b) <= 0) {
+ tail->next = a;
+ a->prev = tail;
+ a = a->next;
+ } else {
+ tail->next = b;
+ b->prev = tail;
+ b = b->next;
+ }
+ tail = tail->next;
+ }
+ tail->next = a ? : b;
+
+ do {
+ /*
+ * In worst cases this loop may run many iterations.
+ * Continue callbacks to the client even though no
+ * element comparison is needed, so the client's cmp()
+ * routine can invoke cond_resched() periodically.
+ */
+ (*cmp)(tail->next, tail->next);
+
+ tail->next->prev = tail;
+ tail = tail->next;
+ } while (tail->next);
+
+ tail->next = head;
+ head->prev = tail;
+}
+
+
+/**
+ * list_sort - sort a list
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * This function implements "merge sort", which has O(nlog(n))
+ * complexity.
+ *
+ * The comparison function @cmp must return a negative value if @a
+ * should sort before @b, and a positive value if @a should sort after
+ * @b. If @a and @b are equivalent, and their original relative
+ * ordering is to be preserved, @cmp must return 0.
+ */
+_INLINE_ void list_sort(struct list_head *head,
+ int (*cmp)(struct list_head *a,
+ struct list_head *b))
+{
+ struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
+ -- last slot is a sentinel */
+ int lev; /* index into part[] */
+ int max_lev = 0;
+ struct list_head *list;
+
+ if (list_empty(head))
+ return;
+
+ memset(part, 0, sizeof(part));
+
+ head->prev->next = NULL;
+ list = head->next;
+
+ while (list) {
+ struct list_head *cur = list;
+ list = list->next;
+ cur->next = NULL;
+
+ for (lev = 0; part[lev]; lev++) {
+ cur = merge(cmp, part[lev], cur);
+ part[lev] = NULL;
+ }
+ if (lev > max_lev) {
+ /* list passed to list_sort() too long for efficiency */
+ if (lev >= ARRAY_SIZE(part)-1)
+ lev--;
+ max_lev = lev;
+ }
+ part[lev] = cur;
+ }
+
+ for (lev = 0; lev < max_lev; lev++)
+ if (part[lev])
+ list = merge(cmp, part[lev], list);
+
+ merge_and_restore_back_links(cmp, head, part[max_lev], list);
+}
+
#undef _INLINE_
#endif /* UTIL_LINUX_LIST_H */
--
1.7.4.1
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH] lists: add list sorting routine
2011-12-12 22:52 [PATCH] lists: add list sorting routine Davidlohr Bueso
@ 2011-12-12 22:55 ` Davidlohr Bueso
2011-12-13 9:26 ` Karel Zak
2011-12-16 11:42 ` Karel Zak
1 sibling, 1 reply; 6+ messages in thread
From: Davidlohr Bueso @ 2011-12-12 22:55 UTC (permalink / raw)
To: Karel Zak; +Cc: util-linux
One note: the code is added to the header file instead of its own C file
so we don't have to update all the build rules of the list.h users.
Thanks,
Davidlohr
On Mon, 2011-12-12 at 23:52 +0100, Davidlohr Bueso wrote:
> From: Davidlohr Bueso <dave@gnu.org>
>
> 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
>
> Signed-off-by: Davidlohr Bueso <dave@gnu.org>
> ---
> include/c.h | 8 +++
> include/list.h | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 140 insertions(+), 0 deletions(-)
>
> diff --git a/include/c.h b/include/c.h
> index c4a95aa..290303e 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;
> diff --git a/include/list.h b/include/list.h
> index f7b17fe..afcfeeb 100644
> --- a/include/list.h
> +++ b/include/list.h
> @@ -3,6 +3,7 @@
> * Copyright (C) 1999-2008 by Theodore Ts'o
> *
> * (based on list.h from e2fsprogs)
> + * Merge sort based on kernel's implementation.
> */
>
> #ifndef UTIL_LINUX_LIST_H
> @@ -192,6 +193,137 @@ _INLINE_ void list_splice(struct list_head *list, struct list_head *head)
> for (pos = (head)->next, pnext = pos->next; pos != (head); \
> pos = pnext, pnext = pos->next)
>
> +#define MAX_LIST_LENGTH_BITS 20
> +
> +/*
> + * Returns a list organized in an intermediate format suited
> + * to chaining of merge() calls: null-terminated, no reserved or
> + * sentinel head node, "prev" links not maintained.
> + */
> +static struct list_head *merge(int (*cmp)(struct list_head *a,
> + struct list_head *b),
> + struct list_head *a, struct list_head *b)
> +{
> + struct list_head head, *tail = &head;
> +
> + while (a && b) {
> + /* if equal, take 'a' -- important for sort stability */
> + if ((*cmp)(a, b) <= 0) {
> + tail->next = a;
> + a = a->next;
> + } else {
> + tail->next = b;
> + b = b->next;
> + }
> + tail = tail->next;
> + }
> + tail->next = a?:b;
> + return head.next;
> +}
> +
> +/*
> + * Combine final list merge with restoration of standard doubly-linked
> + * list structure. This approach duplicates code from merge(), but
> + * runs faster than the tidier alternatives of either a separate final
> + * prev-link restoration pass, or maintaining the prev links
> + * throughout.
> + */
> +static void merge_and_restore_back_links(int (*cmp)(struct list_head *a,
> + struct list_head *b),
> + struct list_head *head,
> + struct list_head *a, struct list_head *b)
> +{
> + struct list_head *tail = head;
> +
> + while (a && b) {
> + /* if equal, take 'a' -- important for sort stability */
> + if ((*cmp)(a, b) <= 0) {
> + tail->next = a;
> + a->prev = tail;
> + a = a->next;
> + } else {
> + tail->next = b;
> + b->prev = tail;
> + b = b->next;
> + }
> + tail = tail->next;
> + }
> + tail->next = a ? : b;
> +
> + do {
> + /*
> + * In worst cases this loop may run many iterations.
> + * Continue callbacks to the client even though no
> + * element comparison is needed, so the client's cmp()
> + * routine can invoke cond_resched() periodically.
> + */
> + (*cmp)(tail->next, tail->next);
> +
> + tail->next->prev = tail;
> + tail = tail->next;
> + } while (tail->next);
> +
> + tail->next = head;
> + head->prev = tail;
> +}
> +
> +
> +/**
> + * list_sort - sort a list
> + * @head: the list to sort
> + * @cmp: the elements comparison function
> + *
> + * This function implements "merge sort", which has O(nlog(n))
> + * complexity.
> + *
> + * The comparison function @cmp must return a negative value if @a
> + * should sort before @b, and a positive value if @a should sort after
> + * @b. If @a and @b are equivalent, and their original relative
> + * ordering is to be preserved, @cmp must return 0.
> + */
> +_INLINE_ void list_sort(struct list_head *head,
> + int (*cmp)(struct list_head *a,
> + struct list_head *b))
> +{
> + struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
> + -- last slot is a sentinel */
> + int lev; /* index into part[] */
> + int max_lev = 0;
> + struct list_head *list;
> +
> + if (list_empty(head))
> + return;
> +
> + memset(part, 0, sizeof(part));
> +
> + head->prev->next = NULL;
> + list = head->next;
> +
> + while (list) {
> + struct list_head *cur = list;
> + list = list->next;
> + cur->next = NULL;
> +
> + for (lev = 0; part[lev]; lev++) {
> + cur = merge(cmp, part[lev], cur);
> + part[lev] = NULL;
> + }
> + if (lev > max_lev) {
> + /* list passed to list_sort() too long for efficiency */
> + if (lev >= ARRAY_SIZE(part)-1)
> + lev--;
> + max_lev = lev;
> + }
> + part[lev] = cur;
> + }
> +
> + for (lev = 0; lev < max_lev; lev++)
> + if (part[lev])
> + list = merge(cmp, part[lev], list);
> +
> + merge_and_restore_back_links(cmp, head, part[max_lev], list);
> +}
> +
> #undef _INLINE_
>
> #endif /* UTIL_LINUX_LIST_H */
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] lists: add list sorting routine
2011-12-12 22:55 ` Davidlohr Bueso
@ 2011-12-13 9:26 ` Karel Zak
2011-12-13 10:56 ` Davidlohr Bueso
0 siblings, 1 reply; 6+ messages in thread
From: Karel Zak @ 2011-12-13 9:26 UTC (permalink / raw)
To: Davidlohr Bueso; +Cc: util-linux
On Mon, Dec 12, 2011 at 11:55:57PM +0100, Davidlohr Bueso wrote:
> One note: the code is added to the header file instead of its own C file
> so we don't have to update all the build rules of the list.h users.
[...]
> > +static struct list_head *merge(int (*cmp)(struct list_head *a,
> > + struct list_head *b),
> > + struct list_head *a, struct list_head *b)
shouldn't be the function "static inline" (or _INLINE_ ) ?
--
Karel Zak <kzak@redhat.com>
http://karelzak.blogspot.com
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] lists: add list sorting routine
2011-12-13 9:26 ` Karel Zak
@ 2011-12-13 10:56 ` Davidlohr Bueso
2011-12-13 11:46 ` Karel Zak
0 siblings, 1 reply; 6+ messages in thread
From: Davidlohr Bueso @ 2011-12-13 10:56 UTC (permalink / raw)
To: Karel Zak; +Cc: util-linux
On Tue, 2011-12-13 at 10:26 +0100, Karel Zak wrote:
> On Mon, Dec 12, 2011 at 11:55:57PM +0100, Davidlohr Bueso wrote:
> > One note: the code is added to the header file instead of its own C file
> > so we don't have to update all the build rules of the list.h users.
>
> [...]
>
> > > +static struct list_head *merge(int (*cmp)(struct list_head *a,
> > > + struct list_head *b),
> > > + struct list_head *a, struct list_head *b)
>
> shouldn't be the function "static inline" (or _INLINE_ ) ?
Hmm yes, do you want me to send another patch with the correction?
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] lists: add list sorting routine
2011-12-13 10:56 ` Davidlohr Bueso
@ 2011-12-13 11:46 ` Karel Zak
0 siblings, 0 replies; 6+ messages in thread
From: Karel Zak @ 2011-12-13 11:46 UTC (permalink / raw)
To: Davidlohr Bueso; +Cc: util-linux
On Tue, Dec 13, 2011 at 11:56:26AM +0100, Davidlohr Bueso wrote:
> On Tue, 2011-12-13 at 10:26 +0100, Karel Zak wrote:
> > On Mon, Dec 12, 2011 at 11:55:57PM +0100, Davidlohr Bueso wrote:
> > > One note: the code is added to the header file instead of its own C file
> > > so we don't have to update all the build rules of the list.h users.
> >
> > [...]
> >
> > > > +static struct list_head *merge(int (*cmp)(struct list_head *a,
> > > > + struct list_head *b),
> > > > + struct list_head *a, struct list_head *b)
> >
> > shouldn't be the function "static inline" (or _INLINE_ ) ?
>
> Hmm yes, do you want me to send another patch with the correction?
No, I'll fix it.
Karel
--
Karel Zak <kzak@redhat.com>
http://karelzak.blogspot.com
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] lists: add list sorting routine
2011-12-12 22:52 [PATCH] lists: add list sorting routine Davidlohr Bueso
2011-12-12 22:55 ` Davidlohr Bueso
@ 2011-12-16 11:42 ` Karel Zak
1 sibling, 0 replies; 6+ messages in thread
From: Karel Zak @ 2011-12-16 11:42 UTC (permalink / raw)
To: Davidlohr Bueso; +Cc: util-linux
On Mon, Dec 12, 2011 at 11:52:26PM +0100, Davidlohr Bueso wrote:
> include/c.h | 8 +++
> include/list.h | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 140 insertions(+), 0 deletions(-)
Applied, thanks.
> + struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
> + -- last slot is a sentinel */
> + int lev; /* index into part[] */
> + int max_lev = 0;
size_t
> + struct list_head *list;
> +
> + if (list_empty(head))
> + return;
> +
> + memset(part, 0, sizeof(part));
> +
> + head->prev->next = NULL;
> + list = head->next;
> +
> + while (list) {
> + struct list_head *cur = list;
> + list = list->next;
> + cur->next = NULL;
> +
> + for (lev = 0; part[lev]; lev++) {
> + cur = merge(cmp, part[lev], cur);
> + part[lev] = NULL;
> + }
> + if (lev > max_lev) {
> + /* list passed to list_sort() too long for efficiency */
> + if (lev >= ARRAY_SIZE(part)-1)
use -Wsign-compare to get more fun :-)
Karel
--
Karel Zak <kzak@redhat.com>
http://karelzak.blogspot.com
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-12-16 11:42 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2011-12-12 22:52 [PATCH] lists: add list sorting routine Davidlohr Bueso
2011-12-12 22:55 ` Davidlohr Bueso
2011-12-13 9:26 ` Karel Zak
2011-12-13 10:56 ` Davidlohr Bueso
2011-12-13 11:46 ` Karel Zak
2011-12-16 11:42 ` Karel Zak
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).