Line data Source code
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 <dev/pci/drm/drm_linux_list.h>
38 :
39 : static struct list_head *
40 : list_sort_merge(struct list_head *, struct list_head *,
41 : int (*)(void *, struct list_head *,
42 : 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 *, struct list_head *,
47 : struct list_head *), void *);
48 :
49 : void
50 0 : list_sort(void *arg, struct list_head *list,
51 : int (*compare)(void *, struct list_head *, 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 0 : 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 0 : for (logn = 0; logn < nitems(accum); logn++)
72 0 : accum[logn] = NULL;
73 :
74 0 : list_for_each_safe(sorted, next, list) {
75 : /* Pick off a single element, always sorted. */
76 0 : sorted->next = NULL;
77 :
78 : /* Add one and propagate the carry. */
79 0 : for (logn = 0; accum[logn] != NULL; logn++) {
80 : /*
81 : * Merge, preferring previously accumulated
82 : * elements to make the sort stable.
83 : */
84 0 : sorted = list_sort_merge(accum[logn], sorted, compare, arg);
85 0 : accum[logn] = NULL;
86 0 : KASSERT((logn + 1) < nitems(accum));
87 : }
88 :
89 : /* Remember the highest index seen so far. */
90 0 : if (logn > max_logn)
91 0 : 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 0 : accum[logn] = sorted;
98 : }
99 :
100 : /*
101 : * Merge ~half of everything we have accumulated.
102 : */
103 : sorted = NULL;
104 0 : for (logn = 0; logn < max_logn; logn++)
105 0 : 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 0 : list_sort_merge_into(list, accum[max_logn], sorted, compare, arg);
112 0 : }
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 *
120 0 : list_sort_merge(struct list_head *a, struct list_head *b,
121 : int (*compare)(void *, struct list_head *,
122 : struct list_head *), void *arg)
123 : {
124 0 : struct list_head head, *tail = &head;
125 :
126 : /*
127 : * Merge while elements in both remain.
128 : */
129 0 : while ((a != NULL) && (b != NULL)) {
130 0 : struct list_head **const first = ((*compare)(arg, a, b) <= 0?
131 : &a : &b);
132 :
133 0 : tail = tail->next = *first;
134 0 : *first = (*first)->next;
135 : }
136 :
137 : /*
138 : * Attach whatever remains.
139 : */
140 0 : tail->next = (a != NULL? a : b);
141 0 : return head.next;
142 0 : }
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
150 0 : list_sort_merge_into(struct list_head *list,
151 : struct list_head *a, struct list_head *b,
152 : int (*compare)(void *, struct list_head *,
153 : struct list_head *), void *arg)
154 : {
155 : struct list_head *prev = list;
156 :
157 : /*
158 : * Merge while elements in both remain.
159 : */
160 0 : while ((a != NULL) && (b != NULL)) {
161 : struct list_head **const first = (
162 0 : (*compare)(arg, a, b) <= 0 ? &a : &b);
163 :
164 0 : (*first)->prev = prev;
165 0 : prev = prev->next = *first;
166 0 : *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 0 : struct list_head *tail = (a == NULL? b : a);
174 0 : while (tail != NULL) {
175 0 : prev->next = tail;
176 0 : tail->prev = prev;
177 0 : prev = prev->next;
178 0 : tail = tail->next;
179 : }
180 :
181 : /*
182 : * Finally, finish the cycle.
183 : */
184 0 : prev->next = list;
185 0 : list->prev = prev;
186 0 : }
|
