1#ifndef __UBOOT__ 2#include <log.h> 3#include <dm/devres.h> 4#include <linux/kernel.h> 5#include <linux/module.h> 6#include <linux/slab.h> 7#else 8#include <linux/compat.h> 9#include <malloc.h> 10#include <linux/printk.h> 11#endif 12#include <linux/list.h> 13#include <linux/list_sort.h> 14 15#define MAX_LIST_LENGTH_BITS 20 16 17/* 18 * Returns a list organized in an intermediate format suited 19 * to chaining of merge() calls: null-terminated, no reserved or 20 * sentinel head node, "prev" links not maintained. 21 */ 22static struct list_head *merge(void *priv, 23 int (*cmp)(void *priv, struct list_head *a, 24 struct list_head *b), 25 struct list_head *a, struct list_head *b) 26{ 27 struct list_head head, *tail = &head; 28 29 while (a && b) { 30 /* if equal, take 'a' -- important for sort stability */ 31 if ((*cmp)(priv, a, b) <= 0) { 32 tail->next = a; 33 a = a->next; 34 } else { 35 tail->next = b; 36 b = b->next; 37 } 38 tail = tail->next; 39 } 40 tail->next = a?:b; 41 return head.next; 42} 43 44/* 45 * Combine final list merge with restoration of standard doubly-linked 46 * list structure. This approach duplicates code from merge(), but 47 * runs faster than the tidier alternatives of either a separate final 48 * prev-link restoration pass, or maintaining the prev links 49 * throughout. 50 */ 51static void merge_and_restore_back_links(void *priv, 52 int (*cmp)(void *priv, struct list_head *a, 53 struct list_head *b), 54 struct list_head *head, 55 struct list_head *a, struct list_head *b) 56{ 57 struct list_head *tail = head; 58 59 while (a && b) { 60 /* if equal, take 'a' -- important for sort stability */ 61 if ((*cmp)(priv, a, b) <= 0) { 62 tail->next = a; 63 a->prev = tail; 64 a = a->next; 65 } else { 66 tail->next = b; 67 b->prev = tail; 68 b = b->next; 69 } 70 tail = tail->next; 71 } 72 tail->next = a ? : b; 73 74 do { 75 /* 76 * In worst cases this loop may run many iterations. 77 * Continue callbacks to the client even though no 78 * element comparison is needed, so the client's cmp() 79 * routine can invoke cond_resched() periodically. 80 */ 81 (*cmp)(priv, tail->next, tail->next); 82 83 tail->next->prev = tail; 84 tail = tail->next; 85 } while (tail->next); 86 87 tail->next = head; 88 head->prev = tail; 89} 90 91/** 92 * list_sort - sort a list 93 * @priv: private data, opaque to list_sort(), passed to @cmp 94 * @head: the list to sort 95 * @cmp: the elements comparison function 96 * 97 * This function implements "merge sort", which has O(nlog(n)) 98 * complexity. 99 * 100 * The comparison function @cmp must return a negative value if @a 101 * should sort before @b, and a positive value if @a should sort after 102 * @b. If @a and @b are equivalent, and their original relative 103 * ordering is to be preserved, @cmp must return 0. 104 */ 105void list_sort(void *priv, struct list_head *head, 106 int (*cmp)(void *priv, struct list_head *a, 107 struct list_head *b)) 108{ 109 struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 110 -- last slot is a sentinel */ 111 int lev; /* index into part[] */ 112 int max_lev = 0; 113 struct list_head *list; 114 115 if (list_empty(head)) 116 return; 117 118 memset(part, 0, sizeof(part)); 119 120 head->prev->next = NULL; 121 list = head->next; 122 123 while (list) { 124 struct list_head *cur = list; 125 list = list->next; 126 cur->next = NULL; 127 128 for (lev = 0; part[lev]; lev++) { 129 cur = merge(priv, cmp, part[lev], cur); 130 part[lev] = NULL; 131 } 132 if (lev > max_lev) { 133 if (unlikely(lev >= ARRAY_SIZE(part)-1)) { 134 printk_once(KERN_DEBUG "list passed to" 135 " list_sort() too long for" 136 " efficiency\n"); 137 lev--; 138 } 139 max_lev = lev; 140 } 141 part[lev] = cur; 142 } 143 144 for (lev = 0; lev < max_lev; lev++) 145 if (part[lev]) 146 list = merge(priv, cmp, part[lev], list); 147 148 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 149} 150EXPORT_SYMBOL(list_sort); 151 152#ifdef CONFIG_TEST_LIST_SORT 153 154#include <linux/random.h> 155 156/* 157 * The pattern of set bits in the list length determines which cases 158 * are hit in list_sort(). 159 */ 160#define TEST_LIST_LEN (512+128+2) /* not including head */ 161 162#define TEST_POISON1 0xDEADBEEF 163#define TEST_POISON2 0xA324354C 164 165struct debug_el { 166 unsigned int poison1; 167 struct list_head list; 168 unsigned int poison2; 169 int value; 170 unsigned serial; 171}; 172 173/* Array, containing pointers to all elements in the test list */ 174static struct debug_el **elts __initdata; 175 176static int __init check(struct debug_el *ela, struct debug_el *elb) 177{ 178 if (ela->serial >= TEST_LIST_LEN) { 179 printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n", 180 ela->serial); 181 return -EINVAL; 182 } 183 if (elb->serial >= TEST_LIST_LEN) { 184 printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n", 185 elb->serial); 186 return -EINVAL; 187 } 188 if (elts[ela->serial] != ela || elts[elb->serial] != elb) { 189 printk(KERN_ERR "list_sort_test: error: phantom element\n"); 190 return -EINVAL; 191 } 192 if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) { 193 printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n", 194 ela->poison1, ela->poison2); 195 return -EINVAL; 196 } 197 if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) { 198 printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n", 199 elb->poison1, elb->poison2); 200 return -EINVAL; 201 } 202 return 0; 203} 204 205static int __init cmp(void *priv, struct list_head *a, struct list_head *b) 206{ 207 struct debug_el *ela, *elb; 208 209 ela = container_of(a, struct debug_el, list); 210 elb = container_of(b, struct debug_el, list); 211 212 check(ela, elb); 213 return ela->value - elb->value; 214} 215 216static int __init list_sort_test(void) 217{ 218 int i, count = 1, err = -EINVAL; 219 struct debug_el *el; 220 struct list_head *cur, *tmp; 221 LIST_HEAD(head); 222 223 printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n"); 224 225 elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL); 226 if (!elts) { 227 printk(KERN_ERR "list_sort_test: error: cannot allocate " 228 "memory\n"); 229 goto exit; 230 } 231 232 for (i = 0; i < TEST_LIST_LEN; i++) { 233 el = kmalloc(sizeof(*el), GFP_KERNEL); 234 if (!el) { 235 printk(KERN_ERR "list_sort_test: error: cannot " 236 "allocate memory\n"); 237 goto exit; 238 } 239 /* force some equivalencies */ 240 el->value = prandom_u32() % (TEST_LIST_LEN / 3); 241 el->serial = i; 242 el->poison1 = TEST_POISON1; 243 el->poison2 = TEST_POISON2; 244 elts[i] = el; 245 list_add_tail(&el->list, &head); 246 } 247 248 list_sort(NULL, &head, cmp); 249 250 for (cur = head.next; cur->next != &head; cur = cur->next) { 251 struct debug_el *el1; 252 int cmp_result; 253 254 if (cur->next->prev != cur) { 255 printk(KERN_ERR "list_sort_test: error: list is " 256 "corrupted\n"); 257 goto exit; 258 } 259 260 cmp_result = cmp(NULL, cur, cur->next); 261 if (cmp_result > 0) { 262 printk(KERN_ERR "list_sort_test: error: list is not " 263 "sorted\n"); 264 goto exit; 265 } 266 267 el = container_of(cur, struct debug_el, list); 268 el1 = container_of(cur->next, struct debug_el, list); 269 if (cmp_result == 0 && el->serial >= el1->serial) { 270 printk(KERN_ERR "list_sort_test: error: order of " 271 "equivalent elements not preserved\n"); 272 goto exit; 273 } 274 275 if (check(el, el1)) { 276 printk(KERN_ERR "list_sort_test: error: element check " 277 "failed\n"); 278 goto exit; 279 } 280 count++; 281 } 282 283 if (count != TEST_LIST_LEN) { 284 printk(KERN_ERR "list_sort_test: error: bad list length %d", 285 count); 286 goto exit; 287 } 288 289 err = 0; 290exit: 291 kfree(elts); 292 list_for_each_safe(cur, tmp, &head) { 293 list_del(cur); 294 kfree(container_of(cur, struct debug_el, list)); 295 } 296 return err; 297} 298module_init(list_sort_test); 299#endif /* CONFIG_TEST_LIST_SORT */ 300