1 /*
2 * list_sort.c: merge sort implementation for linked lists
3 * Copied from the Linux kernel (lib/list_sort.c)
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms and conditions of the GNU General Public License,
7 * version 2, as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
12 * more details.
13 *
14 * You should have received a copy of the GNU General Public License along with
15 * this program; If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include <xen/lib.h>
19 #include <xen/list.h>
20 #include <xen/list_sort.h>
21
22 #define MAX_LIST_LENGTH_BITS 20
23
24 /*
25 * Returns a list organized in an intermediate format suited
26 * to chaining of merge() calls: null-terminated, no reserved or
27 * sentinel head node, "prev" links not maintained.
28 */
merge(void * priv,int (* cmp)(void * priv,struct list_head * a,struct list_head * b),struct list_head * a,struct list_head * b)29 static struct list_head *merge(void *priv,
30 int (*cmp)(void *priv, struct list_head *a,
31 struct list_head *b),
32 struct list_head *a, struct list_head *b)
33 {
34 struct list_head head, *tail = &head;
35
36 while (a && b) {
37 /* if equal, take 'a' -- important for sort stability */
38 if ((*cmp)(priv, a, b) <= 0) {
39 tail->next = a;
40 a = a->next;
41 } else {
42 tail->next = b;
43 b = b->next;
44 }
45 tail = tail->next;
46 }
47 tail->next = a?:b;
48 return head.next;
49 }
50
51 /*
52 * Combine final list merge with restoration of standard doubly-linked
53 * list structure. This approach duplicates code from merge(), but
54 * runs faster than the tidier alternatives of either a separate final
55 * prev-link restoration pass, or maintaining the prev links
56 * throughout.
57 */
merge_and_restore_back_links(void * priv,int (* cmp)(void * priv,struct list_head * a,struct list_head * b),struct list_head * head,struct list_head * a,struct list_head * b)58 static void merge_and_restore_back_links(void *priv,
59 int (*cmp)(void *priv, struct list_head *a,
60 struct list_head *b),
61 struct list_head *head,
62 struct list_head *a, struct list_head *b)
63 {
64 struct list_head *tail = head;
65 u8 count = 0;
66
67 while (a && b) {
68 /* if equal, take 'a' -- important for sort stability */
69 if ((*cmp)(priv, a, b) <= 0) {
70 tail->next = a;
71 a->prev = tail;
72 a = a->next;
73 } else {
74 tail->next = b;
75 b->prev = tail;
76 b = b->next;
77 }
78 tail = tail->next;
79 }
80 tail->next = a ? : b;
81
82 do {
83 /*
84 * In worst cases this loop may run many iterations.
85 * Continue callbacks to the client even though no
86 * element comparison is needed, so the client's cmp()
87 * routine can invoke cond_resched() periodically.
88 */
89 if (unlikely(!(++count)))
90 (*cmp)(priv, tail->next, tail->next);
91
92 tail->next->prev = tail;
93 tail = tail->next;
94 } while (tail->next);
95
96 tail->next = head;
97 head->prev = tail;
98 }
99
100 /**
101 * list_sort - sort a list
102 * @priv: private data, opaque to list_sort(), passed to @cmp
103 * @head: the list to sort
104 * @cmp: the elements comparison function
105 *
106 * This function implements "merge sort", which has O(nlog(n))
107 * complexity.
108 *
109 * The comparison function @cmp must return a negative value if @a
110 * should sort before @b, and a positive value if @a should sort after
111 * @b. If @a and @b are equivalent, and their original relative
112 * ordering is to be preserved, @cmp must return 0.
113 */
list_sort(void * priv,struct list_head * head,int (* cmp)(void * priv,struct list_head * a,struct list_head * b))114 void list_sort(void *priv, struct list_head *head,
115 int (*cmp)(void *priv, struct list_head *a,
116 struct list_head *b))
117 {
118 struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
119 -- last slot is a sentinel */
120 int lev; /* index into part[] */
121 int max_lev = 0;
122 struct list_head *list;
123
124 if (list_empty(head))
125 return;
126
127 memset(part, 0, sizeof(part));
128
129 head->prev->next = NULL;
130 list = head->next;
131
132 while (list) {
133 struct list_head *cur = list;
134 list = list->next;
135 cur->next = NULL;
136
137 for (lev = 0; part[lev]; lev++) {
138 cur = merge(priv, cmp, part[lev], cur);
139 part[lev] = NULL;
140 }
141 if (lev > max_lev) {
142 if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
143 dprintk(XENLOG_DEBUG,
144 "list too long for efficiency\n");
145 lev--;
146 }
147 max_lev = lev;
148 }
149 part[lev] = cur;
150 }
151
152 for (lev = 0; lev < max_lev; lev++)
153 if (part[lev])
154 list = merge(priv, cmp, part[lev], list);
155
156 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
157 }
158