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