lib/list_sort.c

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