Used by later btrfs_alloc_chunk() rework. Signed-off-by: Qu Wenruo <w...@suse.com> --- Makefile | 3 +- kernel-lib/sort.c | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ kernel-lib/sort.h | 16 +++++++++ 3 files changed, 122 insertions(+), 1 deletion(-) create mode 100644 kernel-lib/sort.c create mode 100644 kernel-lib/sort.h
diff --git a/Makefile b/Makefile index 327cdfa08eba..3db7bbe04662 100644 --- a/Makefile +++ b/Makefile @@ -106,7 +106,8 @@ objects = ctree.o disk-io.o kernel-lib/radix-tree.o extent-tree.o print-tree.o \ qgroup.o free-space-cache.o kernel-lib/list_sort.o props.o \ kernel-shared/ulist.o qgroup-verify.o backref.o string-table.o task-utils.o \ inode.o file.o find-root.o free-space-tree.o help.o send-dump.o \ - fsfeatures.o kernel-lib/tables.o kernel-lib/raid56.o transaction.o + fsfeatures.o kernel-lib/tables.o kernel-lib/raid56.o transaction.o \ + kernel-lib/sort.o cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \ cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \ cmds-quota.o cmds-qgroup.o cmds-replace.o check/main.o \ diff --git a/kernel-lib/sort.c b/kernel-lib/sort.c new file mode 100644 index 000000000000..70ae3dbe2852 --- /dev/null +++ b/kernel-lib/sort.c @@ -0,0 +1,104 @@ +/* + * taken from linux kernel lib/sort.c, removed kernel config code and adapted + * for btrfsprogs + */ + +#include "sort.h" + +// SPDX-License-Identifier: GPL-2.0 +/* + * A fast, small, non-recursive O(nlog n) sort for the Linux kernel + * + * Jan 23 2005 Matt Mackall <m...@selenic.com> + */ + +static int alignment_ok(const void *base, int align) +{ + return ((unsigned long)base & (align - 1)) == 0; +} + +static void u32_swap(void *a, void *b, int size) +{ + u32 t = *(u32 *)a; + *(u32 *)a = *(u32 *)b; + *(u32 *)b = t; +} + +static void u64_swap(void *a, void *b, int size) +{ + u64 t = *(u64 *)a; + *(u64 *)a = *(u64 *)b; + *(u64 *)b = t; +} + +static void generic_swap(void *a, void *b, int size) +{ + char t; + + do { + t = *(char *)a; + *(char *)a++ = *(char *)b; + *(char *)b++ = t; + } while (--size > 0); +} + +/** + * sort - sort an array of elements + * @base: pointer to data to sort + * @num: number of elements + * @size: size of each element + * @cmp_func: pointer to comparison function + * @swap_func: pointer to swap function or NULL + * + * This function does a heapsort on the given array. You may provide a + * swap_func function optimized to your element type. + * + * Sorting time is O(n log n) both on average and worst-case. While + * qsort is about 20% faster on average, it suffers from exploitable + * O(n*n) worst-case behavior and extra memory requirements that make + * it less suitable for kernel use. + */ + +void sort(void *base, size_t num, size_t size, + int (*cmp_func)(const void *, const void *), + void (*swap_func)(void *, void *, int size)) +{ + /* pre-scale counters for performance */ + int i = (num/2 - 1) * size, n = num * size, c, r; + + if (!swap_func) { + if (size == 4 && alignment_ok(base, 4)) + swap_func = u32_swap; + else if (size == 8 && alignment_ok(base, 8)) + swap_func = u64_swap; + else + swap_func = generic_swap; + } + + /* heapify */ + for ( ; i >= 0; i -= size) { + for (r = i; r * 2 + size < n; r = c) { + c = r * 2 + size; + if (c < n - size && + cmp_func(base + c, base + c + size) < 0) + c += size; + if (cmp_func(base + r, base + c) >= 0) + break; + swap_func(base + r, base + c, size); + } + } + + /* sort */ + for (i = n - size; i > 0; i -= size) { + swap_func(base, base + i, size); + for (r = 0; r * 2 + size < i; r = c) { + c = r * 2 + size; + if (c < i - size && + cmp_func(base + c, base + c + size) < 0) + c += size; + if (cmp_func(base + r, base + c) >= 0) + break; + swap_func(base + r, base + c, size); + } + } +} diff --git a/kernel-lib/sort.h b/kernel-lib/sort.h new file mode 100644 index 000000000000..9355e01248f2 --- /dev/null +++ b/kernel-lib/sort.h @@ -0,0 +1,16 @@ +/* + * taken from linux kernel include/list_sort.h + * changed include to kerncompat.h + */ + +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_SORT_H +#define _LINUX_SORT_H + +#include "kerncompat.h" + +void sort(void *base, size_t num, size_t size, + int (*cmp)(const void *, const void *), + void (*swap)(void *, void *, int)); + +#endif -- 2.16.1 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html