Blame view
lib/sort.c
2.47 KB
b24413180 License cleanup: ... |
1 |
// SPDX-License-Identifier: GPL-2.0 |
1da177e4c Linux-2.6.12-rc2 |
2 3 4 5 6 |
/* * A fast, small, non-recursive O(nlog n) sort for the Linux kernel * * Jan 23 2005 Matt Mackall <mpm@selenic.com> */ |
c5adae958 lib: add CONFIG_T... |
7 |
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
42cf80965 lib/sort.c: use s... |
8 9 |
#include <linux/types.h> #include <linux/export.h> |
ecec4cb7a [PATCH] lib/sort.... |
10 |
#include <linux/sort.h> |
1da177e4c Linux-2.6.12-rc2 |
11 |
|
ca96ab859 lib/sort: Add 64 ... |
12 13 14 15 16 |
static int alignment_ok(const void *base, int align) { return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) || ((unsigned long)base & (align - 1)) == 0; } |
ecec4cb7a [PATCH] lib/sort.... |
17 |
static void u32_swap(void *a, void *b, int size) |
1da177e4c Linux-2.6.12-rc2 |
18 19 20 21 22 |
{ u32 t = *(u32 *)a; *(u32 *)a = *(u32 *)b; *(u32 *)b = t; } |
ca96ab859 lib/sort: Add 64 ... |
23 24 25 26 27 28 |
static void u64_swap(void *a, void *b, int size) { u64 t = *(u64 *)a; *(u64 *)a = *(u64 *)b; *(u64 *)b = t; } |
ecec4cb7a [PATCH] lib/sort.... |
29 |
static void generic_swap(void *a, void *b, int size) |
1da177e4c Linux-2.6.12-rc2 |
30 31 32 33 34 35 36 37 38 |
{ char t; do { t = *(char *)a; *(char *)a++ = *(char *)b; *(char *)b++ = t; } while (--size > 0); } |
72fd4a35a [PATCH] Numerous ... |
39 |
/** |
1da177e4c Linux-2.6.12-rc2 |
40 41 42 43 |
* sort - sort an array of elements * @base: pointer to data to sort * @num: number of elements * @size: size of each element |
b53907c01 generic swap(): l... |
44 45 |
* @cmp_func: pointer to comparison function * @swap_func: pointer to swap function or NULL |
1da177e4c Linux-2.6.12-rc2 |
46 47 |
* * This function does a heapsort on the given array. You may provide a |
b53907c01 generic swap(): l... |
48 |
* swap_func function optimized to your element type. |
1da177e4c Linux-2.6.12-rc2 |
49 50 51 52 53 54 55 56 |
* * 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, |
b53907c01 generic swap(): l... |
57 58 |
int (*cmp_func)(const void *, const void *), void (*swap_func)(void *, void *, int size)) |
1da177e4c Linux-2.6.12-rc2 |
59 60 |
{ /* pre-scale counters for performance */ |
d3717bdf8 [PATCH] low perfo... |
61 |
int i = (num/2 - 1) * size, n = num * size, c, r; |
1da177e4c Linux-2.6.12-rc2 |
62 |
|
ca96ab859 lib/sort: Add 64 ... |
63 64 65 66 67 68 69 70 |
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; } |
1da177e4c Linux-2.6.12-rc2 |
71 72 73 |
/* heapify */ for ( ; i >= 0; i -= size) { |
d3717bdf8 [PATCH] low perfo... |
74 75 |
for (r = i; r * 2 + size < n; r = c) { c = r * 2 + size; |
b53907c01 generic swap(): l... |
76 77 |
if (c < n - size && cmp_func(base + c, base + c + size) < 0) |
1da177e4c Linux-2.6.12-rc2 |
78 |
c += size; |
b53907c01 generic swap(): l... |
79 |
if (cmp_func(base + r, base + c) >= 0) |
1da177e4c Linux-2.6.12-rc2 |
80 |
break; |
b53907c01 generic swap(): l... |
81 |
swap_func(base + r, base + c, size); |
1da177e4c Linux-2.6.12-rc2 |
82 83 84 85 |
} } /* sort */ |
995e4286a lib/sort.c optimi... |
86 |
for (i = n - size; i > 0; i -= size) { |
b53907c01 generic swap(): l... |
87 |
swap_func(base, base + i, size); |
d3717bdf8 [PATCH] low perfo... |
88 89 |
for (r = 0; r * 2 + size < i; r = c) { c = r * 2 + size; |
b53907c01 generic swap(): l... |
90 91 |
if (c < i - size && cmp_func(base + c, base + c + size) < 0) |
1da177e4c Linux-2.6.12-rc2 |
92 |
c += size; |
b53907c01 generic swap(): l... |
93 |
if (cmp_func(base + r, base + c) >= 0) |
1da177e4c Linux-2.6.12-rc2 |
94 |
break; |
b53907c01 generic swap(): l... |
95 |
swap_func(base + r, base + c, size); |
1da177e4c Linux-2.6.12-rc2 |
96 97 98 99 100 |
} } } EXPORT_SYMBOL(sort); |