Re: [PATCH] sort: Introduce generic list_sort function

Re: [PATCH] sort: Introduce generic list_sort function

[Andi Kleen]

Dave Chinner <david@fromorbit.com> writes:
> +
> +/**
> + * list_sort - sort a list.
> + * @priv: private data, passed to @cmp
> + * @head: the list to sort
> + * @cmp: the elements comparison function
> + *
> + * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
> + * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
> + * in ascending order.
> + *
> + * The comparison function @cmp is supposed to return a negative value if @a is
> + * than @b, and a positive value if @a is greater than @b. If @a and @b are
> + * equivalent, then it does not matter what this function returns.
> + */
> +void list_sort(void *priv, struct list_head *head,
> +	       int (*cmp)(void *priv, struct list_head *a,
> +			  struct list_head *b))

No EXPORT_SYMBOL? 

Also it would seem cleaner to have it in a own file.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

[PATCH V3] sort: Introduce generic list_sort function

[Dave Chinner]

On Tue, Jan 05, 2010 at 12:31:15PM +0100, Andi Kleen wrote:
> Dave Chinner <david@fromorbit.com> writes:
> > +
> > +/**
> > + * list_sort - sort a list.
> > + * @priv: private data, passed to @cmp
> > + * @head: the list to sort
> > + * @cmp: the elements comparison function
> > + *
> > + * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
> > + * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
> > + * in ascending order.
> > + *
> > + * The comparison function @cmp is supposed to return a negative value if @a is
> > + * than @b, and a positive value if @a is greater than @b. If @a and @b are
> > + * equivalent, then it does not matter what this function returns.
> > + */
> > +void list_sort(void *priv, struct list_head *head,
> > +	       int (*cmp)(void *priv, struct list_head *a,
> > +			  struct list_head *b))
> 
> No EXPORT_SYMBOL? 

Bah, who uses modules? :P

Fixed. Updated patch below.

> Also it would seem cleaner to have it in a own file.

That might make sense if we had a large number of generic sort
functions and it was difficult to tell the code apart, but we've
only got 2 right now....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

sort: Introduce generic list_sort function

There are two copies of list_sort() in the tree already, one in the DRM code,
another in ubifs. Now XFS needs this as well. Create a generic list_sort()
function from the ubifs version and convert existing users to it so we
don't end up with yet another copy in the tree.

Signed-off-by: Dave Chinner <david@fromorbit.com>
Acked-by: Dave Airlie <airlied@redhat.com>
Acked-by: Artem Bityutskiy <dedekind@infradead.org>
---
V3: Export list_sort()
V2: fix a typo

 drivers/gpu/drm/drm_modes.c |   90 ++-------------------------------------
 fs/ubifs/gc.c               |   95 -----------------------------------------
 include/linux/sort.h        |    5 ++
 lib/sort.c                  |   98 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 107 insertions(+), 181 deletions(-)

diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c
index 51f6772..3846ed4 100644
--- a/drivers/gpu/drm/drm_modes.c
+++ b/drivers/gpu/drm/drm_modes.c
@@ -1,9 +1,4 @@
 /*
- * The list_sort function is (presumably) licensed under the GPL (see the
- * top level "COPYING" file for details).
- *
- * The remainder of this file is:
- *
  * Copyright © 1997-2003 by The XFree86 Project, Inc.
  * Copyright © 2007 Dave Airlie
  * Copyright © 2007-2008 Intel Corporation
@@ -36,6 +31,7 @@
  */
 
 #include <linux/list.h>
+#include <linux/sort.h>
 #include "drmP.h"
 #include "drm.h"
 #include "drm_crtc.h"
@@ -829,6 +825,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
 
 /**
  * drm_mode_compare - compare modes for favorability
+ * @priv: unused
  * @lh_a: list_head for first mode
  * @lh_b: list_head for second mode
  *
@@ -842,7 +839,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
  * Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
  * positive if @lh_b is better than @lh_a.
  */
-static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
+static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
 {
 	struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
 	struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head);
@@ -859,85 +856,6 @@ static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
 	return diff;
 }
 
