Rev 1412 | Rev 6934 | 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 |
5 | #include |
||
6 | #include |
||
5270 | serge | 7 | #include |
1412 | serge | 8 | |
9 | |||
5270 | serge | 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 | |||
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 | |||
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 | |||
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 | |||
80 | tail = tail->next; |
||
81 | } while (tail->next); |
||
82 | |||
83 | |||
84 | head->prev = tail; |
||
85 | } |
||
86 | |||
87 | |||
1412 | serge | 88 | * list_sort - sort a list |
5270 | serge | 89 | * @priv: private data, opaque to list_sort(), passed to @cmp |
90 | * @head: the list to sort |
||
1412 | serge | 91 | * @cmp: the elements comparison function |
92 | * |
||
93 | * This function implements "merge sort", which has O(nlog(n)) |
||
5270 | serge | 94 | * complexity. |
95 | * |
||
1412 | serge | 96 | * The comparison function @cmp must return a negative value if @a |
5270 | serge | 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 | */ |
||
1412 | serge | 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 |
||
5270 | serge | 106 | -- last slot is a sentinel */ |
107 | int lev; /* index into part[] */ |
||
108 | int max_lev = 0; |
||
109 | struct list_head *list; |
||
110 | |||
1412 | serge | 111 | |
112 | return; |
||
113 | |||
114 | |||
5270 | serge | 115 | |
116 | |||
117 | list = head->next; |
||
1412 | serge | 118 | |
119 | |||
5270 | serge | 120 | struct list_head *cur = list; |
121 | list = list->next; |
||
122 | cur->next = NULL; |
||
123 | |||
1412 | serge | 124 | |
5270 | serge | 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 | } |
||
1412 | serge | 133 | max_lev = lev; |
5270 | serge | 134 | } |
1412 | serge | 135 | part[lev] = cur; |
5270 | serge | 136 | } |
1412 | serge | 137 | |
138 | |||
5270 | serge | 139 | if (part[lev]) |
140 | list = merge(priv, cmp, part[lev], list); |
||
141 | |||
1412 | serge | 142 | |
5270 | serge | 143 | } |
1412 | serge | 144 | EXPORT_SYMBOL(list_sort);>=>=> |
145 |