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