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