1 files changed, 183 insertions, 69 deletions
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 19d11e0bb958..362c10f1653f 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -4,99 +4,213 @@
 #include <linux/slab.h>
 #include <linux/list.h>
+#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(void *priv,
+                                int (*cmp)(void *priv, 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)(priv, 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(void *priv,
+                                int (*cmp)(void *priv, 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)(priv, 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)(priv, tail, tail);
+                tail->next->prev = tail;
+                tail = tail->next;
+        } while (tail->next);
+        tail->next = head;
+        head->prev = tail;
+}
 /**
 * 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
+ * This function implements "merge sort" which has O(nlog(n)) complexity.
- * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
+ * The list is sorted in ascending order.
- * 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,
+                int (*cmp)(void *priv, struct list_head *a,
-                          struct list_head *b))
+                        struct list_head *b))
 {
-        struct list_head *p, *q, *e, *list, *tail, *oldhead;
+        struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
-        int insize, nmerges, psize, qsize, i;
+                                                -- 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;
-        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 (list) {
-                        while (psize > 0 || (qsize > 0 && q)) {
+                struct list_head *cur = list;
-                                if (!psize) {
+                list = list->next;
-                                        e = q;
+                cur->next = NULL;
-                                        q = q->next;
-                                        qsize--;
+                for (lev = 0; part[lev]; lev++) {
-                                        if (q == oldhead)
+                        cur = merge(priv, cmp, part[lev], cur);
-                                                q = NULL;
+                        part[lev] = NULL;
-                                } else if (!qsize || !q) {
+                }
-                                        e = p;
+                if (lev > max_lev) {
-                                        p = p->next;
+                        if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
-                                        psize--;
+                                printk_once(KERN_DEBUG "list passed to"
-                                        if (p == oldhead)
+                                        " list_sort() too long for"
-                                                p = NULL;
+                                        " efficiency\n");
-                                } else if (cmp(priv, p, q) <= 0) {
+                                lev--;
-                                        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;
+                        max_lev = lev;
                }
+                part[lev] = cur;
+        }
-                tail->next = list;
+        for (lev = 0; lev < max_lev; lev++)
-                list->prev = tail;
+                if (part[lev])
+                        list = merge(priv, cmp, part[lev], list);
-                if (nmerges <= 1)
+        merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
-                        break;
+}
+EXPORT_SYMBOL(list_sort);
-                insize *= 2;
+#ifdef DEBUG_LIST_SORT
-        }
+struct debug_el {
+        struct list_head l_h;
+        int value;
+        unsigned serial;
+};
-        head->next = list;
+static int cmp(void *priv, struct list_head *a, struct list_head *b)
-        head->prev = list->prev;
+{
-        list->prev->next = head;
+        return container_of(a, struct debug_el, l_h)->value
-        list->prev = head;
+             - container_of(b, struct debug_el, l_h)->value;
 }
-EXPORT_SYMBOL(list_sort);
+/*
+ * The pattern of set bits in the list length determines which cases
+ * are hit in list_sort().
+ */
+#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
+static int __init list_sort_test(void)
+{
+        int i, r = 1, count;
+        struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
+        struct list_head *cur;
+        printk(KERN_WARNING "testing list_sort()\n");
+        cur = head;
+        for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
+                struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
+                BUG_ON(!el);
+                 /* force some equivalencies */
+                el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
+                el->serial = i;
+                el->l_h.prev = cur;
+                cur->next = &el->l_h;
+                cur = cur->next;
+        }
+        head->prev = cur;
+        list_sort(NULL, head, cmp);
+        count = 1;
+        for (cur = head->next; cur->next != head; cur = cur->next) {
+                struct debug_el *el = container_of(cur, struct debug_el, l_h);
+                int cmp_result = cmp(NULL, cur, cur->next);
+                if (cur->next->prev != cur) {
+                        printk(KERN_EMERG "list_sort() returned "
+                                                "a corrupted list!\n");
+                        return 1;
+                } else if (cmp_result > 0) {
+                        printk(KERN_EMERG "list_sort() failed to sort!\n");
+                        return 1;
+                } else if (cmp_result == 0 &&
+                                el->serial >= container_of(cur->next,
+                                        struct debug_el, l_h)->serial) {
+                        printk(KERN_EMERG "list_sort() failed to preserve order"
+                                                 " of equivalent elements!\n");
+                        return 1;
+                }
+                kfree(cur->prev);
+                count++;
+        }
+        kfree(cur);
+        if (count != LIST_SORT_TEST_LENGTH) {
+                printk(KERN_EMERG "list_sort() returned list of"
+                                                "different length!\n");
+                return 1;
+        }
+        return 0;
+}
+module_init(list_sort_test);
+#endif

