On Tue, Jan 28, 2025 at 05:38:57PM +0100, Andreas Gruenbacher wrote:
> In this second step, transform the eytzinger indexes i, j, and k in
> eytzinger1_sort_r() from 0-based to 1-based. This step looks a bit
> messy, but the resulting code is slightly better.
I really hate the cute and paste of lib/sort.c, I wonder if we could get
rid of that by adding a more generic sort that takes an option
"index/access element" helper.
I've come across situations where we want to sort radix trees as well,
so - maybe?
>
> Signed-off-by: Andreas Gruenbacher <agruenba@xxxxxxxxxx>
> ---
> fs/bcachefs/eytzinger.c | 42 ++++++++++++++++++++---------------------
> 1 file changed, 21 insertions(+), 21 deletions(-)
>
> diff --git a/fs/bcachefs/eytzinger.c b/fs/bcachefs/eytzinger.c
> index 93a5819a6878..00cc5f0826e3 100644
> --- a/fs/bcachefs/eytzinger.c
> +++ b/fs/bcachefs/eytzinger.c
> @@ -170,7 +170,7 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size,
> swap_r_func_t swap_func,
> const void *priv)
> {
> - int i, j, k;
> + unsigned i, j, k;
>
> /* called from 'sort' without swap function, let's pick the default */
> if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap_func)
> @@ -186,46 +186,46 @@ static void eytzinger1_sort_r(void *base1, size_t n, size_t size,
> }
>
> /* heapify */
> - for (i = n / 2 - 1; i >= 0; --i) {
> + for (i = n / 2; i >= 1; --i) {
> /* Find the sift-down path all the way to the leaves. */
> - for (j = i; k = j * 2 + 1, k + 1 < n;)
> - j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1;
> + for (j = i; k = j * 2, k < n;)
> + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1;
>
> /* Special case for the last leaf with no sibling. */
> - if (j * 2 + 2 == n)
> - j = j * 2 + 1;
> + if (j * 2 == n)
> + j *= 2;
>
> /* Backtrack to the correct location. */
> - while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i + 1, j + 1) >= 0)
> - j = (j - 1) / 2;
> + while (j != i && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, i, j) >= 0)
> + j /= 2;
>
> /* Shift the element into its correct place. */
> for (k = j; j != i;) {
> - j = (j - 1) / 2;
> - eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1);
> + j /= 2;
> + eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k);
> }
> }
>
> /* sort */
> - for (i = n - 1; i > 0; --i) {
> - eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i + 1);
> + for (i = n; i > 1; --i) {
> + eytzinger1_do_swap(base1, n, size, swap_func, priv, 1, i);
>
> /* Find the sift-down path all the way to the leaves. */
> - for (j = 0; k = j * 2 + 1, k + 1 < i;)
> - j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k + 1, k + 2) > 0 ? k : k + 1;
> + for (j = 1; k = j * 2, k + 1 < i;)
> + j = eytzinger1_do_cmp(base1, n, size, cmp_func, priv, k, k + 1) > 0 ? k : k + 1;
>
> /* Special case for the last leaf with no sibling. */
> - if (j * 2 + 2 == i)
> - j = j * 2 + 1;
> + if (j * 2 + 1 == i)
> + j *= 2;
>
> /* Backtrack to the correct location. */
> - while (j && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j + 1) >= 0)
> - j = (j - 1) / 2;
> + while (j >= 1 && eytzinger1_do_cmp(base1, n, size, cmp_func, priv, 1, j) >= 0)
> + j /= 2;
>
> /* Shift the element into its correct place. */
> - for (k = j; j;) {
> - j = (j - 1) / 2;
> - eytzinger1_do_swap(base1, n, size, swap_func, priv, j + 1, k + 1);
> + for (k = j; j > 1;) {
> + j /= 2;
> + eytzinger1_do_swap(base1, n, size, swap_func, priv, j, k);
> }
> }
> }
> --
> 2.48.1
>
