1#ifndef __UBOOT__
2#include <log.h>
3#include <dm/devres.h>
4#include <linux/kernel.h>
5#include <linux/module.h>
6#include <linux/slab.h>
7#else
8#include <linux/compat.h>
9#include <malloc.h>
10#include <linux/printk.h>
11#endif
12#include <linux/list.h>
13#include <linux/list_sort.h>
14
15#define MAX_LIST_LENGTH_BITS 20
16
17/*
18 * Returns a list organized in an intermediate format suited
19 * to chaining of merge() calls: null-terminated, no reserved or
20 * sentinel head node, "prev" links not maintained.
21 */
22static struct list_head *merge(void *priv,
23				int (*cmp)(void *priv, struct list_head *a,
24					struct list_head *b),
25				struct list_head *a, struct list_head *b)
26{
27	struct list_head head, *tail = &head;
28
29	while (a && b) {
30		/* if equal, take 'a' -- important for sort stability */
31		if ((*cmp)(priv, a, b) <= 0) {
32			tail->next = a;
33			a = a->next;
34		} else {
35			tail->next = b;
36			b = b->next;
37		}
38		tail = tail->next;
39	}
40	tail->next = a?:b;
41	return head.next;
42}
43
44/*
45 * Combine final list merge with restoration of standard doubly-linked
46 * list structure.  This approach duplicates code from merge(), but
47 * runs faster than the tidier alternatives of either a separate final
48 * prev-link restoration pass, or maintaining the prev links
49 * throughout.
50 */
51static void merge_and_restore_back_links(void *priv,
52				int (*cmp)(void *priv, struct list_head *a,
53					struct list_head *b),
54				struct list_head *head,
55				struct list_head *a, struct list_head *b)
56{
57	struct list_head *tail = head;
58
59	while (a && b) {
60		/* if equal, take 'a' -- important for sort stability */
61		if ((*cmp)(priv, a, b) <= 0) {
62			tail->next = a;
63			a->prev = tail;
64			a = a->next;
65		} else {
66			tail->next = b;
67			b->prev = tail;
68			b = b->next;
69		}
70		tail = tail->next;
71	}
72	tail->next = a ? : b;
73
74	do {
75		/*
76		 * In worst cases this loop may run many iterations.
77		 * Continue callbacks to the client even though no
78		 * element comparison is needed, so the client's cmp()
79		 * routine can invoke cond_resched() periodically.
80		 */
81		(*cmp)(priv, tail->next, tail->next);
82
83		tail->next->prev = tail;
84		tail = tail->next;
85	} while (tail->next);
86
87	tail->next = head;
88	head->prev = tail;
89}
90
91/**
92 * list_sort - sort a list
93 * @priv: private data, opaque to list_sort(), passed to @cmp
94 * @head: the list to sort
95 * @cmp: the elements comparison function
96 *
97 * This function implements "merge sort", which has O(nlog(n))
98 * complexity.
99 *
100 * The comparison function @cmp must return a negative value if @a
101 * should sort before @b, and a positive value if @a should sort after
102 * @b. If @a and @b are equivalent, and their original relative
103 * ordering is to be preserved, @cmp must return 0.
104 */
105void list_sort(void *priv, struct list_head *head,
106		int (*cmp)(void *priv, struct list_head *a,
107			struct list_head *b))
108{
109	struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
110						-- last slot is a sentinel */
111	int lev;  /* index into part[] */
112	int max_lev = 0;
113	struct list_head *list;
114
115	if (list_empty(head))
116		return;
117
118	memset(part, 0, sizeof(part));
119
120	head->prev->next = NULL;
121	list = head->next;
122
123	while (list) {
124		struct list_head *cur = list;
125		list = list->next;
126		cur->next = NULL;
127
128		for (lev = 0; part[lev]; lev++) {
129			cur = merge(priv, cmp, part[lev], cur);
130			part[lev] = NULL;
131		}
132		if (lev > max_lev) {
133			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
134				printk_once(KERN_DEBUG "list passed to"
135					" list_sort() too long for"
136					" efficiency\n");
137				lev--;
138			}
139			max_lev = lev;
140		}
141		part[lev] = cur;
142	}
143
144	for (lev = 0; lev < max_lev; lev++)
145		if (part[lev])
146			list = merge(priv, cmp, part[lev], list);
147
148	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
149}
150EXPORT_SYMBOL(list_sort);
151
152#ifdef CONFIG_TEST_LIST_SORT
153
154#include <linux/random.h>
155
156/*
157 * The pattern of set bits in the list length determines which cases
158 * are hit in list_sort().
159 */
160#define TEST_LIST_LEN (512+128+2) /* not including head */
161
162#define TEST_POISON1 0xDEADBEEF
163#define TEST_POISON2 0xA324354C
164
165struct debug_el {
166	unsigned int poison1;
167	struct list_head list;
168	unsigned int poison2;
169	int value;
170	unsigned serial;
171};
172
173/* Array, containing pointers to all elements in the test list */
174static struct debug_el **elts __initdata;
175
176static int __init check(struct debug_el *ela, struct debug_el *elb)
177{
178	if (ela->serial >= TEST_LIST_LEN) {
179		printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
180				ela->serial);
181		return -EINVAL;
182	}
183	if (elb->serial >= TEST_LIST_LEN) {
184		printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
185				elb->serial);
186		return -EINVAL;
187	}
188	if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
189		printk(KERN_ERR "list_sort_test: error: phantom element\n");
190		return -EINVAL;
191	}
192	if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
193		printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
194				ela->poison1, ela->poison2);
195		return -EINVAL;
196	}
197	if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
198		printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
199				elb->poison1, elb->poison2);
200		return -EINVAL;
201	}
202	return 0;
203}
204
205static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
206{
207	struct debug_el *ela, *elb;
208
209	ela = container_of(a, struct debug_el, list);
210	elb = container_of(b, struct debug_el, list);
211
212	check(ela, elb);
213	return ela->value - elb->value;
214}
215
216static int __init list_sort_test(void)
217{
218	int i, count = 1, err = -EINVAL;
219	struct debug_el *el;
220	struct list_head *cur, *tmp;
221	LIST_HEAD(head);
222
223	printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
224
225	elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL);
226	if (!elts) {
227		printk(KERN_ERR "list_sort_test: error: cannot allocate "
228				"memory\n");
229		goto exit;
230	}
231
232	for (i = 0; i < TEST_LIST_LEN; i++) {
233		el = kmalloc(sizeof(*el), GFP_KERNEL);
234		if (!el) {
235			printk(KERN_ERR "list_sort_test: error: cannot "
236					"allocate memory\n");
237			goto exit;
238		}
239		 /* force some equivalencies */
240		el->value = prandom_u32() % (TEST_LIST_LEN / 3);
241		el->serial = i;
242		el->poison1 = TEST_POISON1;
243		el->poison2 = TEST_POISON2;
244		elts[i] = el;
245		list_add_tail(&el->list, &head);
246	}
247
248	list_sort(NULL, &head, cmp);
249
250	for (cur = head.next; cur->next != &head; cur = cur->next) {
251		struct debug_el *el1;
252		int cmp_result;
253
254		if (cur->next->prev != cur) {
255			printk(KERN_ERR "list_sort_test: error: list is "
256					"corrupted\n");
257			goto exit;
258		}
259
260		cmp_result = cmp(NULL, cur, cur->next);
261		if (cmp_result > 0) {
262			printk(KERN_ERR "list_sort_test: error: list is not "
263					"sorted\n");
264			goto exit;
265		}
266
267		el = container_of(cur, struct debug_el, list);
268		el1 = container_of(cur->next, struct debug_el, list);
269		if (cmp_result == 0 && el->serial >= el1->serial) {
270			printk(KERN_ERR "list_sort_test: error: order of "
271					"equivalent elements not preserved\n");
272			goto exit;
273		}
274
275		if (check(el, el1)) {
276			printk(KERN_ERR "list_sort_test: error: element check "
277					"failed\n");
278			goto exit;
279		}
280		count++;
281	}
282
283	if (count != TEST_LIST_LEN) {
284		printk(KERN_ERR "list_sort_test: error: bad list length %d",
285				count);
286		goto exit;
287	}
288
289	err = 0;
290exit:
291	kfree(elts);
292	list_for_each_safe(cur, tmp, &head) {
293		list_del(cur);
294		kfree(container_of(cur, struct debug_el, list));
295	}
296	return err;
297}
298module_init(list_sort_test);
299#endif /* CONFIG_TEST_LIST_SORT */
300