Subversion Repositories Kolibri OS

Rev

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

  1.  
  2. #define pr_fmt(fmt) "list_sort_test: " fmt
  3.  
  4. #include <linux/kernel.h>
  5. #include <linux/bug.h>
  6. #include <linux/compiler.h>
  7. #include <linux/export.h>
  8. #include <linux/string.h>
  9. #include <linux/list_sort.h>
  10. #include <linux/list.h>
  11.  
  12. #define MAX_LIST_LENGTH_BITS 20
  13.  
  14. /*
  15.  * Returns a list organized in an intermediate format suited
  16.  * to chaining of merge() calls: null-terminated, no reserved or
  17.  * sentinel head node, "prev" links not maintained.
  18.  */
  19. static struct list_head *merge(void *priv,
  20.                                 int (*cmp)(void *priv, struct list_head *a,
  21.                                         struct list_head *b),
  22.                                 struct list_head *a, struct list_head *b)
  23. {
  24.         struct list_head head, *tail = &head;
  25.  
  26.         while (a && b) {
  27.                 /* if equal, take 'a' -- important for sort stability */
  28.                 if ((*cmp)(priv, a, b) <= 0) {
  29.                         tail->next = a;
  30.                         a = a->next;
  31.                 } else {
  32.                         tail->next = b;
  33.                         b = b->next;
  34.                 }
  35.                 tail = tail->next;
  36.         }
  37.         tail->next = a?:b;
  38.         return head.next;
  39. }
  40.  
  41. /*
  42.  * Combine final list merge with restoration of standard doubly-linked
  43.  * list structure.  This approach duplicates code from merge(), but
  44.  * runs faster than the tidier alternatives of either a separate final
  45.  * prev-link restoration pass, or maintaining the prev links
  46.  * throughout.
  47.  */
  48. static void merge_and_restore_back_links(void *priv,
  49.                                 int (*cmp)(void *priv, struct list_head *a,
  50.                                         struct list_head *b),
  51.                                 struct list_head *head,
  52.                                 struct list_head *a, struct list_head *b)
  53. {
  54.         struct list_head *tail = head;
  55.         u8 count = 0;
  56.  
  57.         while (a && b) {
  58.                 /* if equal, take 'a' -- important for sort stability */
  59.                 if ((*cmp)(priv, a, b) <= 0) {
  60.                         tail->next = a;
  61.                         a->prev = tail;
  62.                         a = a->next;
  63.                 } else {
  64.                         tail->next = b;
  65.                         b->prev = tail;
  66.                         b = b->next;
  67.                 }
  68.                 tail = tail->next;
  69.         }
  70.         tail->next = a ? : b;
  71.  
  72.         do {
  73.                 /*
  74.                  * In worst cases this loop may run many iterations.
  75.                  * Continue callbacks to the client even though no
  76.                  * element comparison is needed, so the client's cmp()
  77.                  * routine can invoke cond_resched() periodically.
  78.                  */
  79.                 if (unlikely(!(++count)))
  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 too long for efficiency\n");
  134.                                 lev--;
  135.                                 }
  136.                         max_lev = lev;
  137.                         }
  138.                 part[lev] = cur;
  139.                 }
  140.  
  141.         for (lev = 0; lev < max_lev; lev++)
  142.                 if (part[lev])
  143.                         list = merge(priv, cmp, part[lev], list);
  144.  
  145.         merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
  146. }
  147. EXPORT_SYMBOL(list_sort);
  148.