5 #include "../flist_sort.h"
8 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
11 #define MAX_LIST_LENGTH_BITS 65
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.
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)
23 struct flist_head head, *tail = &head;
26 /* if equal, take 'a' -- important for sort stability */
27 if ((*cmp)(priv, a, b) <= 0) {
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
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)
53 struct flist_head *tail = head;
56 /* if equal, take 'a' -- important for sort stability */
57 if ((*cmp)(priv, a, b) <= 0) {
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.
77 cmp(priv, tail, tail);
79 tail->next->prev = tail;
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
93 * This function implements "merge sort", which has O(nlog(n))
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.
101 void flist_sort(void *priv, struct flist_head *head,
102 int (*cmp)(void *priv, struct flist_head *a,
103 struct flist_head *b))
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[] */
109 struct flist_head *list;
111 if (flist_empty(head))
114 memset(part, 0, sizeof(part));
116 head->prev->next = NULL;
120 struct flist_head *cur = list;
124 for (lev = 0; part[lev]; lev++) {
125 cur = merge(priv, cmp, part[lev], cur);
129 assert(lev < ARRAY_SIZE(part) - 1);
135 for (lev = 0; lev < max_lev; lev++)
137 list = merge(priv, cmp, part[lev], list);
139 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);