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
+ * @num: number of elements
+ * @size: size of each element
+ * @by: number of elements to rotate by
+ * @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 },
+ };
+
+ 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;
+ }
+ }
+#undef CHUNK_SIZE
+}
+EXPORT_SYMBOL(rotate);
--
2.32.0
