1 #include <linux/kernel.h>
2 #include <linux/module.h>
3 #include <linux/list_sort.h>
4 #include <linux/slab.h>
5 #include <linux/list.h>
8 * list_sort - sort a list.
9 * @priv: private data, passed to @cmp
10 * @head: the list to sort
11 * @cmp: the elements comparison function
13 * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
14 * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
17 * The comparison function @cmp is supposed to return a negative value if @a is
18 * less than @b, and a positive value if @a is greater than @b. If @a and @b
19 * are equivalent, then it does not matter what this function returns.
21 void list_sort(void *priv
, struct list_head
*head
,
22 int (*cmp
)(void *priv
, struct list_head
*a
,
25 struct list_head
*p
, *q
, *e
, *list
, *tail
, *oldhead
;
26 int insize
, nmerges
, psize
, qsize
, i
;
43 for (i
= 0; i
< insize
; i
++) {
45 q
= q
->next
== oldhead
? NULL
: q
->next
;
51 while (psize
> 0 || (qsize
> 0 && q
)) {
58 } else if (!qsize
|| !q
) {
64 } else if (cmp(priv
, p
, q
) <= 0) {
97 head
->prev
= list
->prev
;
98 list
->prev
->next
= head
;
102 EXPORT_SYMBOL(list_sort
);
This page took 0.032869 seconds and 5 git commands to generate.