Blame view
lib/list_sort.c
7.03 KB
2c761270d lib: Introduce ge... |
1 2 3 4 5 |
#include <linux/kernel.h> #include <linux/module.h> #include <linux/list_sort.h> #include <linux/slab.h> #include <linux/list.h> |
835cc0c84 lib: more scalabl... |
6 7 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#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. */ |
f015ac3ed lib/list_sort: do... |
72 |
(*cmp)(priv, tail->next, tail->next); |
835cc0c84 lib: more scalabl... |
73 74 75 76 77 78 79 80 |
tail->next->prev = tail; tail = tail->next; } while (tail->next); tail->next = head; head->prev = tail; } |
2c761270d lib: Introduce ge... |
81 |
/** |
02b12b7a2 lib: revise list_... |
82 83 |
* list_sort - sort a list * @priv: private data, opaque to list_sort(), passed to @cmp |
2c761270d lib: Introduce ge... |
84 85 86 |
* @head: the list to sort * @cmp: the elements comparison function * |
02b12b7a2 lib: revise list_... |
87 88 |
* This function implements "merge sort", which has O(nlog(n)) * complexity. |
2c761270d lib: Introduce ge... |
89 |
* |
02b12b7a2 lib: revise list_... |
90 91 92 93 |
* 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 lib: Introduce ge... |
94 95 |
*/ void list_sort(void *priv, struct list_head *head, |
835cc0c84 lib: more scalabl... |
96 97 |
int (*cmp)(void *priv, struct list_head *a, struct list_head *b)) |
2c761270d lib: Introduce ge... |
98 |
{ |
835cc0c84 lib: more scalabl... |
99 100 101 102 103 |
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 lib: Introduce ge... |
104 105 106 |
if (list_empty(head)) return; |
835cc0c84 lib: more scalabl... |
107 108 109 |
memset(part, 0, sizeof(part)); head->prev->next = NULL; |
2c761270d lib: Introduce ge... |
110 |
list = head->next; |
2c761270d lib: Introduce ge... |
111 |
|
835cc0c84 lib: more scalabl... |
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
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)) { printk_once(KERN_DEBUG "list passed to" " list_sort() too long for" " efficiency "); lev--; |
2c761270d lib: Introduce ge... |
128 |
} |
835cc0c84 lib: more scalabl... |
129 |
max_lev = lev; |
2c761270d lib: Introduce ge... |
130 |
} |
835cc0c84 lib: more scalabl... |
131 132 |
part[lev] = cur; } |
2c761270d lib: Introduce ge... |
133 |
|
835cc0c84 lib: more scalabl... |
134 135 136 |
for (lev = 0; lev < max_lev; lev++) if (part[lev]) list = merge(priv, cmp, part[lev], list); |
2c761270d lib: Introduce ge... |
137 |
|
835cc0c84 lib: more scalabl... |
138 139 140 |
merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); } EXPORT_SYMBOL(list_sort); |
2c761270d lib: Introduce ge... |
141 |
|
6d411e6c0 lib/Kconfig.debug... |
142 |
#ifdef CONFIG_TEST_LIST_SORT |
eeee9ebb5 lib/list_sort: te... |
143 144 |
#include <linux/random.h> |
041b78f23 lib/list_sort: te... |
145 146 147 148 149 150 151 152 |
/* * 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 lib: more scalabl... |
153 |
struct debug_el { |
041b78f23 lib/list_sort: te... |
154 |
unsigned int poison1; |
eeee9ebb5 lib/list_sort: te... |
155 |
struct list_head list; |
041b78f23 lib/list_sort: te... |
156 |
unsigned int poison2; |
835cc0c84 lib: more scalabl... |
157 158 159 |
int value; unsigned serial; }; |
2c761270d lib: Introduce ge... |
160 |
|
041b78f23 lib/list_sort: te... |
161 162 163 164 |
/* 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 lib: more scalabl... |
165 |
{ |
041b78f23 lib/list_sort: te... |
166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 |
if (ela->serial >= TEST_LIST_LEN) { printk(KERN_ERR "list_sort_test: error: incorrect serial %d ", ela->serial); return -EINVAL; } if (elb->serial >= TEST_LIST_LEN) { printk(KERN_ERR "list_sort_test: error: incorrect serial %d ", elb->serial); return -EINVAL; } if (elts[ela->serial] != ela || elts[elb->serial] != elb) { printk(KERN_ERR "list_sort_test: error: phantom element "); return -EINVAL; } if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) { printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x ", ela->poison1, ela->poison2); return -EINVAL; } if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) { printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x ", elb->poison1, elb->poison2); return -EINVAL; } return 0; |
2c761270d lib: Introduce ge... |
196 |
} |
041b78f23 lib/list_sort: te... |
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 lib: more scalabl... |
207 208 209 |
static int __init list_sort_test(void) { |
f3dc0e384 lib/list_sort: te... |
210 211 212 213 |
int i, count = 1, err = -EINVAL; struct debug_el *el; struct list_head *cur, *tmp; LIST_HEAD(head); |
835cc0c84 lib: more scalabl... |
214 |
|
014afa943 lib/list_sort: te... |
215 216 |
printk(KERN_DEBUG "list_sort_test: start testing list_sort() "); |
835cc0c84 lib: more scalabl... |
217 |
|
041b78f23 lib/list_sort: te... |
218 219 220 221 222 223 224 |
elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL); if (!elts) { printk(KERN_ERR "list_sort_test: error: cannot allocate " "memory "); goto exit; } |
eeee9ebb5 lib/list_sort: te... |
225 |
for (i = 0; i < TEST_LIST_LEN; i++) { |
f3dc0e384 lib/list_sort: te... |
226 227 |
el = kmalloc(sizeof(*el), GFP_KERNEL); if (!el) { |
014afa943 lib/list_sort: te... |
228 |
printk(KERN_ERR "list_sort_test: error: cannot " |
f3dc0e384 lib/list_sort: te... |
229 230 231 232 |
"allocate memory "); goto exit; } |
835cc0c84 lib: more scalabl... |
233 |
/* force some equivalencies */ |
f39fee5f1 lib/: rename rand... |
234 |
el->value = prandom_u32() % (TEST_LIST_LEN / 3); |
835cc0c84 lib: more scalabl... |
235 |
el->serial = i; |
041b78f23 lib/list_sort: te... |
236 237 238 |
el->poison1 = TEST_POISON1; el->poison2 = TEST_POISON2; elts[i] = el; |
f3dc0e384 lib/list_sort: te... |
239 |
list_add_tail(&el->list, &head); |
835cc0c84 lib: more scalabl... |
240 |
} |
835cc0c84 lib: more scalabl... |
241 |
|
f3dc0e384 lib/list_sort: te... |
242 243 244 245 246 |
list_sort(NULL, &head, cmp); for (cur = head.next; cur->next != &head; cur = cur->next) { struct debug_el *el1; int cmp_result; |
835cc0c84 lib: more scalabl... |
247 |
|
835cc0c84 lib: more scalabl... |
248 |
if (cur->next->prev != cur) { |
014afa943 lib/list_sort: te... |
249 250 251 |
printk(KERN_ERR "list_sort_test: error: list is " "corrupted "); |
f3dc0e384 lib/list_sort: te... |
252 253 254 255 256 |
goto exit; } cmp_result = cmp(NULL, cur, cur->next); if (cmp_result > 0) { |
014afa943 lib/list_sort: te... |
257 258 259 |
printk(KERN_ERR "list_sort_test: error: list is not " "sorted "); |
f3dc0e384 lib/list_sort: te... |
260 261 262 263 264 265 |
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) { |
014afa943 lib/list_sort: te... |
266 267 268 |
printk(KERN_ERR "list_sort_test: error: order of " "equivalent elements not preserved "); |
f3dc0e384 lib/list_sort: te... |
269 |
goto exit; |
835cc0c84 lib: more scalabl... |
270 |
} |
041b78f23 lib/list_sort: te... |
271 272 273 274 275 276 277 |
if (check(el, el1)) { printk(KERN_ERR "list_sort_test: error: element check " "failed "); goto exit; } |
835cc0c84 lib: more scalabl... |
278 279 |
count++; } |
f3dc0e384 lib/list_sort: te... |
280 |
|
eeee9ebb5 lib/list_sort: te... |
281 |
if (count != TEST_LIST_LEN) { |
014afa943 lib/list_sort: te... |
282 283 |
printk(KERN_ERR "list_sort_test: error: bad list length %d", count); |
f3dc0e384 lib/list_sort: te... |
284 285 286 287 288 |
goto exit; } err = 0; exit: |
041b78f23 lib/list_sort: te... |
289 |
kfree(elts); |
f3dc0e384 lib/list_sort: te... |
290 291 292 |
list_for_each_safe(cur, tmp, &head) { list_del(cur); kfree(container_of(cur, struct debug_el, list)); |
835cc0c84 lib: more scalabl... |
293 |
} |
f3dc0e384 lib/list_sort: te... |
294 |
return err; |
835cc0c84 lib: more scalabl... |
295 296 |
} module_init(list_sort_test); |
6d411e6c0 lib/Kconfig.debug... |
297 |
#endif /* CONFIG_TEST_LIST_SORT */ |