Hi Rasmus, Andy,
On Wed, Aug 25, 2021 at 09:05:19AM +0200, Rasmus Villemoes wrote:
> On 24/08/2021 15.33, Andy Shevchenko wrote:
> > In some cases we want to circular shift an array of elements.
> > Introduce rotate() helper for that.
> >
> > Signed-off-by: Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>
> > ---
> > include/linux/sort.h | 3 +++
> > lib/sort.c | 61 ++++++++++++++++++++++++++++++++++++++++++++
> > 2 files changed, 64 insertions(+)
> >
> > diff --git a/include/linux/sort.h b/include/linux/sort.h
> > index b5898725fe9d..c881acb12ffc 100644
> > --- a/include/linux/sort.h
> > +++ b/include/linux/sort.h
> > @@ -13,4 +13,7 @@ void sort(void *base, size_t num, size_t size,
> > cmp_func_t cmp_func,
> > swap_func_t swap_func);
> >
> > +void rotate(void *base, size_t num, size_t size, size_t by,
> > + swap_func_t swap_func);
> > +
> > #endif
> > diff --git a/lib/sort.c b/lib/sort.c
> > index d9b2f5b73620..b9243f8db34b 100644
> > --- a/lib/sort.c
> > +++ b/lib/sort.c
> > @@ -14,6 +14,7 @@
> >
> > #include <linux/types.h>
> > #include <linux/export.h>
> > +#include <linux/minmax.h>
> > #include <linux/sort.h>
> >
> > /**
> > @@ -275,3 +276,63 @@ void sort(void *base, size_t num, size_t size,
> > return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func);
> > }
> > EXPORT_SYMBOL(sort);
> > +
> > +/**
> > + * rotate - rotate an array of elements by a number of elements
> > + * @base: pointer to data to sort
>
> sort?
>
> > + * @num: number of elements
> > + * @size: size of each element
> > + * @by: number of elements to rotate by
>
> Perhaps add (0 <= @by < @num) or something like that, and/or start the
> implementation with "if (num <= 1) return; if (by >= num) by %= num;"
The latter could be done unconditionally.
>
> > + * @swap_func: pointer to swap function or NULL
> > + *
> > + * Helper function to advance all the elements of a circular buffer by
> > + * @by positions.
> > + */
> > +void rotate(void *base, size_t num, size_t size, size_t by,
> > + swap_func_t swap_func)
> > +{
> > + struct {
> > + size_t begin, end;
> > + } arr[2] = {
> > + { .begin = 0, .end = by - 1 },
> > + { .begin = by, .end = num - 1 },
> > + };
>
> I see you just copied-and-adapted, but I think the code would be much
> easier to read without all those plus/minus ones all over.
Now that I think about it, they can be just removed. In that case end
refers to the element following end, rather than the last element.
>
> > + swap_func = choose_swap_func(swap_func, base, size);
> > +
> > +#define CHUNK_SIZE(a) ((a)->end - (a)->begin + 1)
> > +
> > + /* Loop as long as we have out-of-place entries */
> > + while (CHUNK_SIZE(&arr[0]) && CHUNK_SIZE(&arr[1])) {
> > + size_t size0, i;
> > +
> > + /*
> > + * Find the number of entries that can be arranged on this
> > + * iteration.
> > + */
> > + size0 = min(CHUNK_SIZE(&arr[0]), CHUNK_SIZE(&arr[1]));
> > +
> > + /* Swap the entries in two parts of the array */
> > + for (i = 0; i < size0; i++) {
> > + void *a = base + size * (arr[0].begin + i);
> > + void *b = base + size * (arr[1].begin + i);
> > +
> > + do_swap(a, b, size, swap_func);
> > + }
> > +
> > + if (CHUNK_SIZE(&arr[0]) > CHUNK_SIZE(&arr[1])) {
> > + /* The end of the first array remains unarranged */
> > + arr[0].begin += size0;
> > + } else {
> > + /*
> > + * The first array is fully arranged so we proceed
> > + * handling the next one.
> > + */
> > + arr[0].begin = arr[1].begin;
> > + arr[0].end = arr[1].begin + size0 - 1;
> > + arr[1].begin += size0;
> > + }
> > + }
>
> Perhaps add a small self-test, it's not at all obvious how this works
> (perhaps it's some standard CS101 algorithm for rotating in-place, I
> don't know, but even then an implementation can have off-by-ones and
> corner cases).
I don't know, I wrote this to fix a bug in the ipu3-cio2 driver. ;-) The
hardware, and so the arguments, were static. Nice to see it would be useful
elsewhere almost as-is.
>
> for (len = 1; len < 15; ++len) {
> for (by = 0; by <= len; ++by) {
> for (i = 0; i < len; ++i)
> arr[i] = i;
> rotate(arr, len, sizeof(int), by);
> for (i = 0; i < len; ++i)
> if (arr[i] != (i + by) % len)
> error();
> }
> }
Makes sense to add something like that.
After addressing the comments, for patches from 1 to 3:
Acked-by: Sakari Ailus <sakari.ailus@xxxxxxxxxxxxxxx>
--
Kind regards,
Sakari Ailus
