lib/list_sort.c

   1 #include <linux/kernel.h>
   2 #include <linux/module.h>
   3 #include <linux/list_sort.h>
   4 #include <linux/slab.h>
   5 #include <linux/list.h>
   6
   7 /**
   8  * list_sort - sort a list.
   9  * @priv: private data, passed to @cmp
  10  * @head: the list to sort
  11  * @cmp: the elements comparison function
  12  *
  13  * This function has been implemented by Mark J Roberts <mjr@znex.org>. It
  14  * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
  15  * in ascending order.
  16  *
  17  * The comparison function @cmp is supposed to return a negative value if @a is
  18  * less than @b, and a positive value if @a is greater than @b. If @a and @b
  19  * are equivalent, then it does not matter what this function returns.
  20  */
  21 void list_sort(void *priv, struct list_head *head,
  22                int (*cmp)(void *priv, struct list_head *a,
  23                           struct list_head *b))
  24 {
  25         struct list_head *p, *q, *e, *list, *tail, *oldhead;
  26         int insize, nmerges, psize, qsize, i;
  27
  28         if (list_empty(head))
  29                 return;
  30
  31         list = head->next;
  32         list_del(head);
  33         insize = 1;
  34         for (;;) {
  35                 p = oldhead = list;
  36                 list = tail = NULL;
  37                 nmerges = 0;
  38
  39                 while (p) {
  40                         nmerges++;
  41                         q = p;
  42                         psize = 0;
  43                         for (i = 0; i < insize; i++) {
  44                                 psize++;
  45                                 q = q->next == oldhead ? NULL : q->next;
  46                                 if (!q)
  47                                         break;
  48                         }
  49
  50                         qsize = insize;
  51                         while (psize > 0 || (qsize > 0 && q)) {
  52                                 if (!psize) {
  53                                         e = q;
  54                                         q = q->next;
  55                                         qsize--;
  56                                         if (q == oldhead)
  57                                                 q = NULL;
  58                                 } else if (!qsize || !q) {
  59                                         e = p;
  60                                         p = p->next;
  61                                         psize--;
  62                                         if (p == oldhead)
  63                                                 p = NULL;
  64                                 } else if (cmp(priv, p, q) <= 0) {
  65                                         e = p;
  66                                         p = p->next;
  67                                         psize--;
  68                                         if (p == oldhead)
  69                                                 p = NULL;
  70                                 } else {
  71                                         e = q;
  72                                         q = q->next;
  73                                         qsize--;
  74                                         if (q == oldhead)
  75                                                 q = NULL;
  76                                 }
  77                                 if (tail)
  78                                         tail->next = e;
  79                                 else
  80                                         list = e;
  81                                 e->prev = tail;
  82                                 tail = e;
  83                         }
  84                         p = q;
  85                 }
  86
  87                 tail->next = list;
  88                 list->prev = tail;
  89
  90                 if (nmerges <= 1)
  91                         break;
  92
  93                 insize *= 2;
  94         }
  95
  96         head->next = list;
  97         head->prev = list->prev;
  98         list->prev->next = head;
  99         list->prev = head;
 100 }
 101
 102 EXPORT_SYMBOL(list_sort);