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