1 /* $NetBSD: linux_list_sort.c,v 1.2 2014/03/18 18:20:43 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2013 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include <sys/cdefs.h>
33 __KERNEL_RCSID(0, "$NetBSD: linux_list_sort.c,v 1.2 2014/03/18 18:20:43 riastradh Exp $");
34
35 #include <sys/systm.h>
36
37 #include <machine/limits.h>
38
39 #include <linux/list.h>
40 #include <linux/list_sort.h>
41
42 static struct list_head *
43 list_sort_merge(struct list_head *, struct list_head *,
44 int (*)(void *, struct list_head *, struct list_head *),
45 void *);
46 static void list_sort_merge_into(struct list_head *,
47 struct list_head *, struct list_head *,
48 int (*)(void *, struct list_head *, struct list_head *),
49 void *);
50
51 void
list_sort(void * arg,struct list_head * list,int (* compare)(void *,struct list_head *,struct list_head *))52 list_sort(void *arg, struct list_head *list,
53 int (*compare)(void *, struct list_head *, struct list_head *))
54 {
55 /*
56 * Array of sorted sublists, counting in binary: accumulator[i]
57 * is sorted, and either is NULL or has length 2^i.
58 */
59 struct list_head *accumulator[64];
60
61 /* Indices into accumulator. */
62 unsigned int logn, max_logn = 0;
63
64 /* The sorted list we're currently working on. */
65 struct list_head *sorted;
66
67 /* The remainder of the unsorted list. */
68 struct list_head *next;
69
70 /* Make sure we can't possibly have more than 2^64-element lists. */
71 __CTASSERT((CHAR_BIT * sizeof(struct list_head *)) <= 64);
72
73 for (logn = 0; logn < __arraycount(accumulator); logn++)
74 accumulator[logn] = NULL;
75
76 list_for_each_safe(sorted, next, list) {
77 /* Pick off a single element, always sorted. */
78 sorted->next = NULL;
79
80 /* Add one and propagate the carry. */
81 for (logn = 0; accumulator[logn] != NULL; logn++) {
82 /*
83 * Merge, preferring previously accumulated
84 * elements to make the sort stable.
85 */
86 sorted = list_sort_merge(accumulator[logn], sorted,
87 compare, arg);
88 accumulator[logn] = NULL;
89 KASSERT((logn + 1) < __arraycount(accumulator));
90 }
91
92 /* Remember the highest index seen so far. */
93 if (logn > max_logn)
94 max_logn = logn;
95
96 /*
97 * logn = log_2(length(sorted)), and accumulator[logn]
98 * is now empty, so save the sorted sublist there.
99 */
100 accumulator[logn] = sorted;
101 }
102
103 /*
104 * Merge ~half of everything we have accumulated.
105 */
106 sorted = NULL;
107 for (logn = 0; logn < max_logn; logn++)
108 sorted = list_sort_merge(accumulator[logn], sorted, compare,
109 arg);
110
111 /*
112 * Merge the last ~halves back into the list, and fix the back
113 * pointers.
114 */
115 list_sort_merge_into(list, accumulator[max_logn], sorted, compare,
116 arg);
117 }
118
119 /*
120 * Merge the NULL-terminated lists starting at nodes `a' and `b',
121 * breaking ties by choosing nodes in `a' first, and returning
122 * whichever node has the least element.
123 */
124 static struct list_head *
list_sort_merge(struct list_head * a,struct list_head * b,int (* compare)(void *,struct list_head *,struct list_head *),void * arg)125 list_sort_merge(struct list_head *a, struct list_head *b,
126 int (*compare)(void *, struct list_head *, struct list_head *), void *arg)
127 {
128 struct list_head head, *tail = &head;
129
130 /*
131 * Merge while elements in both remain.
132 */
133 while ((a != NULL) && (b != NULL)) {
134 struct list_head **const first = ((*compare)(arg, a, b) <= 0?
135 &a : &b);
136
137 tail = tail->next = *first;
138 *first = (*first)->next;
139 }
140
141 /*
142 * Attach whatever remains.
143 */
144 tail->next = (a != NULL? a : b);
145 return head.next;
146 }
147
148 /*
149 * Merge the NULL-terminated lists starting at nodes `a' and `b' into
150 * the (uninitialized) list head `list', breaking ties by choosing
151 * nodes in `a' first, and setting the `prev' pointers as we go.
152 */
153 static void
list_sort_merge_into(struct list_head * list,struct list_head * a,struct list_head * b,int (* compare)(void *,struct list_head *,struct list_head *),void * arg)154 list_sort_merge_into(struct list_head *list,
155 struct list_head *a, struct list_head *b,
156 int (*compare)(void *, struct list_head *, struct list_head *), void *arg)
157 {
158 struct list_head *prev = list;
159
160 /*
161 * Merge while elements in both remain.
162 */
163 while ((a != NULL) && (b != NULL)) {
164 struct list_head **const first = ((*compare)(arg, a, b) <= 0?
165 &a : &b);
166
167 (*first)->prev = prev;
168 prev = prev->next = *first;
169 *first = (*first)->next;
170 }
171
172 /*
173 * Attach whichever of a and b remains, and fix up the prev
174 * pointers all the way down the rest of the list.
175 */
176 struct list_head *tail = (a == NULL? b : a);
177 while (tail != NULL) {
178 prev->next = tail;
179 tail->prev = prev;
180 prev = prev->next;
181 tail = tail->next;
182 }
183
184 /*
185 * Finally, finish the cycle.
186 */
187 prev->next = list;
188 list->prev = prev;
189 }
190