b24413180f560 (Greg Kroah-Hartman 2017-11-01 15:07:57 +0100 1) // SPDX-License-Identifier: GPL-2.0
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 2) #include <linux/kernel.h>
7259fa0424208 (Rasmus Villemoes 2015-02-12 15:02:48 -0800 3) #include <linux/bug.h>
7259fa0424208 (Rasmus Villemoes 2015-02-12 15:02:48 -0800 4) #include <linux/compiler.h>
7259fa0424208 (Rasmus Villemoes 2015-02-12 15:02:48 -0800 5) #include <linux/export.h>
7259fa0424208 (Rasmus Villemoes 2015-02-12 15:02:48 -0800 6) #include <linux/string.h>
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 7) #include <linux/list_sort.h>
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 8) #include <linux/list.h>
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 9)
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 10) /*
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 11) * Returns a list organized in an intermediate format suited
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 12) * to chaining of merge() calls: null-terminated, no reserved or
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 13) * sentinel head node, "prev" links not maintained.
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 14) */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 15) __attribute__((nonnull(2,3,4)))
4f0f586bf0c89 (Sami Tolvanen 2021-04-08 11:28:34 -0700 16) static struct list_head *merge(void *priv, list_cmp_func_t cmp,
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 17) struct list_head *a, struct list_head *b)
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 18) {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 19) struct list_head *head, **tail = &head;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 20)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 21) for (;;) {
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 22) /* if equal, take 'a' -- important for sort stability */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 23) if (cmp(priv, a, b) <= 0) {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 24) *tail = a;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 25) tail = &a->next;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 26) a = a->next;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 27) if (!a) {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 28) *tail = b;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 29) break;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 30) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 31) } else {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 32) *tail = b;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 33) tail = &b->next;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 34) b = b->next;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 35) if (!b) {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 36) *tail = a;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 37) break;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 38) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 39) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 40) }
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 41) return head;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 42) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 43)
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 44) /*
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 45) * Combine final list merge with restoration of standard doubly-linked
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 46) * list structure. This approach duplicates code from merge(), but
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 47) * runs faster than the tidier alternatives of either a separate final
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 48) * prev-link restoration pass, or maintaining the prev links
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 49) * throughout.
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 50) */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 51) __attribute__((nonnull(2,3,4,5)))
4f0f586bf0c89 (Sami Tolvanen 2021-04-08 11:28:34 -0700 52) static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 53) struct list_head *a, struct list_head *b)
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 54) {
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 55) struct list_head *tail = head;
61b3d6c48f059 (Rasmus Villemoes 2014-08-06 16:09:44 -0700 56) u8 count = 0;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 57)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 58) for (;;) {
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 59) /* if equal, take 'a' -- important for sort stability */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 60) if (cmp(priv, a, b) <= 0) {
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 61) tail->next = a;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 62) a->prev = tail;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 63) tail = a;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 64) a = a->next;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 65) if (!a)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 66) break;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 67) } else {
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 68) tail->next = b;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 69) b->prev = tail;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 70) tail = b;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 71) b = b->next;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 72) if (!b) {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 73) b = a;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 74) break;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 75) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 76) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 77) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 78)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 79) /* Finish linking remainder of list b on to tail */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 80) tail->next = b;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 81) do {
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 82) /*
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 83) * If the merge is highly unbalanced (e.g. the input is
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 84) * already sorted), this loop may run many iterations.
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 85) * Continue callbacks to the client even though no
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 86) * element comparison is needed, so the client's cmp()
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 87) * routine can invoke cond_resched() periodically.
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 88) */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 89) if (unlikely(!++count))
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 90) cmp(priv, b, b);
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 91) b->prev = tail;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 92) tail = b;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 93) b = b->next;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 94) } while (b);
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 95)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 96) /* And the final links to make a circular doubly-linked list */
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 97) tail->next = head;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 98) head->prev = tail;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 99) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 100)
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 101) /**
02b12b7a28faa (Don Mullis 2010-03-05 13:43:15 -0800 102) * list_sort - sort a list
02b12b7a28faa (Don Mullis 2010-03-05 13:43:15 -0800 103) * @priv: private data, opaque to list_sort(), passed to @cmp
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 104) * @head: the list to sort
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 105) * @cmp: the elements comparison function
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 106) *
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 107) * The comparison funtion @cmp must return > 0 if @a should sort after
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 108) * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 109) * sort before @b *or* their original order should be preserved. It is
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 110) * always called with the element that came first in the input in @a,
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 111) * and list_sort is a stable sort, so it is not necessary to distinguish
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 112) * the @a < @b and @a == @b cases.
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 113) *
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 114) * This is compatible with two styles of @cmp function:
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 115) * - The traditional style which returns <0 / =0 / >0, or
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 116) * - Returning a boolean 0/1.
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 117) * The latter offers a chance to save a few cycles in the comparison
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 118) * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 119) *
f35a1abd9e7a0 (Jonathan Corbet 2019-05-22 13:41:45 -0600 120) * A good way to write a multi-word comparison is::
f35a1abd9e7a0 (Jonathan Corbet 2019-05-22 13:41:45 -0600 121) *
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 122) * if (a->high != b->high)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 123) * return a->high > b->high;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 124) * if (a->middle != b->middle)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 125) * return a->middle > b->middle;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 126) * return a->low > b->low;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 127) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 128) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 129) * This mergesort is as eager as possible while always performing at least
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 130) * 2:1 balanced merges. Given two pending sublists of size 2^k, they are
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 131) * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 132) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 133) * Thus, it will avoid cache thrashing as long as 3*2^k elements can
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 134) * fit into the cache. Not quite as good as a fully-eager bottom-up
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 135) * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 136) * the common case that everything fits into L1.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 137) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 138) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 139) * The merging is controlled by "count", the number of elements in the
e89b6358052de (ToastC 2021-05-06 18:03:31 -0700 140) * pending lists. This is beautifully simple code, but rather subtle.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 141) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 142) * Each time we increment "count", we set one bit (bit k) and clear
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 143) * bits k-1 .. 0. Each time this happens (except the very first time
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 144) * for each bit, when count increments to 2^k), we merge two lists of
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 145) * size 2^k into one list of size 2^(k+1).
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 146) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 147) * This merge happens exactly when the count reaches an odd multiple of
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 148) * 2^k, which is when we have 2^k elements pending in smaller lists,
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 149) * so it's safe to merge away two lists of size 2^k.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 150) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 151) * After this happens twice, we have created two lists of size 2^(k+1),
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 152) * which will be merged into a list of size 2^(k+2) before we create
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 153) * a third list of size 2^(k+1), so there are never more than two pending.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 154) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 155) * The number of pending lists of size 2^k is determined by the
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 156) * state of bit k of "count" plus two extra pieces of information:
4ae5b8f2140d1 (Mauro Carvalho Chehab 2019-06-18 15:51:19 -0300 157) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 158) * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 159) * - Whether the higher-order bits are zero or non-zero (i.e.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 160) * is count >= 2^(k+1)).
4ae5b8f2140d1 (Mauro Carvalho Chehab 2019-06-18 15:51:19 -0300 161) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 162) * There are six states we distinguish. "x" represents some arbitrary
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 163) * bits, and "y" represents some arbitrary non-zero bits:
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 164) * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 165) * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 166) * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 167) * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 168) * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 169) * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 170) * (merge and loop back to state 2)
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 171) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 172) * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 173) * bit k-1 is set while the more significant bits are non-zero) and
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 174) * merge them away in the 5->2 transition. Note in particular that just
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 175) * before the 5->2 transition, all lower-order bits are 11 (state 3),
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 176) * so there is one list of each smaller size.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 177) *
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 178) * When we reach the end of the input, we merge all the pending
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 179) * lists, from smallest to largest. If you work through cases 2 to
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 180) * 5 above, you can see that the number of elements we merge with a list
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 181) * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 182) * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 183) */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 184) __attribute__((nonnull(2,3)))
4f0f586bf0c89 (Sami Tolvanen 2021-04-08 11:28:34 -0700 185) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 186) {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 187) struct list_head *list = head->next, *pending = NULL;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 188) size_t count = 0; /* Count of pending */
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 189)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 190) if (list == head->prev) /* Zero or one elements */
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 191) return;
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 192)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 193) /* Convert to a null-terminated singly-linked list. */
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 194) head->prev->next = NULL;
2c761270d5520 (Dave Chinner 2010-01-12 17:39:16 +1100 195)
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 196) /*
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 197) * Data structure invariants:
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 198) * - All lists are singly linked and null-terminated; prev
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 199) * pointers are not maintained.
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 200) * - pending is a prev-linked "list of lists" of sorted
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 201) * sublists awaiting further merging.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 202) * - Each of the sorted sublists is power-of-two in size.
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 203) * - Sublists are sorted by size and age, smallest & newest at front.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 204) * - There are zero to two sublists of each size.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 205) * - A pair of pending sublists are merged as soon as the number
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 206) * of following pending elements equals their size (i.e.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 207) * each time count reaches an odd multiple of that size).
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 208) * That ensures each later final merge will be at worst 2:1.
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 209) * - Each round consists of:
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 210) * - Merging the two sublists selected by the highest bit
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 211) * which flips when count is incremented, and
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 212) * - Adding an element from the input as a size-1 sublist.
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 213) */
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 214) do {
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 215) size_t bits;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 216) struct list_head **tail = &pending;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 217)
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 218) /* Find the least-significant clear bit in count */
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 219) for (bits = count; bits & 1; bits >>= 1)
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 220) tail = &(*tail)->prev;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 221) /* Do the indicated merge */
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 222) if (likely(bits)) {
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 223) struct list_head *a = *tail, *b = a->prev;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 224)
4f0f586bf0c89 (Sami Tolvanen 2021-04-08 11:28:34 -0700 225) a = merge(priv, cmp, b, a);
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 226) /* Install the merged result in place of the inputs */
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 227) a->prev = b->prev;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 228) *tail = a;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 229) }
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 230)
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 231) /* Move one element from input list to pending */
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 232) list->prev = pending;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 233) pending = list;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 234) list = list->next;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 235) pending->next = NULL;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 236) count++;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 237) } while (list);
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 238)
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 239) /* End of input; merge together all the pending lists. */
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 240) list = pending;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 241) pending = pending->prev;
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 242) for (;;) {
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 243) struct list_head *next = pending->prev;
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 244)
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 245) if (!next)
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 246) break;
4f0f586bf0c89 (Sami Tolvanen 2021-04-08 11:28:34 -0700 247) list = merge(priv, cmp, pending, list);
b5c56e0cdd629 (George Spelvin 2019-05-14 15:43:02 -0700 248) pending = next;
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 249) }
043b3f7b6388f (George Spelvin 2019-05-14 15:42:58 -0700 250) /* The final merge, rebuilding prev links */
4f0f586bf0c89 (Sami Tolvanen 2021-04-08 11:28:34 -0700 251) merge_final(priv, cmp, head, pending, list);
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 252) }
835cc0c8477fd (Don Mullis 2010-03-05 13:43:15 -0800 253) EXPORT_SYMBOL(list_sort);
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags