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/kernel.h>
40 #include <linux/list.h>
41 #include <linux/list_sort.h>
42
43 static struct list_head *
44 list_sort_merge(struct list_head *, struct list_head *,
45 int (*)(void *, struct list_head *,
46 struct list_head *), void *);
47 static void
48 list_sort_merge_into(struct list_head *,
49 struct list_head *, struct list_head *,
50 int (*)(void *, struct list_head *,
51 struct list_head *), void *);
52
53 void
list_sort(void * arg,struct list_head * list,int (* compare)(void *,struct list_head *,struct list_head *))54 list_sort(void *arg, struct list_head *list,
55 int (*compare)(void *, struct list_head *, struct list_head *))
56 {
57 /*
58 * Array of sorted sublists, counting in binary: accum[i]
59 * is sorted, and either is NULL or has length 2^i.
60 */
61 struct list_head *accum[64];
62
63 /* Indices into accum. */
64 unsigned int logn, max_logn = 0;
65
66 /* The sorted list we're currently working on. */
67 struct list_head *sorted;
68
69 /* The remainder of the unsorted list. */
70 struct list_head *next;
71
72 /* Make sure we can't possibly have more than 2^64-element lists. */
73 CTASSERT((CHAR_BIT * sizeof(struct list_head *)) <= 64);
74
75 for (logn = 0; logn < ARRAY_SIZE(accum); logn++)
76 accum[logn] = NULL;
77
78 list_for_each_safe(sorted, next, list) {
79 /* Pick off a single element, always sorted. */
80 sorted->next = NULL;
81
82 /* Add one and propagate the carry. */
83 for (logn = 0; accum[logn] != NULL; logn++) {
84 /*
85 * Merge, preferring previously accumulated
86 * elements to make the sort stable.
87 */
88 sorted = list_sort_merge(accum[logn], sorted, compare, arg);
89 accum[logn] = NULL;
90 KKASSERT((logn + 1) < ARRAY_SIZE(accum));
91 }
92
93 /* Remember the highest index seen so far. */
94 if (logn > max_logn)
95 max_logn = logn;
96
97 /*
98 * logn = log_2(length(sorted)), and accum[logn]
99 * is now empty, so save the sorted sublist there.
100 */
101 accum[logn] = sorted;
102 }
103
104 /*
105 * Merge ~half of everything we have accumulated.
106 */
107 sorted = NULL;
108 for (logn = 0; logn < max_logn; logn++)
109 sorted = list_sort_merge(accum[logn], sorted, compare, 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, accum[max_logn], sorted, compare, arg);
116 }
117
118 /*
119 * Merge the NULL-terminated lists starting at nodes `a' and `b',
120 * breaking ties by choosing nodes in `a' first, and returning
121 * whichever node has the least element.
122 */
123 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)124 list_sort_merge(struct list_head *a, struct list_head *b,
125 int (*compare)(void *, struct list_head *,
126 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 *,
157 struct list_head *), void *arg)
158 {
159 struct list_head *prev = list;
160
161 /*
162 * Merge while elements in both remain.
163 */
164 while ((a != NULL) && (b != NULL)) {
165 struct list_head **const first = (
166 (*compare)(arg, a, b) <= 0 ? &a : &b);
167
168 (*first)->prev = prev;
169 prev = prev->next = *first;
170 *first = (*first)->next;
171 }
172
173 /*
174 * Attach whichever of a and b remains, and fix up the prev
175 * pointers all the way down the rest of the list.
176 */
177 struct list_head *tail = (a == NULL? b : a);
178 while (tail != NULL) {
179 prev->next = tail;
180 tail->prev = prev;
181 prev = prev->next;
182 tail = tail->next;
183 }
184
185 /*
186 * Finally, finish the cycle.
187 */
188 prev->next = list;
189 list->prev = prev;
190 }
191