diff --git a/lib/list_sort.c b/lib/list_sort.c index 19d11e0bb958..362c10f1653f 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c
@@ -4,99 +4,213 @@
4	#include <linux/slab.h>	4	#include <linux/slab.h>
5	#include <linux/list.h>	5	#include <linux/list.h>
6		6
		7	#define MAX_LIST_LENGTH_BITS 20
		8
		9	/*
		10	* Returns a list organized in an intermediate format suited
		11	* to chaining of merge() calls: null-terminated, no reserved or
		12	* sentinel head node, "prev" links not maintained.
		13	*/
		14	static struct list_head merge(void priv,
		15	int (cmp)(void priv, struct list_head *a,
		16	struct list_head *b),
		17	struct list_head a, struct list_head b)
		18	{
		19	struct list_head head, *tail = &head;
		20
		21	while (a && b) {
		22	/* if equal, take 'a' -- important for sort stability */
		23	if ((*cmp)(priv, a, b) <= 0) {
		24	tail->next = a;
		25	a = a->next;
		26	} else {
		27	tail->next = b;
		28	b = b->next;
		29	}
		30	tail = tail->next;
		31	}
		32	tail->next = a?:b;
		33	return head.next;
		34	}
		35
		36	/*
		37	* Combine final list merge with restoration of standard doubly-linked
		38	* list structure. This approach duplicates code from merge(), but
		39	* runs faster than the tidier alternatives of either a separate final
		40	* prev-link restoration pass, or maintaining the prev links
		41	* throughout.
		42	*/
		43	static void merge_and_restore_back_links(void *priv,
		44	int (cmp)(void priv, struct list_head *a,
		45	struct list_head *b),
		46	struct list_head *head,
		47	struct list_head a, struct list_head b)
		48	{
		49	struct list_head *tail = head;
		50
		51	while (a && b) {
		52	/* if equal, take 'a' -- important for sort stability */
		53	if ((*cmp)(priv, a, b) <= 0) {
		54	tail->next = a;
		55	a->prev = tail;
		56	a = a->next;
		57	} else {
		58	tail->next = b;
		59	b->prev = tail;
		60	b = b->next;
		61	}
		62	tail = tail->next;
		63	}
		64	tail->next = a ? : b;
		65
		66	do {
		67	/*
		68	* In worst cases this loop may run many iterations.
		69	* Continue callbacks to the client even though no
		70	* element comparison is needed, so the client's cmp()
		71	* routine can invoke cond_resched() periodically.
		72	*/
		73	(*cmp)(priv, tail, tail);
		74
		75	tail->next->prev = tail;
		76	tail = tail->next;
		77	} while (tail->next);
		78
		79	tail->next = head;
		80	head->prev = tail;
		81	}
		82
