path: root/lib/sort.c (plain)
blob: fc20df42aa6f2945aae8586c3c4d3599ca6d67f0

1	/*
2	* A fast, small, non-recursive O(nlog n) sort for the Linux kernel
3	*
4	* Jan 23 2005 Matt Mackall <mpm@selenic.com>
5	*/
6
7	#include <linux/types.h>
8	#include <linux/export.h>
9	#include <linux/sort.h>
10
11	static int alignment_ok(const void *base, int align)
12	{
13	return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
14	((unsigned long)base & (align - 1)) == 0;
15	}
16
17	static void u32_swap(void *a, void *b, int size)
18	{
19	u32 t = *(u32 *)a;
20	*(u32 *)a = *(u32 *)b;
21	*(u32 *)b = t;
22	}
23
24	static void u64_swap(void *a, void *b, int size)
25	{
26	u64 t = *(u64 *)a;
27	*(u64 *)a = *(u64 *)b;
28	*(u64 *)b = t;
29	}
30
31	static void generic_swap(void *a, void *b, int size)
32	{
33	char t;
34
35	do {
36	t = *(char *)a;
37	*(char *)a++ = *(char *)b;
38	*(char *)b++ = t;
39	} while (--size > 0);
40	}
41
42	/**
43	* sort - sort an array of elements
44	* @base: pointer to data to sort
45	* @num: number of elements
46	* @size: size of each element
47	* @cmp_func: pointer to comparison function
48	* @swap_func: pointer to swap function or NULL
49	*
50	* This function does a heapsort on the given array. You may provide a
51	* swap_func function optimized to your element type.
52	*
53	* Sorting time is O(n log n) both on average and worst-case. While
54	* qsort is about 20% faster on average, it suffers from exploitable
55	* O(n*n) worst-case behavior and extra memory requirements that make
56	* it less suitable for kernel use.
57	*/
58
59	void sort(void *base, size_t num, size_t size,
60	int (*cmp_func)(const void *, const void *),
61	void (*swap_func)(void *, void *, int size))
62	{
63	/* pre-scale counters for performance */
64	int i = (num/2 - 1) * size, n = num * size, c, r;
65
66	if (!swap_func) {
67	if (size == 4 && alignment_ok(base, 4))
68	swap_func = u32_swap;
69	else if (size == 8 && alignment_ok(base, 8))
70	swap_func = u64_swap;
71	else
72	swap_func = generic_swap;
73	}
74
75	/* heapify */
76	for ( ; i >= 0; i -= size) {
77	for (r = i; r * 2 + size < n; r = c) {
78	c = r * 2 + size;
79	if (c < n - size &&
80	cmp_func(base + c, base + c + size) < 0)
81	c += size;
82	if (cmp_func(base + r, base + c) >= 0)
83	break;
84	swap_func(base + r, base + c, size);
85	}
86	}
87
88	/* sort */
89	for (i = n - size; i > 0; i -= size) {
90	swap_func(base, base + i, size);
91	for (r = 0; r * 2 + size < i; r = c) {
92	c = r * 2 + size;
93	if (c < i - size &&
94	cmp_func(base + c, base + c + size) < 0)
95	c += size;
96	if (cmp_func(base + r, base + c) >= 0)
97	break;
98	swap_func(base + r, base + c, size);
99	}
100	}
101	}
102
103	EXPORT_SYMBOL(sort);
104
105	#if 0
106	#include <linux/slab.h>
107	/* a simple boot-time regression test */
108
109	int cmpint(const void *a, const void *b)
110	{
111	return *(int *)a - *(int *)b;
112	}
113
114	static int sort_test(void)
115	{
116	int *a, i, r = 1;
117
118	a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
119	BUG_ON(!a);
120
121	printk("testing sort()\n");
122
123	for (i = 0; i < 1000; i++) {
124	r = (r * 725861) % 6599;
125	a[i] = r;
126	}
127
128	sort(a, 1000, sizeof(int), cmpint, NULL);
129
130	for (i = 0; i < 999; i++)
131	if (a[i] > a[i+1]) {
132	printk("sort() failed!\n");
133	break;
134	}
135
136	kfree(a);
137
138	return 0;
139	}
140
141	module_init(sort_test);
142	#endif
143