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