Commit | Line | Data |
---|---|---|
d29cd59a JA |
1 | #include <string.h> |
2 | #include <assert.h> | |
3 | ||
4 | #include "../flist.h" | |
5 | #include "../flist_sort.h" | |
6 | ||
7 | #ifndef ARRAY_SIZE | |
8 | #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) | |
9 | #endif | |
10 | ||
11 | #define MAX_LIST_LENGTH_BITS 65 | |
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 flist_head *merge(void *priv, | |
19 | int (*cmp)(void *priv, struct flist_head *a, | |
20 | struct flist_head *b), | |
21 | struct flist_head *a, struct flist_head *b) | |
22 | { | |
23 | struct flist_head head, *tail = &head; | |
24 | ||
25 | while (a && b) { | |
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 flist_head *a, | |
49 | struct flist_head *b), | |
50 | struct flist_head *head, | |
51 | struct flist_head *a, struct flist_head *b) | |
52 | { | |
53 | struct flist_head *tail = head; | |
54 | ||
55 | while (a && b) { | |
56 | /* if equal, take 'a' -- important for sort stability */ | |
57 | if ((*cmp)(priv, a, b) <= 0) { | |
58 | tail->next = a; | |
59 | a->prev = tail; | |
60 | a = a->next; | |
61 | } else { | |
62 | tail->next = b; | |
63 | b->prev = tail; | |
64 | b = b->next; | |
65 | } | |
66 | tail = tail->next; | |
67 | } | |
68 | tail->next = a ? : b; | |
69 | ||
70 | do { | |
71 | /* | |
72 | * In worst cases this loop may run many iterations. | |
73 | * Continue callbacks to the client even though no | |
74 | * element comparison is needed, so the client's cmp() | |
75 | * routine can invoke cond_resched() periodically. | |
76 | */ | |
77 | cmp(priv, tail, tail); | |
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 | * flist_sort - sort a list | |
89 | * @priv: private data, opaque to flist_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 flist_sort(void *priv, struct flist_head *head, | |
102 | int (*cmp)(void *priv, struct flist_head *a, | |
103 | struct flist_head *b)) | |
104 | { | |
105 | struct flist_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 flist_head *list; | |
110 | ||
111 | if (flist_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 flist_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 | } | |
04539687 | 128 | if (lev > max_lev) { |
d29cd59a | 129 | assert(lev < ARRAY_SIZE(part) - 1); |
04539687 JA |
130 | max_lev = lev; |
131 | } | |
d29cd59a JA |
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 | } |