-/* FIXME: what we don't have a list sort function? */
-/* list sort from Mark J Roberts (mjr@znex.org) */
-void list_sort(struct list_head *head,
-	       int (*cmp)(struct list_head *a, struct list_head *b))
-{
-	struct list_head *p, *q, *e, *list, *tail, *oldhead;
-	int insize, nmerges, psize, qsize, i;
-
-	list = head->next;
-	list_del(head);
-	insize = 1;
-	for (;;) {
-		p = oldhead = list;
-		list = tail = NULL;
-		nmerges = 0;
-
-		while (p) {
-			nmerges++;
-			q = p;
-			psize = 0;
-			for (i = 0; i < insize; i++) {
-				psize++;
-				q = q->next == oldhead ? NULL : q->next;
-				if (!q)
-					break;
-			}
-
-			qsize = insize;
-			while (psize > 0 || (qsize > 0 && q)) {
-				if (!psize) {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				} else if (!qsize || !q) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else if (cmp(p, q) <= 0) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				}
-				if (tail)
-					tail->next = e;
-				else
-					list = e;
-				e->prev = tail;
-				tail = e;
-			}
-			p = q;
-		}
-
-		tail->next = list;
-		list->prev = tail;
-
-		if (nmerges <= 1)
-			break;
-
-		insize *= 2;
-	}
-
-	head->next = list;
-	head->prev = list->prev;
-	list->prev->next = head;
-	list->prev = head;
-}
-
 /**
  * drm_mode_sort - sort mode list
  * @mode_list: list to sort
@@ -949,7 +867,7 @@ void list_sort(struct list_head *head,
  */
 void drm_mode_sort(struct list_head *mode_list)
 {
-	list_sort(mode_list, drm_mode_compare);
+	list_sort(NULL, mode_list, drm_mode_compare);
 }
 EXPORT_SYMBOL(drm_mode_sort);
 
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 618c270..4976e07 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -108,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
 }
 
 /**
- * list_sort - sort a list.
- * @priv: private data, passed to @cmp
- * @head: the list to sort
- * @cmp: the elements comparison function
- *
- * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
- * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
- * in ascending order.
- *
- * The comparison function @cmp is supposed to return a negative value if @a is
- * than @b, and a positive value if @a is greater than @b. If @a and @b are
- * equivalent, then it does not matter what this function returns.
- */
-static void list_sort(void *priv, struct list_head *head,
-		      int (*cmp)(void *priv, struct list_head *a,
-				 struct list_head *b))
-{
-	struct list_head *p, *q, *e, *list, *tail, *oldhead;
-	int insize, nmerges, psize, qsize, i;
-
-	if (list_empty(head))
-		return;
-
-	list = head->next;
-	list_del(head);
-	insize = 1;
-	for (;;) {
-		p = oldhead = list;
-		list = tail = NULL;
-		nmerges = 0;
-
-		while (p) {
-			nmerges++;
-			q = p;
-			psize = 0;
-			for (i = 0; i < insize; i++) {
-				psize++;
-				q = q->next == oldhead ? NULL : q->next;
-				if (!q)
-					break;
-			}
-
-			qsize = insize;
-			while (psize > 0 || (qsize > 0 && q)) {
-				if (!psize) {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				} else if (!qsize || !q) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else if (cmp(priv, p, q) <= 0) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				}
-				if (tail)
-					tail->next = e;
-				else
-					list = e;
-				e->prev = tail;
-				tail = e;
-			}
-			p = q;
-		}
-
-		tail->next = list;
-		list->prev = tail;
-
-		if (nmerges <= 1)
-			break;
-
-		insize *= 2;
-	}
-
-	head->next = list;
-	head->prev = list->prev;
-	list->prev->next = head;
-	list->prev = head;
-}
-
-/**
  * data_nodes_cmp - compare 2 data nodes.
  * @priv: UBIFS file-system description object
  * @a: first data node
diff --git a/include/linux/sort.h b/include/linux/sort.h
index d534da2..99a2ed5 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -3,8 +3,13 @@
 
 #include <linux/types.h>
 
+struct list_head;
+
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
 	  void (*swap)(void *, void *, int));
 
+void list_sort(void *priv, struct list_head *head,
+	       int (*cmp)(void *priv, struct list_head *a,
+			  struct list_head *b));
 #endif
diff --git a/lib/sort.c b/lib/sort.c
index 926d004..a9ce544 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -8,6 +8,7 @@
 #include <linux/module.h>
 #include <linux/sort.h>
 #include <linux/slab.h>
+#include <linux/list.h>
 
 static void u32_swap(void *a, void *b, int size)
 {
@@ -121,3 +122,100 @@ static int sort_test(void)
 
 module_init(sort_test);
 #endif
+
+/**
+ * list_sort - sort a list.
+ * @priv: private data, passed to @cmp
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
+ * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
+ * in ascending order.
+ *
+ * The comparison function @cmp is supposed to return a negative value if @a is
+ * less than @b, and a positive value if @a is greater than @b. If @a and @b
+ * are equivalent, then it does not matter what this function returns.
+ */
+void list_sort(void *priv, struct list_head *head,
+	       int (*cmp)(void *priv, struct list_head *a,
+			  struct list_head *b))
+{
+	struct list_head *p, *q, *e, *list, *tail, *oldhead;
+	int insize, nmerges, psize, qsize, i;
+
+	if (list_empty(head))
+		return;
+
+	list = head->next;
+	list_del(head);
+	insize = 1;
+	for (;;) {
+		p = oldhead = list;
+		list = tail = NULL;
+		nmerges = 0;
+
+		while (p) {
+			nmerges++;
+			q = p;
+			psize = 0;
+			for (i = 0; i < insize; i++) {
+				psize++;
+				q = q->next == oldhead ? NULL : q->next;
+				if (!q)
+					break;
+			}
+
+			qsize = insize;
+			while (psize > 0 || (qsize > 0 && q)) {
+				if (!psize) {
+					e = q;
+					q = q->next;
+					qsize--;
+					if (q == oldhead)
+						q = NULL;
+				} else if (!qsize || !q) {
+					e = p;
+					p = p->next;
+					psize--;
+					if (p == oldhead)
+						p = NULL;
+				} else if (cmp(priv, p, q) <= 0) {
+					e = p;
+					p = p->next;
+					psize--;
+					if (p == oldhead)
+						p = NULL;
+				} else {
+					e = q;
+					q = q->next;
+					qsize--;
+					if (q == oldhead)
+						q = NULL;
+				}
+				if (tail)
+					tail->next = e;
+				else
+					list = e;
+				e->prev = tail;
+				tail = e;
+			}
+			p = q;
+		}
+
+		tail->next = list;
+		list->prev = tail;
+
+		if (nmerges <= 1)
+			break;
+
+		insize *= 2;
+	}
+
+	head->next = list;
+	head->prev = list->prev;
+	list->prev->next = head;
+	list->prev = head;
+}
+
+EXPORT_SYMBOL(list_sort);

Re: [PATCH V3] sort: Introduce generic list_sort function

[Andi Kleen]

> > Also it would seem cleaner to have it in a own file.
> 
> That might make sense if we had a large number of generic sort
> functions and it was difficult to tell the code apart, but we've
> only got 2 right now....

I was more thinking of the case that it can be easily made a lib-y
and then eliminated by the linker on non modular kernels if not needed
(unfortunately that would require putting the EXPORT_SYMBOL somewhere else)

-Andi

Re: [PATCH V3] sort: Introduce generic list_sort function

[Christoph Hellwig]

On Tue, Jan 05, 2010 at 01:52:35PM +0100, Andi Kleen wrote:
> > > Also it would seem cleaner to have it in a own file.
> > 
> > That might make sense if we had a large number of generic sort
> > functions and it was difficult to tell the code apart, but we've
> > only got 2 right now....
> 
> I was more thinking of the case that it can be easily made a lib-y
> and then eliminated by the linker on non modular kernels if not needed
> (unfortunately that would require putting the EXPORT_SYMBOL somewhere else)

lib-y doesn't work together with EXPORT_SYMBOL, having the export
outside would also always pull it in.  These days the whole lib-y mess
doesn't make sense anymore - if we really need an optional library
symbol we can just pull it in through a Kconfig variable.

Re: [PATCH V3] sort: Introduce generic list_sort function

[Andi Kleen]

> lib-y doesn't work together with EXPORT_SYMBOL, having the export
> outside would also always pull it in.  These days the whole lib-y mess
> doesn't make sense anymore - if we really need an optional library
> symbol we can just pull it in through a Kconfig variable.

It works for non modular kernels with CONFIG_MODULES turned off.

See also the other patch I posted yesterday to fix this for 
lib/*

-Andi


-- 
ak@linux.intel.com -- Speaking for myself only.

[PATCH] sort: Introduce generic list_sort function

[Dave Chinner]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 9209 bytes --]

There are two copies of list_sort() in the tree already, one in the DRM code,
another in ubifs. Now XFS needs this as well. Create a generic list_sort()
function from the ubifs version and convert existing users to it so we
don't end up with yet another copy in the tree.

CC: Dave Airlie <airlied@redhat.com>
CC: Artem Bityutskiy <dedekind@infradead.org>
CC: Adrian Hunter <adrian.hunter@nokia.com>

Signed-off-by: Dave Chinner <david@fromorbit.com>
---
 drivers/gpu/drm/drm_modes.c |   90 ++--------------------------------------
 fs/ubifs/gc.c               |   95 ------------------------------------------
 include/linux/sort.h        |    5 ++
 lib/sort.c                  |   97 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 106 insertions(+), 181 deletions(-)

diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c
index 51f6772..3846ed4 100644
--- a/drivers/gpu/drm/drm_modes.c
+++ b/drivers/gpu/drm/drm_modes.c
@@ -1,9 +1,4 @@
 /*
- * The list_sort function is (presumably) licensed under the GPL (see the
- * top level "COPYING" file for details).
- *
- * The remainder of this file is:
- *
  * Copyright © 1997-2003 by The XFree86 Project, Inc.
  * Copyright © 2007 Dave Airlie
  * Copyright © 2007-2008 Intel Corporation
@@ -36,6 +31,7 @@
  */
 
 #include <linux/list.h>
+#include <linux/sort.h>
 #include "drmP.h"
 #include "drm.h"
 #include "drm_crtc.h"
@@ -829,6 +825,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
 
 /**
  * drm_mode_compare - compare modes for favorability
+ * @priv: unused
  * @lh_a: list_head for first mode
  * @lh_b: list_head for second mode
  *
@@ -842,7 +839,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
  * Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
  * positive if @lh_b is better than @lh_a.
  */
-static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
+static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
 {
 	struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
 	struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head);
@@ -859,85 +856,6 @@ static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
 	return diff;
 }
 
-/* FIXME: what we don't have a list sort function? */
-/* list sort from Mark J Roberts (mjr@znex.org) */
-void list_sort(struct list_head *head,
-	       int (*cmp)(struct list_head *a, struct list_head *b))
-{
-	struct list_head *p, *q, *e, *list, *tail, *oldhead;
-	int insize, nmerges, psize, qsize, i;
-
-	list = head->next;
-	list_del(head);
-	insize = 1;
-	for (;;) {
-		p = oldhead = list;
-		list = tail = NULL;
-		nmerges = 0;
-
-		while (p) {
-			nmerges++;
-			q = p;
-			psize = 0;
-			for (i = 0; i < insize; i++) {
-				psize++;
-				q = q->next == oldhead ? NULL : q->next;
-				if (!q)
-					break;
-			}
-
-			qsize = insize;
-			while (psize > 0 || (qsize > 0 && q)) {
-				if (!psize) {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				} else if (!qsize || !q) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else if (cmp(p, q) <= 0) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				}
-				if (tail)
-					tail->next = e;
-				else
-					list = e;
-				e->prev = tail;
-				tail = e;
-			}
-			p = q;
-		}
-
-		tail->next = list;
-		list->prev = tail;
-
-		if (nmerges <= 1)
-			break;
-
-		insize *= 2;
-	}
-
-	head->next = list;
-	head->prev = list->prev;
-	list->prev->next = head;
-	list->prev = head;
-}
-
 /**
  * drm_mode_sort - sort mode list
  * @mode_list: list to sort
@@ -949,7 +867,7 @@ void list_sort(struct list_head *head,
  */
 void drm_mode_sort(struct list_head *mode_list)
 {
-	list_sort(mode_list, drm_mode_compare);
+	list_sort(NULL, mode_list, drm_mode_compare);
 }
 EXPORT_SYMBOL(drm_mode_sort);
 
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 618c270..4976e07 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -108,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
 }
 
 /**
- * list_sort - sort a list.
- * @priv: private data, passed to @cmp
- * @head: the list to sort
- * @cmp: the elements comparison function
- *
- * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
- * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
- * in ascending order.
- *
- * The comparison function @cmp is supposed to return a negative value if @a is
- * than @b, and a positive value if @a is greater than @b. If @a and @b are
- * equivalent, then it does not matter what this function returns.
- */
-static void list_sort(void *priv, struct list_head *head,
-		      int (*cmp)(void *priv, struct list_head *a,
-				 struct list_head *b))
-{
-	struct list_head *p, *q, *e, *list, *tail, *oldhead;
-	int insize, nmerges, psize, qsize, i;
-
-	if (list_empty(head))
-		return;
-
-	list = head->next;
-	list_del(head);
-	insize = 1;
-	for (;;) {
-		p = oldhead = list;
-		list = tail = NULL;
-		nmerges = 0;
-
-		while (p) {
-			nmerges++;
-			q = p;
-			psize = 0;
-			for (i = 0; i < insize; i++) {
-				psize++;
-				q = q->next == oldhead ? NULL : q->next;
-				if (!q)
-					break;
-			}
-
-			qsize = insize;
-			while (psize > 0 || (qsize > 0 && q)) {
-				if (!psize) {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				} else if (!qsize || !q) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else if (cmp(priv, p, q) <= 0) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				}
-				if (tail)
-					tail->next = e;
-				else
-					list = e;
-				e->prev = tail;
-				tail = e;
-			}
-			p = q;
-		}
-
-		tail->next = list;
-		list->prev = tail;
-
-		if (nmerges <= 1)
-			break;
-
-		insize *= 2;
-	}
-
-	head->next = list;
-	head->prev = list->prev;
-	list->prev->next = head;
-	list->prev = head;
-}
-
-/**
  * data_nodes_cmp - compare 2 data nodes.
  * @priv: UBIFS file-system description object
  * @a: first data node
diff --git a/include/linux/sort.h b/include/linux/sort.h
index d534da2..99a2ed5 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -3,8 +3,13 @@
 
 #include <linux/types.h>
 
+struct list_head;
+
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
 	  void (*swap)(void *, void *, int));
 
+void list_sort(void *priv, struct list_head *head,
+	       int (*cmp)(void *priv, struct list_head *a,
+			  struct list_head *b));
 #endif
diff --git a/lib/sort.c b/lib/sort.c
index 926d004..1772c45 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -8,6 +8,7 @@
 #include <linux/module.h>
 #include <linux/sort.h>
 #include <linux/slab.h>
+#include <linux/list.h>
 
 static void u32_swap(void *a, void *b, int size)
 {
@@ -121,3 +122,99 @@ static int sort_test(void)
 
 module_init(sort_test);
 #endif
+
+/**
+ * list_sort - sort a list.
+ * @priv: private data, passed to @cmp
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
+ * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
+ * in ascending order.
+ *
+ * The comparison function @cmp is supposed to return a negative value if @a is
+ * than @b, and a positive value if @a is greater than @b. If @a and @b are
+ * equivalent, then it does not matter what this function returns.
+ */
+void list_sort(void *priv, struct list_head *head,
+	       int (*cmp)(void *priv, struct list_head *a,
+			  struct list_head *b))
+{
+	struct list_head *p, *q, *e, *list, *tail, *oldhead;
+	int insize, nmerges, psize, qsize, i;
+
+	if (list_empty(head))
+		return;
+
+	list = head->next;
+	list_del(head);
+	insize = 1;
+	for (;;) {
+		p = oldhead = list;
+		list = tail = NULL;
+		nmerges = 0;
+
+		while (p) {
+			nmerges++;
+			q = p;
+			psize = 0;
+			for (i = 0; i < insize; i++) {
+				psize++;
+				q = q->next == oldhead ? NULL : q->next;
+				if (!q)
+					break;
+			}
+
+			qsize = insize;
+			while (psize > 0 || (qsize > 0 && q)) {
+				if (!psize) {
+					e = q;
+					q = q->next;
+					qsize--;
+					if (q == oldhead)
+						q = NULL;
+				} else if (!qsize || !q) {
+					e = p;
+					p = p->next;
+					psize--;
+					if (p == oldhead)
+						p = NULL;
+				} else if (cmp(priv, p, q) <= 0) {
+					e = p;
+					p = p->next;
+					psize--;
+					if (p == oldhead)
+						p = NULL;
+				} else {
+					e = q;
+					q = q->next;
+					qsize--;
+					if (q == oldhead)
+						q = NULL;
+				}
+				if (tail)
+					tail->next = e;
+				else
+					list = e;
+				e->prev = tail;
+				tail = e;
+			}
+			p = q;
+		}
+
+		tail->next = list;
+		list->prev = tail;
+
+		if (nmerges <= 1)
+			break;
+
+		insize *= 2;
+	}
+
+	head->next = list;
+	head->prev = list->prev;
+	list->prev->next = head;
+	list->prev = head;
+}
+
-- 
1.6.5

