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 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 * 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 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