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;"
> + * @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.
> + 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).
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();
}
}
Rasmus
