diff options
author | Jakub Kicinski <kuba@kernel.org> | 2024-03-22 02:14:13 +0300 |
---|---|---|
committer | Jakub Kicinski <kuba@kernel.org> | 2024-03-22 02:15:08 +0300 |
commit | 537c2e91d3549e5d6020bb0576cf9b54a845255f (patch) | |
tree | c09e8a1b7d733cde19b0c72678c28fb2bc97ff6b /lib/sort.c | |
parent | 237bb5f7f7f55ec5f773469a974c61a49c298625 (diff) | |
parent | cba9ffdb9913dfe6be29f049ce920ce451ce7cc4 (diff) | |
download | linux-537c2e91d3549e5d6020bb0576cf9b54a845255f.tar.xz |
Merge git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net
Cross-merge networking fixes after downstream PR.
Signed-off-by: Jakub Kicinski <kuba@kernel.org>
Diffstat (limited to 'lib/sort.c')
-rw-r--r-- | lib/sort.c | 20 |
1 files changed, 15 insertions, 5 deletions
diff --git a/lib/sort.c b/lib/sort.c index b399bf10d675..a0509088f82a 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -215,6 +215,7 @@ void sort_r(void *base, size_t num, size_t size, /* pre-scale counters for performance */ size_t n = num * size, a = (num/2) * size; const unsigned int lsbit = size & -size; /* Used to find parent */ + size_t shift = 0; if (!a) /* num < 2 || size == 0 */ return; @@ -242,12 +243,21 @@ void sort_r(void *base, size_t num, size_t size, for (;;) { size_t b, c, d; - if (a) /* Building heap: sift down --a */ - a -= size; - else if (n -= size) /* Sorting: Extract root to --n */ + if (a) /* Building heap: sift down a */ + a -= size << shift; + else if (n > 3 * size) { /* Sorting: Extract two largest elements */ + n -= size; do_swap(base, base + n, size, swap_func, priv); - else /* Sort complete */ + shift = do_cmp(base + size, base + 2 * size, cmp_func, priv) <= 0; + a = size << shift; + n -= size; + do_swap(base + a, base + n, size, swap_func, priv); + } else if (n > size) { /* Sorting: Extract root */ + n -= size; + do_swap(base, base + n, size, swap_func, priv); + } else { /* Sort complete */ break; + } /* * Sift element at "a" down into heap. This is the @@ -262,7 +272,7 @@ void sort_r(void *base, size_t num, size_t size, * average, 3/4 worst-case.) */ for (b = a; c = 2*b + size, (d = c + size) < n;) - b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d; + b = do_cmp(base + c, base + d, cmp_func, priv) > 0 ? c : d; if (d == n) /* Special case last leaf with no sibling */ b = c; |