Re: [PATCH] sort: Introduce generic list_sort function

[Dave Airlie]

On Tue, 2010-01-05 at 10:54 +1100, Dave Chinner wrote:
> There are two copies of list_sort() in the tree already, one in the DRM code,
> another in ubifs. Now XFS needs this as well. Create a generic list_sort()
> function from the ubifs version and convert existing users to it so we
> don't end up with yet another copy in the tree.

Acked-by: Dave Airlie <airlied@redhat.com>

Meant to do this myself when we imported modesetting, but never got
around to it,

Thanks,
Dave.

Re: [PATCH] sort: Introduce generic list_sort function

[Artem Bityutskiy]

On Tue, 2010-01-05 at 10:54 +1100, Dave Chinner wrote:
> There are two copies of list_sort() in the tree already, one in the DRM code,
> another in ubifs. Now XFS needs this as well. Create a generic list_sort()
> function from the ubifs version and convert existing users to it so we
> don't end up with yet another copy in the tree.
> 
> CC: Dave Airlie <airlied@redhat.com>
> CC: Artem Bityutskiy <dedekind@infradead.org>
> CC: Adrian Hunter <adrian.hunter@nokia.com>
> 
> Signed-off-by: Dave Chinner <david@fromorbit.com>

Acked-by: Artem Bityutskiy <dedekind@infradead.org>

Thanks, this has been in my TODO list for long time as well :-)

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Re: [PATCH] sort: Introduce generic list_sort function

[Artem Bityutskiy]

