Rev 1412 | Rev 6934 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1412 | Rev 5270 | ||
---|---|---|---|
Line -... | Line 1... | ||
- | 1 | #define pr_fmt(fmt) "list_sort_test: " fmt |
|
- | 2 | ||
- | 3 | #include |
|
1 | #include |
4 | #include |
2 | #include |
5 | #include |
3 | #include |
6 | #include |
- | 7 | #include |
|
4 | #include |
8 | |
Line -... | Line 9... | ||
- | 9 | #define MAX_LIST_LENGTH_BITS 20 |
|
- | 10 | ||
- | 11 | /* |
|
- | 12 | * Returns a list organized in an intermediate format suited |
|
- | 13 | * to chaining of merge() calls: null-terminated, no reserved or |
|
- | 14 | * sentinel head node, "prev" links not maintained. |
|
- | 15 | */ |
|
- | 16 | static struct list_head *merge(void *priv, |
|
- | 17 | int (*cmp)(void *priv, struct list_head *a, |
|
- | 18 | struct list_head *b), |
|
- | 19 | struct list_head *a, struct list_head *b) |
|
- | 20 | { |
|
- | 21 | struct list_head head, *tail = &head; |
|
- | 22 | ||
- | 23 | while (a && b) { |
|
- | 24 | /* if equal, take 'a' -- important for sort stability */ |
|
- | 25 | if ((*cmp)(priv, a, b) <= 0) { |
|
- | 26 | tail->next = a; |
|
- | 27 | a = a->next; |
|
- | 28 | } else { |
|
- | 29 | tail->next = b; |
|
- | 30 | b = b->next; |
|
- | 31 | } |
|
- | 32 | tail = tail->next; |
|
- | 33 | } |
|
- | 34 | tail->next = a?:b; |
|
- | 35 | return head.next; |
|
- | 36 | } |
|
- | 37 | ||
- | 38 | /* |
|
- | 39 | * Combine final list merge with restoration of standard doubly-linked |
|
- | 40 | * list structure. This approach duplicates code from merge(), but |
|
- | 41 | * runs faster than the tidier alternatives of either a separate final |
|
- | 42 | * prev-link restoration pass, or maintaining the prev links |
|
- | 43 | * throughout. |
|
- | 44 | */ |
|
- | 45 | static void merge_and_restore_back_links(void *priv, |
|
- | 46 | int (*cmp)(void *priv, struct list_head *a, |
|
- | 47 | struct list_head *b), |
|
- | 48 | struct list_head *head, |
|
- | 49 | struct list_head *a, struct list_head *b) |
|
- | 50 | { |
|
- | 51 | struct list_head *tail = head; |
|
- | 52 | u8 count = 0; |
|
- | 53 | ||
- | 54 | while (a && b) { |
|
- | 55 | /* if equal, take 'a' -- important for sort stability */ |
|
- | 56 | if ((*cmp)(priv, a, b) <= 0) { |
|
- | 57 | tail->next = a; |
|
- | 58 | a->prev = tail; |
|
- | 59 | a = a->next; |
|
- | 60 | } else { |
|
- | 61 | tail->next = b; |
|
- | 62 | b->prev = tail; |
|
- | 63 | b = b->next; |
|
- | 64 | } |
|
- | 65 | tail = tail->next; |
|
- | 66 | } |
|
- | 67 | tail->next = a ? : b; |
|
- | 68 | ||
- | 69 | do { |
|
- | 70 | /* |
|
- | 71 | * In worst cases this loop may run many iterations. |
|
- | 72 | * Continue callbacks to the client even though no |
|
- | 73 | * element comparison is needed, so the client's cmp() |
|
- | 74 | * routine can invoke cond_resched() periodically. |
|
- | 75 | */ |
|
- | 76 | if (unlikely(!(++count))) |
|
- | 77 | (*cmp)(priv, tail->next, tail->next); |
|
- | 78 | ||
- | 79 | tail->next->prev = tail; |
|
- | 80 | tail = tail->next; |
|
- | 81 | } while (tail->next); |
|
- | 82 | ||
- | 83 | tail->next = head; |
|
- | 84 | head->prev = tail; |
|
- | 85 | } |
|
- | 86 | ||
5 | 87 | /** |
|
6 | /** |
88 | * list_sort - sort a list |
7 | * list_sort - sort a list. |
89 | * @priv: private data, opaque to list_sort(), passed to @cmp |
8 | * @priv: private data, passed to @cmp |
90 | * @head: the list to sort |
9 | * @head: the list to sort |
91 | * @cmp: the elements comparison function |
10 | * @cmp: the elements comparison function |
92 | * |
11 | * |
93 | * This function implements "merge sort", which has O(nlog(n)) |
12 | * This function has been implemented by Mark J Roberts |
- | |
13 | * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted |
94 | * complexity. |
14 | * in ascending order. |
95 | * |
15 | * |
96 | * The comparison function @cmp must return a negative value if @a |
16 | * The comparison function @cmp is supposed to return a negative value if @a is |
97 | * should sort before @b, and a positive value if @a should sort after |
- | 98 | * @b. If @a and @b are equivalent, and their original relative |
|
17 | * less than @b, and a positive value if @a is greater than @b. If @a and @b |
99 | * ordering is to be preserved, @cmp must return 0. |
18 | * are equivalent, then it does not matter what this function returns. |
100 | */ |
19 | */ |
101 | void list_sort(void *priv, struct list_head *head, |
20 | void list_sort(void *priv, struct list_head *head, |
102 | int (*cmp)(void *priv, struct list_head *a, |
21 | int (*cmp)(void *priv, struct list_head *a, |
103 | struct list_head *b)) |
22 | struct list_head *b)) |
104 | { |
23 | { |
105 | struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists |
- | 106 | -- last slot is a sentinel */ |
|
24 | struct list_head *p, *q, *e, *list, *tail, *oldhead; |
107 | int lev; /* index into part[] */ |
- | 108 | int max_lev = 0; |
|
- | 109 | struct list_head *list; |
|
Line 25... | Line 110... | ||
25 | int insize, nmerges, psize, qsize, i; |
110 | |
26 | 111 | if (list_empty(head)) |
|
Line -... | Line 112... | ||
- | 112 | return; |
|
- | 113 | ||
- | 114 | memset(part, 0, sizeof(part)); |
|
27 | if (list_empty(head)) |
115 | |
28 | return; |
- | |
29 | - | ||
30 | list = head->next; |
- | |
31 | list_del(head); |
- | |
32 | insize = 1; |
- | |
33 | for (;;) { |
- | |
34 | p = oldhead = list; |
116 | head->prev->next = NULL; |
35 | list = tail = NULL; |
117 | list = head->next; |
36 | nmerges = 0; |
- | |
37 | - | ||
38 | while (p) { |
- | |
39 | nmerges++; |
118 | |
40 | q = p; |
119 | while (list) { |
41 | psize = 0; |
120 | struct list_head *cur = list; |
42 | for (i = 0; i < insize; i++) { |
- | |
43 | psize++; |
- | |
44 | q = q->next == oldhead ? NULL : q->next; |
- | |
45 | if (!q) |
121 | list = list->next; |
46 | break; |
- | |
47 | } |
- | |
48 | - | ||
49 | qsize = insize; |
- | |
50 | while (psize > 0 || (qsize > 0 && q)) { |
- | |
51 | if (!psize) { |
- | |
52 | e = q; |
- | |
53 | q = q->next; |
- | |
54 | qsize--; |
122 | cur->next = NULL; |
55 | if (q == oldhead) |
- | |
56 | q = NULL; |
- | |
57 | } else if (!qsize || !q) { |
- | |
58 | e = p; |
- | |
59 | p = p->next; |
- | |
60 | psize--; |
123 | |
61 | if (p == oldhead) |
- | |
62 | p = NULL; |
- | |
63 | } else if (cmp(priv, p, q) <= 0) { |
- | |
64 | e = p; |
- | |
65 | p = p->next; |
- | |
66 | psize--; |
- | |
67 | if (p == oldhead) |
- | |
68 | p = NULL; |
- | |
69 | } else { |
- | |
70 | e = q; |
- | |
71 | q = q->next; |
124 | for (lev = 0; part[lev]; lev++) { |
72 | qsize--; |
125 | cur = merge(priv, cmp, part[lev], cur); |
73 | if (q == oldhead) |
126 | part[lev] = NULL; |
74 | q = NULL; |
127 | } |
75 | } |
- | |
76 | if (tail) |
- | |
77 | tail->next = e; |
128 | if (lev > max_lev) { |
78 | else |
129 | if (unlikely(lev >= ARRAY_SIZE(part)-1)) { |
79 | list = e; |
130 | printk_once(KERN_DEBUG "list too long for efficiency\n"); |
80 | e->prev = tail; |
131 | lev--; |
81 | tail = e; |
132 | } |
82 | } |
- | |
83 | p = q; |
- | |
84 | } |
133 | max_lev = lev; |
85 | - | ||
86 | tail->next = list; |
- | |
87 | list->prev = tail; |
- | |
88 | - | ||
89 | if (nmerges <= 1) |
- | |
90 | break; |
134 | } |
Line 91... | Line -... | ||
91 | - | ||
92 | insize *= 2; |
135 | part[lev] = cur; |
93 | } |
136 | } |
94 | 137 | ||
95 | head->next = list; |
- | |
Line -... | Line 138... | ||
- | 138 | for (lev = 0; lev < max_lev; lev++) |
|
- | 139 | if (part[lev]) |
|
96 | head->prev = list->prev; |
140 | list = merge(priv, cmp, part[lev], list); |