]>
Commit | Line | Data |
---|---|---|
1 | #include <linux/kernel.h> | |
2 | #include <linux/bug.h> | |
3 | #include <linux/compiler.h> | |
4 | #include <linux/export.h> | |
5 | #include <linux/string.h> | |
6 | #include <linux/list_sort.h> | |
7 | #include <linux/list.h> | |
8 | ||
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 | ||
87 | /** | |
88 | * list_sort - sort a list | |
89 | * @priv: private data, opaque to list_sort(), passed to @cmp | |
90 | * @head: the list to sort | |
91 | * @cmp: the elements comparison function | |
92 | * | |
93 | * This function implements "merge sort", which has O(nlog(n)) | |
94 | * complexity. | |
95 | * | |
96 | * The comparison function @cmp must return a negative value if @a | |
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 | |
99 | * ordering is to be preserved, @cmp must return 0. | |
100 | */ | |
101 | void list_sort(void *priv, struct list_head *head, | |
102 | int (*cmp)(void *priv, struct list_head *a, | |
103 | struct list_head *b)) | |
104 | { | |
105 | struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists | |
106 | -- last slot is a sentinel */ | |
107 | int lev; /* index into part[] */ | |
108 | int max_lev = 0; | |
109 | struct list_head *list; | |
110 | ||
111 | if (list_empty(head)) | |
112 | return; | |
113 | ||
114 | memset(part, 0, sizeof(part)); | |
115 | ||
116 | head->prev->next = NULL; | |
117 | list = head->next; | |
118 | ||
119 | while (list) { | |
120 | struct list_head *cur = list; | |
121 | list = list->next; | |
122 | cur->next = NULL; | |
123 | ||
124 | for (lev = 0; part[lev]; lev++) { | |
125 | cur = merge(priv, cmp, part[lev], cur); | |
126 | part[lev] = NULL; | |
127 | } | |
128 | if (lev > max_lev) { | |
129 | if (unlikely(lev >= ARRAY_SIZE(part)-1)) { | |
130 | printk_once(KERN_DEBUG "list too long for efficiency\n"); | |
131 | lev--; | |
132 | } | |
133 | max_lev = lev; | |
134 | } | |
135 | part[lev] = cur; | |
136 | } | |
137 | ||
138 | for (lev = 0; lev < max_lev; lev++) | |
139 | if (part[lev]) | |
140 | list = merge(priv, cmp, part[lev], list); | |
141 | ||
142 | merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); | |
143 | } | |
144 | EXPORT_SYMBOL(list_sort); |