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 <common.h>
10 #include <malloc.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 */
merge(void * priv,int (* cmp)(void * priv,struct list_head * a,struct list_head * b),struct list_head * a,struct list_head * b)22 static 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 */
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)51 static 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 */
list_sort(void * priv,struct list_head * head,int (* cmp)(void * priv,struct list_head * a,struct list_head * b))105 void 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 }
150 EXPORT_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
165 struct 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 */
174 static struct debug_el **elts __initdata;
175
check(struct debug_el * ela,struct debug_el * elb)176 static 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
cmp(void * priv,struct list_head * a,struct list_head * b)205 static 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
list_sort_test(void)216 static 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;
290 exit:
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 }
298 module_init(list_sort_test);
299 #endif /* CONFIG_TEST_LIST_SORT */
300