sort.c 2.47 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
Linus Torvalds's avatar
Linus Torvalds committed
2 3 4 5 6 7
/*
 * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
 *
 * Jan 23 2005  Matt Mackall <mpm@selenic.com>
 */

8 9
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

10 11
#include <linux/types.h>
#include <linux/export.h>
12
#include <linux/sort.h>
Linus Torvalds's avatar
Linus Torvalds committed
13

14 15 16 17 18 19
static int alignment_ok(const void *base, int align)
{
	return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
		((unsigned long)base & (align - 1)) == 0;
}

20
static void u32_swap(void *a, void *b, int size)
Linus Torvalds's avatar
Linus Torvalds committed
21 22 23 24 25 26
{
	u32 t = *(u32 *)a;
	*(u32 *)a = *(u32 *)b;
	*(u32 *)b = t;
}

27 28 29 30 31 32 33
static void u64_swap(void *a, void *b, int size)
{
	u64 t = *(u64 *)a;
	*(u64 *)a = *(u64 *)b;
	*(u64 *)b = t;
}

34
static void generic_swap(void *a, void *b, int size)
Linus Torvalds's avatar
Linus Torvalds committed
35 36 37 38 39 40 41 42 43 44
{
	char t;

	do {
		t = *(char *)a;
		*(char *)a++ = *(char *)b;
		*(char *)b++ = t;
	} while (--size > 0);
}

45
/**
Linus Torvalds's avatar
Linus Torvalds committed
46 47 48 49
 * sort - sort an array of elements
 * @base: pointer to data to sort
 * @num: number of elements
 * @size: size of each element
50 51
 * @cmp_func: pointer to comparison function
 * @swap_func: pointer to swap function or NULL
Linus Torvalds's avatar
Linus Torvalds committed
52 53
 *
 * This function does a heapsort on the given array. You may provide a
54
 * swap_func function optimized to your element type.
Linus Torvalds's avatar
Linus Torvalds committed
55 56 57 58 59 60 61 62
 *
 * 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,
63 64
	  int (*cmp_func)(const void *, const void *),
	  void (*swap_func)(void *, void *, int size))
Linus Torvalds's avatar
Linus Torvalds committed
65 66
{
	/* pre-scale counters for performance */
67
	int i = (num/2 - 1) * size, n = num * size, c, r;
Linus Torvalds's avatar
Linus Torvalds committed
68

69 70 71 72 73 74 75 76
	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;
	}
Linus Torvalds's avatar
Linus Torvalds committed
77 78 79

	/* heapify */
	for ( ; i >= 0; i -= size) {
80 81
		for (r = i; r * 2 + size < n; r  = c) {
			c = r * 2 + size;
82 83
			if (c < n - size &&
					cmp_func(base + c, base + c + size) < 0)
Linus Torvalds's avatar
Linus Torvalds committed
84
				c += size;
85
			if (cmp_func(base + r, base + c) >= 0)
Linus Torvalds's avatar
Linus Torvalds committed
86
				break;
87
			swap_func(base + r, base + c, size);
Linus Torvalds's avatar
Linus Torvalds committed
88 89 90 91
		}
	}

	/* sort */
92
	for (i = n - size; i > 0; i -= size) {
93
		swap_func(base, base + i, size);
94 95
		for (r = 0; r * 2 + size < i; r = c) {
			c = r * 2 + size;
96 97
			if (c < i - size &&
					cmp_func(base + c, base + c + size) < 0)
Linus Torvalds's avatar
Linus Torvalds committed
98
				c += size;
99
			if (cmp_func(base + r, base + c) >= 0)
Linus Torvalds's avatar
Linus Torvalds committed
100
				break;
101
			swap_func(base + r, base + c, size);
Linus Torvalds's avatar
Linus Torvalds committed
102 103 104 105 106
		}
	}
}

EXPORT_SYMBOL(sort);