OpenCores
URL https://opencores.org/ocsvn/test_project/test_project/trunk

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [lib/] [sort.c] - Blame information for rev 81

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 62 marcus.erl
/*
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/kernel.h>
8
#include <linux/module.h>
9
#include <linux/sort.h>
10
#include <linux/slab.h>
11
 
12
static void u32_swap(void *a, void *b, int size)
13
{
14
        u32 t = *(u32 *)a;
15
        *(u32 *)a = *(u32 *)b;
16
        *(u32 *)b = t;
17
}
18
 
19
static void generic_swap(void *a, void *b, int size)
20
{
21
        char t;
22
 
23
        do {
24
                t = *(char *)a;
25
                *(char *)a++ = *(char *)b;
26
                *(char *)b++ = t;
27
        } while (--size > 0);
28
}
29
 
30
/**
31
 * sort - sort an array of elements
32
 * @base: pointer to data to sort
33
 * @num: number of elements
34
 * @size: size of each element
35
 * @cmp: pointer to comparison function
36
 * @swap: pointer to swap function or NULL
37
 *
38
 * This function does a heapsort on the given array. You may provide a
39
 * swap function optimized to your element type.
40
 *
41
 * Sorting time is O(n log n) both on average and worst-case. While
42
 * qsort is about 20% faster on average, it suffers from exploitable
43
 * O(n*n) worst-case behavior and extra memory requirements that make
44
 * it less suitable for kernel use.
45
 */
46
 
47
void sort(void *base, size_t num, size_t size,
48
          int (*cmp)(const void *, const void *),
49
          void (*swap)(void *, void *, int size))
50
{
51
        /* pre-scale counters for performance */
52
        int i = (num/2 - 1) * size, n = num * size, c, r;
53
 
54
        if (!swap)
55
                swap = (size == 4 ? u32_swap : generic_swap);
56
 
57
        /* heapify */
58
        for ( ; i >= 0; i -= size) {
59
                for (r = i; r * 2 + size < n; r  = c) {
60
                        c = r * 2 + size;
61
                        if (c < n - size && cmp(base + c, base + c + size) < 0)
62
                                c += size;
63
                        if (cmp(base + r, base + c) >= 0)
64
                                break;
65
                        swap(base + r, base + c, size);
66
                }
67
        }
68
 
69
        /* sort */
70
        for (i = n - size; i > 0; i -= size) {
71
                swap(base, base + i, size);
72
                for (r = 0; r * 2 + size < i; r = c) {
73
                        c = r * 2 + size;
74
                        if (c < i - size && cmp(base + c, base + c + size) < 0)
75
                                c += size;
76
                        if (cmp(base + r, base + c) >= 0)
77
                                break;
78
                        swap(base + r, base + c, size);
79
                }
80
        }
81
}
82
 
83
EXPORT_SYMBOL(sort);
84
 
85
#if 0
86
/* a simple boot-time regression test */
87
 
88
int cmpint(const void *a, const void *b)
89
{
90
        return *(int *)a - *(int *)b;
91
}
92
 
93
static int sort_test(void)
94
{
95
        int *a, i, r = 1;
96
 
97
        a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
98
        BUG_ON(!a);
99
 
100
        printk("testing sort()\n");
101
 
102
        for (i = 0; i < 1000; i++) {
103
                r = (r * 725861) % 6599;
104
                a[i] = r;
105
        }
106
 
107
        sort(a, 1000, sizeof(int), cmpint, NULL);
108
 
109
        for (i = 0; i < 999; i++)
110
                if (a[i] > a[i+1]) {
111
                        printk("sort() failed!\n");
112
                        break;
113
                }
114
 
115
        kfree(a);
116
 
117
        return 0;
118
}
119
 
120
module_init(sort_test);
121
#endif

powered by: WebSVN 2.1.0

© copyright 1999-2025 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.