1 /* $NetBSD: linux_list_sort.c,v 1.2 2014/03/18 18:20:43 riastradh Exp $ */
4 * Copyright (c) 2013 The NetBSD Foundation, Inc.
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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.
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 $");
35 #include <sys/systm.h>
37 #include <machine/limits.h>
39 #include <linux/kernel.h>
40 #include <linux/list.h>
41 #include <linux/list_sort.h>
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 *);
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 *);
54 list_sort(void *arg
, struct list_head
*list
,
55 int (*compare
)(void *, struct list_head
*, struct list_head
*))
58 * Array of sorted sublists, counting in binary: accum[i]
59 * is sorted, and either is NULL or has length 2^i.
61 struct list_head
*accum
[64];
63 /* Indices into accum. */
64 unsigned int logn
, max_logn
= 0;
66 /* The sorted list we're currently working on. */
67 struct list_head
*sorted
;
69 /* The remainder of the unsorted list. */
70 struct list_head
*next
;
72 /* Make sure we can't possibly have more than 2^64-element lists. */
73 CTASSERT((CHAR_BIT
* sizeof(struct list_head
*)) <= 64);
75 for (logn
= 0; logn
< ARRAY_SIZE(accum
); logn
++)
78 list_for_each_safe(sorted
, next
, list
) {
79 /* Pick off a single element, always sorted. */
82 /* Add one and propagate the carry. */
83 for (logn
= 0; accum
[logn
] != NULL
; logn
++) {
85 * Merge, preferring previously accumulated
86 * elements to make the sort stable.
88 sorted
= list_sort_merge(accum
[logn
], sorted
, compare
, arg
);
90 KKASSERT((logn
+ 1) < ARRAY_SIZE(accum
));
93 /* Remember the highest index seen so far. */
98 * logn = log_2(length(sorted)), and accum[logn]
99 * is now empty, so save the sorted sublist there.
101 accum
[logn
] = sorted
;
105 * Merge ~half of everything we have accumulated.
108 for (logn
= 0; logn
< max_logn
; logn
++)
109 sorted
= list_sort_merge(accum
[logn
], sorted
, compare
, arg
);
112 * Merge the last ~halves back into the list, and fix the back
115 list_sort_merge_into(list
, accum
[max_logn
], sorted
, compare
, arg
);
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.
123 static struct list_head
*
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
)
128 struct list_head head
, *tail
= &head
;
131 * Merge while elements in both remain.
133 while ((a
!= NULL
) && (b
!= NULL
)) {
134 struct list_head
**const first
= ((*compare
)(arg
, a
, b
) <= 0?
137 tail
= tail
->next
= *first
;
138 *first
= (*first
)->next
;
142 * Attach whatever remains.
144 tail
->next
= (a
!= NULL
? a
: b
);
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.
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
)
159 struct list_head
*prev
= list
;
162 * Merge while elements in both remain.
164 while ((a
!= NULL
) && (b
!= NULL
)) {
165 struct list_head
**const first
= (
166 (*compare
)(arg
, a
, b
) <= 0 ? &a
: &b
);
168 (*first
)->prev
= prev
;
169 prev
= prev
->next
= *first
;
170 *first
= (*first
)->next
;
174 * Attach whichever of a and b remains, and fix up the prev
175 * pointers all the way down the rest of the list.
177 struct list_head
*tail
= (a
== NULL
? b
: a
);
178 while (tail
!= NULL
) {
186 * Finally, finish the cycle.