1 files changed, 102 insertions, 0 deletions
diff --git a/lib/list_sort.c b/lib/list_sort.c
new file mode 100644
index 000000000000..19d11e0bb958
--- /dev/null
+++ b/lib/list_sort.c
@@ -0,0 +1,102 @@
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/list_sort.h>
+#include <linux/slab.h>
+#include <linux/list.h>
+/**
+ * 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);

diff --git a/lib/list_sort.c b/lib/list_sort.c new file mode 100644 index 000000000000..19d11e0bb958 --- /dev/null +++ b/lib/list_sort.c
@@ -0,0 +1,102 @@
	1	#include <linux/kernel.h>
	2	#include <linux/module.h>
	3	#include <linux/list_sort.h>
	4	#include <linux/slab.h>
	5	#include <linux/list.h>
	6
	7	/**
	8	* list_sort - sort a list.
	9	* @priv: private data, passed to @cmp
	10	* @head: the list to sort
	11	* @cmp: the elements comparison function
	12	*
	13	* This function has been implemented by Mark J Roberts <mjr@znex.org>. It
	14	* implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
	15	* in ascending order.
	16	*
	17	* The comparison function @cmp is supposed to return a negative value if @a is
	18	* less than @b, and a positive value if @a is greater than @b. If @a and @b
	19	* are equivalent, then it does not matter what this function returns.
	20	*/
	21	void list_sort(void priv, struct list_head head,
	22	int (cmp)(void priv, struct list_head *a,
	23	struct list_head *b))
	24	{
	25	struct list_head p, q, e, list, tail, oldhead;
	26	int insize, nmerges, psize, qsize, i;
	27
	28	if (list_empty(head))
	29	return;
	30
	31	list = head->next;
	32	list_del(head);
	33	insize = 1;
	34	for (;;) {
	35	p = oldhead = list;
	36	list = tail = NULL;
	37	nmerges = 0;
	38
	39	while (p) {
	40	nmerges++;
	41	q = p;
	42	psize = 0;
	43	for (i = 0; i < insize; i++) {
	44	psize++;
	45	q = q->next == oldhead ? NULL : q->next;
	46	if (!q)
	47	break;
	48	}
	49
	50	qsize = insize;
	51	while (psize > 0 \|\| (qsize > 0 && q)) {
	52	if (!psize) {
	53	e = q;
	54	q = q->next;
	55	qsize--;
	56	if (q == oldhead)
	57	q = NULL;
	58	} else if (!qsize \|\| !q) {
	59	e = p;
	60	p = p->next;
	61	psize--;
	62	if (p == oldhead)
	63	p = NULL;
	64	} else if (cmp(priv, p, q) <= 0) {
	65	e = p;
	66	p = p->next;
	67	psize--;
	68	if (p == oldhead)
	69	p = NULL;
	70	} else {
	71	e = q;
	72	q = q->next;
	73	qsize--;
	74	if (q == oldhead)
	75	q = NULL;
	76	}
	77	if (tail)
	78	tail->next = e;
	79	else
	80	list = e;
	81	e->prev = tail;
	82	tail = e;
	83	}
	84	p = q;
	85	}
	86
	87	tail->next = list;
	88	list->prev = tail;
	89
	90	if (nmerges <= 1)
	91	break;
	92
	93	insize *= 2;
	94	}
	95
	96	head->next = list;
	97	head->prev = list->prev;
	98	list->prev->next = head;
	99	list->prev = head;
	100	}
	101
	102	EXPORT_SYMBOL(list_sort);