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