Subversion Repositories Kolibri OS

Rev

Rev 5270 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

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