7	/**	83	/**
8	* list_sort - sort a list.	84	* list_sort - sort a list.
9	* @priv: private data, passed to @cmp	85	* @priv: private data, passed to @cmp
10	* @head: the list to sort	86	* @head: the list to sort
11	* @cmp: the elements comparison function	87	* @cmp: the elements comparison function
12	*	88	*
13	* This function has been implemented by Mark J Roberts <mjr@znex.org>. It	89	* This function implements "merge sort" which has O(nlog(n)) complexity.
14	* implements "merge sort" which has O(nlog(n)) complexity. The list is sorted	90	* The list is sorted in ascending order.
15	* in ascending order.
16	*	91	*
17	* The comparison function @cmp is supposed to return a negative value if @a is	92	* 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	93	* 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.	94	* are equivalent, then it does not matter what this function returns.
20	*/	95	*/
21	void list_sort(void priv, struct list_head head,	96	void list_sort(void priv, struct list_head head,
22	int (cmp)(void priv, struct list_head *a,	97	int (cmp)(void priv, struct list_head *a,
23	struct list_head *b))	98	struct list_head *b))
24	{	99	{
25	struct list_head p, q, e, list, tail, oldhead;	100	struct list_head part[MAX_LIST_LENGTH_BITS+1]; / sorted partial lists
26	int insize, nmerges, psize, qsize, i;	101	-- last slot is a sentinel */
		102	int lev; /* index into part[] */
		103	int max_lev = 0;
		104	struct list_head *list;
27		105
28	if (list_empty(head))	106	if (list_empty(head))
29	return;	107	return;
30		108
		109	memset(part, 0, sizeof(part));
		110
		111	head->prev->next = NULL;
31	list = head->next;	112	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		113
50	qsize = insize;	114	while (list) {
51	while (psize > 0 \|\| (qsize > 0 && q)) {	115	struct list_head *cur = list;
52	if (!psize) {	116	list = list->next;
53	e = q;	117	cur->next = NULL;
54	q = q->next;	118
55	qsize--;	119	for (lev = 0; part[lev]; lev++) {
56	if (q == oldhead)	120	cur = merge(priv, cmp, part[lev], cur);
57	q = NULL;	121	part[lev] = NULL;
58	} else if (!qsize \|\| !q) {	122	}
59	e = p;	123	if (lev > max_lev) {
60	p = p->next;	124	if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
61	psize--;	125	printk_once(KERN_DEBUG "list passed to"
62	if (p == oldhead)	126	" list_sort() too long for"
63	p = NULL;	127	" efficiency\n");
64	} else if (cmp(priv, p, q) <= 0) {	128	lev--;
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	}	129	}
84	p = q;	130	max_lev = lev;
85	}	131	}
		132	part[lev] = cur;
		133	}
86		134
87	tail->next = list;	135	for (lev = 0; lev < max_lev; lev++)
88	list->prev = tail;	136	if (part[lev])
		137	list = merge(priv, cmp, part[lev], list);
89		138
90	if (nmerges <= 1)	139	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
91	break;	140	}
		141	EXPORT_SYMBOL(list_sort);
92		142
93	insize *= 2;	143	#ifdef DEBUG_LIST_SORT
94	}	144	struct debug_el {
		145	struct list_head l_h;
		146	int value;
		147	unsigned serial;
		148	};
95		149
96	head->next = list;	150	static int cmp(void priv, struct list_head a, struct list_head *b)
97	head->prev = list->prev;	151	{
98	list->prev->next = head;	152	return container_of(a, struct debug_el, l_h)->value
99	list->prev = head;	153	- container_of(b, struct debug_el, l_h)->value;
100	}	154	}
101		155
102	EXPORT_SYMBOL(list_sort);	156	/*
		157	* The pattern of set bits in the list length determines which cases
		158	* are hit in list_sort().
		159	*/
		160	#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
		161
		162	static int __init list_sort_test(void)
		163	{
		164	int i, r = 1, count;
		165	struct list_head head = kmalloc(sizeof(head), GFP_KERNEL);
		166	struct list_head *cur;
		167
		168	printk(KERN_WARNING "testing list_sort()\n");
		169
		170	cur = head;
		171	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
		172	struct debug_el el = kmalloc(sizeof(el), GFP_KERNEL);
		173	BUG_ON(!el);
		174	/* force some equivalencies */
		175	el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
		176	el->serial = i;
		177
		178	el->l_h.prev = cur;
		179	cur->next = &el->l_h;
		180	cur = cur->next;
		181	}
		182	head->prev = cur;
		183
		184	list_sort(NULL, head, cmp);
		185
		186	count = 1;
		187	for (cur = head->next; cur->next != head; cur = cur->next) {
		188	struct debug_el *el = container_of(cur, struct debug_el, l_h);
		189	int cmp_result = cmp(NULL, cur, cur->next);
		190	if (cur->next->prev != cur) {
		191	printk(KERN_EMERG "list_sort() returned "
		192	"a corrupted list!\n");
		193	return 1;
		194	} else if (cmp_result > 0) {
		195	printk(KERN_EMERG "list_sort() failed to sort!\n");
		196	return 1;
		197	} else if (cmp_result == 0 &&
		198	el->serial >= container_of(cur->next,
		199	struct debug_el, l_h)->serial) {
		200	printk(KERN_EMERG "list_sort() failed to preserve order"
		201	" of equivalent elements!\n");
		202	return 1;
		203	}
		204	kfree(cur->prev);
		205	count++;
		206	}
		207	kfree(cur);
		208	if (count != LIST_SORT_TEST_LENGTH) {
		209	printk(KERN_EMERG "list_sort() returned list of"
		210	"different length!\n");
		211	return 1;
		212	}
		213	return 0;
		214	}
		215	module_init(list_sort_test);
		216	#endif