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