LXR linux/lib/list

   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#define MAX_LIST_LENGTH_BITS 20
  11
  12/*
  13 * Returns a list organized in an intermediate format suited
  14 * to chaining of merge() calls: null-terminated, no reserved or
  15 * sentinel head node, "prev" links not maintained.
  16 */
  17static struct list_head *merge(void *priv,
  18                                int (*cmp)(void *priv, struct list_head *a,
  19                                        struct list_head *b),
  20                                struct list_head *a, struct list_head *b)
  21{
  22        struct list_head head, *tail = &head;
  23
  24        while (a && b) {
  25                /* if equal, take 'a' -- important for sort stability */
  26                if ((*cmp)(priv, a, b) <= 0) {
  27                        tail->next = a;
  28                        a = a->next;
  29                } else {
  30                        tail->next = b;
  31                        b = b->next;
  32                }
  33                tail = tail->next;
  34        }
  35        tail->next = a?:b;
  36        return head.next;
  37}
  38
  39/*
  40 * Combine final list merge with restoration of standard doubly-linked
  41 * list structure.  This approach duplicates code from merge(), but
  42 * runs faster than the tidier alternatives of either a separate final
  43 * prev-link restoration pass, or maintaining the prev links
  44 * throughout.
  45 */
  46static void merge_and_restore_back_links(void *priv,
  47                                int (*cmp)(void *priv, struct list_head *a,
  48                                        struct list_head *b),
  49                                struct list_head *head,
  50                                struct list_head *a, struct list_head *b)
  51{
  52        struct list_head *tail = head;
  53        u8 count = 0;
  54
  55        while (a && b) {
  56                /* if equal, take 'a' -- important for sort stability */
  57                if ((*cmp)(priv, a, b) <= 0) {
  58                        tail->next = a;
  59                        a->prev = tail;
  60                        a = a->next;
  61                } else {
  62                        tail->next = b;
  63                        b->prev = tail;
  64                        b = b->next;
  65                }
  66                tail = tail->next;
  67        }
  68        tail->next = a ? : b;
  69
  70        do {
  71                /*
  72                 * In worst cases this loop may run many iterations.
  73                 * Continue callbacks to the client even though no
  74                 * element comparison is needed, so the client's cmp()
  75                 * routine can invoke cond_resched() periodically.
  76                 */
  77                if (unlikely(!(++count)))
  78                        (*cmp)(priv, tail->next, tail->next);
  79
  80                tail->next->prev = tail;
  81                tail = tail->next;
  82        } while (tail->next);
  83
  84        tail->next = head;
  85        head->prev = tail;
  86}
  87
  88/**
  89 * list_sort - sort a list
  90 * @priv: private data, opaque to list_sort(), passed to @cmp
  91 * @head: the list to sort
  92 * @cmp: the elements comparison function
  93 *
  94 * This function implements "merge sort", which has O(nlog(n))
  95 * complexity.
  96 *
  97 * The comparison function @cmp must return a negative value if @a
  98 * should sort before @b, and a positive value if @a should sort after
  99 * @b. If @a and @b are equivalent, and their original relative
 100 * ordering is to be preserved, @cmp must return 0.
 101 */
 102void list_sort(void *priv, struct list_head *head,
 103                int (*cmp)(void *priv, struct list_head *a,
 104                        struct list_head *b))
 105{
 106        struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
 107                                                -- last slot is a sentinel */
 108        int lev;  /* index into part[] */
 109        int max_lev = 0;
 110        struct list_head *list;
 111
 112        if (list_empty(head))
 113                return;
 114
 115        memset(part, 0, sizeof(part));
 116
 117        head->prev->next = NULL;
 118        list = head->next;
 119
 120        while (list) {
 121                struct list_head *cur = list;
 122                list = list->next;
 123                cur->next = NULL;
 124
 125                for (lev = 0; part[lev]; lev++) {
 126                        cur = merge(priv, cmp, part[lev], cur);
 127                        part[lev] = NULL;
 128                }
 129                if (lev > max_lev) {
 130                        if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
 131                                printk_once(KERN_DEBUG "list too long for efficiency\n");
 132                                lev--;
 133                        }
 134                        max_lev = lev;
 135                }
 136                part[lev] = cur;
 137        }
 138
 139        for (lev = 0; lev < max_lev; lev++)
 140                if (part[lev])
 141                        list = merge(priv, cmp, part[lev], list);
 142
 143        merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
 144}
 145EXPORT_SYMBOL(list_sort);
 146