| Message ID | 20250128163859.1883260-21-agruenba@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | bcachefs: eytzinger code | expand |
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@redhat.com> > --- > 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 >
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); } } }
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. Signed-off-by: Andreas Gruenbacher <agruenba@redhat.com> --- fs/bcachefs/eytzinger.c | 42 ++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 21 deletions(-)