LXR RHEL4/lib/sort.c

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