lib/list_sort.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include <linux/kernel.h>
   3 #include <linux/bug.h>
   4 #include <linux/compiler.h>
   5 #include <linux/export.h>
   6 #include <linux/string.h>
   7 #include <linux/list_sort.h>
   8 #include <linux/list.h>
   9
  10 typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,
  11                 struct list_head const *, struct list_head const *);
  12
  13 /*
  14  * Returns a list organized in an intermediate format suited
  15  * to chaining of merge() calls: null-terminated, no reserved or
  16  * sentinel head node, "prev" links not maintained.
  17  */
  18 __attribute__((nonnull(2,3,4)))
  19 static struct list_head *merge(void *priv, cmp_func cmp,
  20                                 struct list_head *a, struct list_head *b)
  21 {
  22         struct list_head *head, **tail = &head;
  23
  24         for (;;) {
  25                 /* if equal, take 'a' -- important for sort stability */
  26                 if (cmp(priv, a, b) <= 0) {
  27                         *tail = a;
  28                         tail = &a->next;
  29                         a = a->next;
  30                         if (!a) {
  31                                 *tail = b;
  32                                 break;
  33                         }
  34                 } else {
  35                         *tail = b;
  36                         tail = &b->next;
  37                         b = b->next;
  38                         if (!b) {
  39                                 *tail = a;
  40                                 break;
  41                         }
  42                 }
  43         }
  44         return head;
  45 }
  46
  47 /*
  48  * Combine final list merge with restoration of standard doubly-linked
  49  * list structure.  This approach duplicates code from merge(), but
  50  * runs faster than the tidier alternatives of either a separate final
  51  * prev-link restoration pass, or maintaining the prev links
  52  * throughout.
  53  */
  54 __attribute__((nonnull(2,3,4,5)))
  55 static void merge_final(void *priv, cmp_func cmp, struct list_head *head,
  56                         struct list_head *a, struct list_head *b)
  57 {
  58         struct list_head *tail = head;
  59         u8 count = 0;
  60
  61         for (;;) {
  62                 /* if equal, take 'a' -- important for sort stability */
  63                 if (cmp(priv, a, b) <= 0) {
  64                         tail->next = a;
  65                         a->prev = tail;
  66                         tail = a;
  67                         a = a->next;
  68                         if (!a)
  69                                 break;
  70                 } else {
  71                         tail->next = b;
  72                         b->prev = tail;
  73                         tail = b;
  74                         b = b->next;
  75                         if (!b) {
  76                                 b = a;
  77                                 break;
  78                         }
  79                 }
  80         }
  81
  82         /* Finish linking remainder of list b on to tail */
  83         tail->next = b;
  84         do {
  85                 /*
  86                  * If the merge is highly unbalanced (e.g. the input is
  87                  * already sorted), this loop may run many iterations.
  88                  * Continue callbacks to the client even though no
  89                  * element comparison is needed, so the client's cmp()
  90                  * routine can invoke cond_resched() periodically.
  91                  */
  92                 if (unlikely(!++count))
  93                         cmp(priv, b, b);
  94                 b->prev = tail;
  95                 tail = b;
  96                 b = b->next;
  97         } while (b);
  98
  99         /* And the final links to make a circular doubly-linked list */
 100         tail->next = head;
 101         head->prev = tail;
 102 }
 103
 104 /**
 105  * list_sort - sort a list
 106  * @priv: private data, opaque to list_sort(), passed to @cmp
 107  * @head: the list to sort
 108  * @cmp: the elements comparison function
 109  *
 110  * This function implements a bottom-up merge sort, which has O(nlog(n))
 111  * complexity.  We use depth-first order to take advantage of cacheing.
 112  * (E.g. when we get to the fourth element, we immediately merge the
 113  * first two 2-element lists.)
 114  *
 115  * The comparison funtion @cmp must return > 0 if @a should sort after
 116  * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
 117  * sort before @b *or* their original order should be preserved.  It is
 118  * always called with the element that came first in the input in @a,
 119  * and list_sort is a stable sort, so it is not necessary to distinguish
 120  * the @a < @b and @a == @b cases.
 121  *
 122  * This is compatible with two styles of @cmp function:
 123  * - The traditional style which returns <0 / =0 / >0, or
 124  * - Returning a boolean 0/1.
 125  * The latter offers a chance to save a few cycles in the comparison
 126  * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
 127  *
 128  * A good way to write a multi-word comparison is
 129  *      if (a->high != b->high)
 130  *              return a->high > b->high;
 131  *      if (a->middle != b->middle)
 132  *              return a->middle > b->middle;
 133  *      return a->low > b->low;
 134  */
 135 __attribute__((nonnull(2,3)))
 136 void list_sort(void *priv, struct list_head *head,
 137                 int (*cmp)(void *priv, struct list_head *a,
 138                         struct list_head *b))
 139 {
 140         struct list_head *list = head->next, *pending = NULL;
 141         size_t count = 0;       /* Count of pending */
 142
 143         if (list == head->prev) /* Zero or one elements */
 144                 return;
 145
 146         /* Convert to a null-terminated singly-linked list. */
 147         head->prev->next = NULL;
 148
 149         /*
 150          * Data structure invariants:
 151          * - All lists are singly linked and null-terminated; prev
 152          *   pointers are not maintained.
 153          * - pending is a prev-linked "list of lists" of sorted
 154          *   sublists awaiting further merging.
 155          * - Each of the sorted sublists is power-of-two in size,
 156          *   corresponding to bits set in "count".
 157          * - Sublists are sorted by size and age, smallest & newest at front.
 158          */
 159         do {
 160                 size_t bits;
 161                 struct list_head *cur = list;
 162
 163                 /* Extract the head of "list" as a single-element list "cur" */
 164                 list = list->next;
 165                 cur->next = NULL;
 166
 167                 /* Do merges corresponding to set lsbits in count */
 168                 for (bits = count; bits & 1; bits >>= 1) {
 169                         cur = merge(priv, (cmp_func)cmp, pending, cur);
 170                         pending = pending->prev;  /* Untouched by merge() */
 171                 }
 172                 /* And place the result at the head of "pending" */
 173                 cur->prev = pending;
 174                 pending = cur;
 175                 count++;
 176         } while (list->next);
 177
 178         /* Now merge together last element with all pending lists */
 179         while (pending->prev) {
 180                 list = merge(priv, (cmp_func)cmp, pending, list);
 181                 pending = pending->prev;
 182         }
 183         /* The final merge, rebuilding prev links */
 184         merge_final(priv, (cmp_func)cmp, head, pending, list);
 185 }
 186 EXPORT_SYMBOL(list_sort);