On Tue, 2010-01-05 at 10:54 +1100, Dave Chinner wrote:
> There are two copies of list_sort() in the tree already, one in the DRM code,
> another in ubifs. Now XFS needs this as well. Create a generic list_sort()
> function from the ubifs version and convert existing users to it so we
> don't end up with yet another copy in the tree.
> 
> CC: Dave Airlie <airlied@redhat.com>
> CC: Artem Bityutskiy <dedekind@infradead.org>
> CC: Adrian Hunter <adrian.hunter@nokia.com>
> 
> Signed-off-by: Dave Chinner <david@fromorbit.com>
> ---
>  drivers/gpu/drm/drm_modes.c |   90 ++--------------------------------------
>  fs/ubifs/gc.c               |   95 ------------------------------------------
>  include/linux/sort.h        |    5 ++
>  lib/sort.c                  |   97 +++++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 106 insertions(+), 181 deletions(-)
> 
> diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c
> index 51f6772..3846ed4 100644
> --- a/drivers/gpu/drm/drm_modes.c
> +++ b/drivers/gpu/drm/drm_modes.c
> @@ -1,9 +1,4 @@
>  /*
> - * The list_sort function is (presumably) licensed under the GPL (see the
> - * top level "COPYING" file for details).
> - *
> - * The remainder of this file is:
> - *
>   * Copyright © 1997-2003 by The XFree86 Project, Inc.
>   * Copyright © 2007 Dave Airlie
>   * Copyright © 2007-2008 Intel Corporation
> @@ -36,6 +31,7 @@
>   */
>  
>  #include <linux/list.h>
> +#include <linux/sort.h>
>  #include "drmP.h"
>  #include "drm.h"
>  #include "drm_crtc.h"
> @@ -829,6 +825,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
>  
>  /**
>   * drm_mode_compare - compare modes for favorability
> + * @priv: unused
>   * @lh_a: list_head for first mode
>   * @lh_b: list_head for second mode
>   *
> @@ -842,7 +839,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
>   * Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
>   * positive if @lh_b is better than @lh_a.
>   */
> -static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
> +static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
>  {
>  	struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
>  	struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head);
> @@ -859,85 +856,6 @@ static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
>  	return diff;
>  }
>  
> -/* FIXME: what we don't have a list sort function? */
> -/* list sort from Mark J Roberts (mjr@znex.org) */
> -void list_sort(struct list_head *head,
> -	       int (*cmp)(struct list_head *a, struct list_head *b))
> -{
> -	struct list_head *p, *q, *e, *list, *tail, *oldhead;
> -	int insize, nmerges, psize, qsize, i;
> -
> -	list = head->next;
> -	list_del(head);
> -	insize = 1;
> -	for (;;) {
> -		p = oldhead = list;
> -		list = tail = NULL;
> -		nmerges = 0;
> -
> -		while (p) {
> -			nmerges++;
> -			q = p;
> -			psize = 0;
> -			for (i = 0; i < insize; i++) {
> -				psize++;
> -				q = q->next == oldhead ? NULL : q->next;
> -				if (!q)
> -					break;
> -			}
> -
> -			qsize = insize;
> -			while (psize > 0 || (qsize > 0 && q)) {
> -				if (!psize) {
> -					e = q;
> -					q = q->next;
> -					qsize--;
> -					if (q == oldhead)
> -						q = NULL;
> -				} else if (!qsize || !q) {
> -					e = p;
> -					p = p->next;
> -					psize--;
> -					if (p == oldhead)
> -						p = NULL;
> -				} else if (cmp(p, q) <= 0) {
> -					e = p;
> -					p = p->next;
> -					psize--;
> -					if (p == oldhead)
> -						p = NULL;
> -				} else {
> -					e = q;
> -					q = q->next;
> -					qsize--;
> -					if (q == oldhead)
> -						q = NULL;
> -				}
> -				if (tail)
> -					tail->next = e;
> -				else
> -					list = e;
> -				e->prev = tail;
> -				tail = e;
> -			}
> -			p = q;
> -		}
> -
> -		tail->next = list;
> -		list->prev = tail;
> -
> -		if (nmerges <= 1)
> -			break;
> -
> -		insize *= 2;
> -	}
> -
> -	head->next = list;
> -	head->prev = list->prev;
> -	list->prev->next = head;
> -	list->prev = head;
> -}
> -
>  /**
>   * drm_mode_sort - sort mode list
>   * @mode_list: list to sort
> @@ -949,7 +867,7 @@ void list_sort(struct list_head *head,
>   */
>  void drm_mode_sort(struct list_head *mode_list)
>  {
> -	list_sort(mode_list, drm_mode_compare);
> +	list_sort(NULL, mode_list, drm_mode_compare);
>  }
>  EXPORT_SYMBOL(drm_mode_sort);
>  
> diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
> index 618c270..4976e07 100644
> --- a/fs/ubifs/gc.c
> +++ b/fs/ubifs/gc.c
> @@ -108,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
>  }
>  
>  /**
> - * list_sort - sort a list.
> - * @priv: private data, passed to @cmp
> - * @head: the list to sort
> - * @cmp: the elements comparison function
> - *
> - * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
> - * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
> - * in ascending order.
> - *
> - * The comparison function @cmp is supposed to return a negative value if @a is
> - * than @b, and a positive value if @a is greater than @b. If @a and @b are
> - * equivalent, then it does not matter what this function returns.
> - */
> -static void list_sort(void *priv, struct list_head *head,
> -		      int (*cmp)(void *priv, struct list_head *a,
> -				 struct list_head *b))
> -{
> -	struct list_head *p, *q, *e, *list, *tail, *oldhead;
> -	int insize, nmerges, psize, qsize, i;
> -
> -	if (list_empty(head))
> -		return;
> -
> -	list = head->next;
> -	list_del(head);
> -	insize = 1;
> -	for (;;) {
> -		p = oldhead = list;
> -		list = tail = NULL;
> -		nmerges = 0;
> -
> -		while (p) {
> -			nmerges++;
> -			q = p;
> -			psize = 0;
> -			for (i = 0; i < insize; i++) {
> -				psize++;
> -				q = q->next == oldhead ? NULL : q->next;
> -				if (!q)
> -					break;
> -			}
> -
> -			qsize = insize;
> -			while (psize > 0 || (qsize > 0 && q)) {
> -				if (!psize) {
> -					e = q;
> -					q = q->next;
> -					qsize--;
> -					if (q == oldhead)
> -						q = NULL;
> -				} else if (!qsize || !q) {
> -					e = p;
> -					p = p->next;
> -					psize--;
> -					if (p == oldhead)
> -						p = NULL;
> -				} else if (cmp(priv, p, q) <= 0) {
> -					e = p;
> -					p = p->next;
> -					psize--;
> -					if (p == oldhead)
> -						p = NULL;
> -				} else {
> -					e = q;
> -					q = q->next;
> -					qsize--;
> -					if (q == oldhead)
> -						q = NULL;
> -				}
> -				if (tail)
> -					tail->next = e;
> -				else
> -					list = e;
> -				e->prev = tail;
> -				tail = e;
> -			}
> -			p = q;
> -		}
> -
> -		tail->next = list;
> -		list->prev = tail;
> -
> -		if (nmerges <= 1)
> -			break;
> -
> -		insize *= 2;
> -	}
> -
> -	head->next = list;
> -	head->prev = list->prev;
> -	list->prev->next = head;
> -	list->prev = head;
> -}
> -
> -/**
>   * data_nodes_cmp - compare 2 data nodes.
>   * @priv: UBIFS file-system description object
>   * @a: first data node
> diff --git a/include/linux/sort.h b/include/linux/sort.h
> index d534da2..99a2ed5 100644
> --- a/include/linux/sort.h
> +++ b/include/linux/sort.h
> @@ -3,8 +3,13 @@
>  
>  #include <linux/types.h>
>  
> +struct list_head;
> +
>  void sort(void *base, size_t num, size_t size,
>  	  int (*cmp)(const void *, const void *),
>  	  void (*swap)(void *, void *, int));
>  
> +void list_sort(void *priv, struct list_head *head,
> +	       int (*cmp)(void *priv, struct list_head *a,
> +			  struct list_head *b));
>  #endif
> diff --git a/lib/sort.c b/lib/sort.c
> index 926d004..1772c45 100644
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -8,6 +8,7 @@
>  #include <linux/module.h>
>  #include <linux/sort.h>
>  #include <linux/slab.h>
> +#include <linux/list.h>
>  
>  static void u32_swap(void *a, void *b, int size)
>  {
> @@ -121,3 +122,99 @@ static int sort_test(void)
>  
>  module_init(sort_test);
>  #endif
> +
> +/**
> + * list_sort - sort a list.
> + * @priv: private data, passed to @cmp
> + * @head: the list to sort
> + * @cmp: the elements comparison function
> + *
> + * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
> + * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
> + * in ascending order.
> + *
> + * The comparison function @cmp is supposed to return a negative value if @a is
> + * than @b, and a positive value if @a is greater than @b. If @a and @b are

While you are on it, could you also please fix the typo: "if @a is less
than @b".

> + * equivalent, then it does not matter what this function returns.
> + */

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Re: [PATCH] sort: Introduce generic list_sort function

[Dave Chinner]

On Tue, Jan 05, 2010 at 08:26:11AM +0200, Artem Bityutskiy wrote:
> > + * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
> > + * in ascending order.
> > + *
> > + * The comparison function @cmp is supposed to return a negative value if @a is
> > + * than @b, and a positive value if @a is greater than @b. If @a and @b are
> 
> While you are on it, could you also please fix the typo: "if @a is less
> than @b".

Fixed. New patch below.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

sort: Introduce generic list_sort function

There are two copies of list_sort() in the tree already, one in the DRM code,
another in ubifs. Now XFS needs this as well. Create a generic list_sort()
function from the ubifs version and convert existing users to it so we
don't end up with yet another copy in the tree.

Signed-off-by: Dave Chinner <david@fromorbit.com>
Acked-by: Dave Airlie <airlied@redhat.com>
Acked-by: Artem Bityutskiy <dedekind@infradead.org>
---
 drivers/gpu/drm/drm_modes.c |   90 ++--------------------------------------
 fs/ubifs/gc.c               |   95 ------------------------------------------
 include/linux/sort.h        |    5 ++
 lib/sort.c                  |   97 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 106 insertions(+), 181 deletions(-)

diff --git a/drivers/gpu/drm/drm_modes.c b/drivers/gpu/drm/drm_modes.c
index 51f6772..3846ed4 100644
--- a/drivers/gpu/drm/drm_modes.c
+++ b/drivers/gpu/drm/drm_modes.c
@@ -1,9 +1,4 @@
 /*
- * The list_sort function is (presumably) licensed under the GPL (see the
- * top level "COPYING" file for details).
- *
- * The remainder of this file is:
- *
  * Copyright © 1997-2003 by The XFree86 Project, Inc.
  * Copyright © 2007 Dave Airlie
  * Copyright © 2007-2008 Intel Corporation
@@ -36,6 +31,7 @@
  */
 
 #include <linux/list.h>
+#include <linux/sort.h>
 #include "drmP.h"
 #include "drm.h"
 #include "drm_crtc.h"
@@ -829,6 +825,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
 
 /**
  * drm_mode_compare - compare modes for favorability
+ * @priv: unused
  * @lh_a: list_head for first mode
  * @lh_b: list_head for second mode
  *
@@ -842,7 +839,7 @@ EXPORT_SYMBOL(drm_mode_prune_invalid);
  * Negative if @lh_a is better than @lh_b, zero if they're equivalent, or
  * positive if @lh_b is better than @lh_a.
  */
-static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
+static int drm_mode_compare(void *priv, struct list_head *lh_a, struct list_head *lh_b)
 {
 	struct drm_display_mode *a = list_entry(lh_a, struct drm_display_mode, head);
 	struct drm_display_mode *b = list_entry(lh_b, struct drm_display_mode, head);
@@ -859,85 +856,6 @@ static int drm_mode_compare(struct list_head *lh_a, struct list_head *lh_b)
 	return diff;
 }
 
-/* FIXME: what we don't have a list sort function? */
-/* list sort from Mark J Roberts (mjr@znex.org) */
-void list_sort(struct list_head *head,
-	       int (*cmp)(struct list_head *a, struct list_head *b))
-{
-	struct list_head *p, *q, *e, *list, *tail, *oldhead;
-	int insize, nmerges, psize, qsize, i;
-
-	list = head->next;
-	list_del(head);
-	insize = 1;
-	for (;;) {
-		p = oldhead = list;
-		list = tail = NULL;
-		nmerges = 0;
-
-		while (p) {
-			nmerges++;
-			q = p;
-			psize = 0;
-			for (i = 0; i < insize; i++) {
-				psize++;
-				q = q->next == oldhead ? NULL : q->next;
-				if (!q)
-					break;
-			}
-
-			qsize = insize;
-			while (psize > 0 || (qsize > 0 && q)) {
-				if (!psize) {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				} else if (!qsize || !q) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else if (cmp(p, q) <= 0) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				}
-				if (tail)
-					tail->next = e;
-				else
-					list = e;
-				e->prev = tail;
-				tail = e;
-			}
-			p = q;
-		}
-
-		tail->next = list;
-		list->prev = tail;
-
-		if (nmerges <= 1)
-			break;
-
-		insize *= 2;
-	}
-
-	head->next = list;
-	head->prev = list->prev;
-	list->prev->next = head;
-	list->prev = head;
-}
-
 /**
  * drm_mode_sort - sort mode list
  * @mode_list: list to sort
@@ -949,7 +867,7 @@ void list_sort(struct list_head *head,
  */
 void drm_mode_sort(struct list_head *mode_list)
 {
-	list_sort(mode_list, drm_mode_compare);
+	list_sort(NULL, mode_list, drm_mode_compare);
 }
 EXPORT_SYMBOL(drm_mode_sort);
 
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 618c270..4976e07 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -108,101 +108,6 @@ static int switch_gc_head(struct ubifs_info *c)
 }
 
 /**
- * list_sort - sort a list.
- * @priv: private data, passed to @cmp
- * @head: the list to sort
- * @cmp: the elements comparison function
- *
- * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
- * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
- * in ascending order.
- *
- * The comparison function @cmp is supposed to return a negative value if @a is
- * than @b, and a positive value if @a is greater than @b. If @a and @b are
- * equivalent, then it does not matter what this function returns.
- */
-static void list_sort(void *priv, struct list_head *head,
-		      int (*cmp)(void *priv, struct list_head *a,
-				 struct list_head *b))
-{
-	struct list_head *p, *q, *e, *list, *tail, *oldhead;
-	int insize, nmerges, psize, qsize, i;
-
-	if (list_empty(head))
-		return;
-
-	list = head->next;
-	list_del(head);
-	insize = 1;
-	for (;;) {
-		p = oldhead = list;
-		list = tail = NULL;
-		nmerges = 0;
-
-		while (p) {
-			nmerges++;
-			q = p;
-			psize = 0;
-			for (i = 0; i < insize; i++) {
-				psize++;
-				q = q->next == oldhead ? NULL : q->next;
-				if (!q)
-					break;
-			}
-
-			qsize = insize;
-			while (psize > 0 || (qsize > 0 && q)) {
-				if (!psize) {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				} else if (!qsize || !q) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else if (cmp(priv, p, q) <= 0) {
-					e = p;
-					p = p->next;
-					psize--;
-					if (p == oldhead)
-						p = NULL;
-				} else {
-					e = q;
-					q = q->next;
-					qsize--;
-					if (q == oldhead)
-						q = NULL;
-				}
-				if (tail)
-					tail->next = e;
-				else
-					list = e;
-				e->prev = tail;
-				tail = e;
-			}
-			p = q;
-		}
-
-		tail->next = list;
-		list->prev = tail;
-
-		if (nmerges <= 1)
-			break;
-
-		insize *= 2;
-	}
-
-	head->next = list;
-	head->prev = list->prev;
-	list->prev->next = head;
-	list->prev = head;
-}
-
-/**
  * data_nodes_cmp - compare 2 data nodes.
  * @priv: UBIFS file-system description object
  * @a: first data node
diff --git a/include/linux/sort.h b/include/linux/sort.h
index d534da2..99a2ed5 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -3,8 +3,13 @@
 
 #include <linux/types.h>
 
+struct list_head;
+
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
 	  void (*swap)(void *, void *, int));
 
+void list_sort(void *priv, struct list_head *head,
+	       int (*cmp)(void *priv, struct list_head *a,
+			  struct list_head *b));
 #endif
diff --git a/lib/sort.c b/lib/sort.c
index 926d004..5bab8ff 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -8,6 +8,7 @@
 #include <linux/module.h>
 #include <linux/sort.h>
 #include <linux/slab.h>
+#include <linux/list.h>
 
 static void u32_swap(void *a, void *b, int size)
 {
@@ -121,3 +122,99 @@ static int sort_test(void)
 
 module_init(sort_test);
 #endif
+
+/**
+ * list_sort - sort a list.
+ * @priv: private data, passed to @cmp
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
+ * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
+ * in ascending order.
+ *
+ * The comparison function @cmp is supposed to return a negative value if @a is
+ * less than @b, and a positive value if @a is greater than @b. If @a and @b
+ * are equivalent, then it does not matter what this function returns.
+ */
+void list_sort(void *priv, struct list_head *head,
+	       int (*cmp)(void *priv, struct list_head *a,
+			  struct list_head *b))
+{
+	struct list_head *p, *q, *e, *list, *tail, *oldhead;
+	int insize, nmerges, psize, qsize, i;
+
+	if (list_empty(head))
+		return;
+
+	list = head->next;
+	list_del(head);
+	insize = 1;
+	for (;;) {
+		p = oldhead = list;
+		list = tail = NULL;
+		nmerges = 0;
+
+		while (p) {
+			nmerges++;
+			q = p;
+			psize = 0;
+			for (i = 0; i < insize; i++) {
+				psize++;
+				q = q->next == oldhead ? NULL : q->next;
+				if (!q)
+					break;
+			}
+
+			qsize = insize;
+			while (psize > 0 || (qsize > 0 && q)) {
+				if (!psize) {
+					e = q;
+					q = q->next;
+					qsize--;
+					if (q == oldhead)
+						q = NULL;
+				} else if (!qsize || !q) {
+					e = p;
+					p = p->next;
+					psize--;
+					if (p == oldhead)
+						p = NULL;
+				} else if (cmp(priv, p, q) <= 0) {
+					e = p;
+					p = p->next;
+					psize--;
+					if (p == oldhead)
+						p = NULL;
+				} else {
+					e = q;
+					q = q->next;
+					qsize--;
+					if (q == oldhead)
+						q = NULL;
+				}
+				if (tail)
+					tail->next = e;
+				else
+					list = e;
+				e->prev = tail;
+				tail = e;
+			}
+			p = q;
+		}
+
+		tail->next = list;
+		list->prev = tail;
+
+		if (nmerges <= 1)
+			break;
+
+		insize *= 2;
+	}
+
+	head->next = list;
+	head->prev = list->prev;
+	list->prev->next = head;
+	list->prev = head;
+}
+