sort.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    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 #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_func: pointer to comparison function
   36  * @swap_func: pointer to swap function or NULL
   37  *
   38  * This function does a heapsort on the given array. You may provide a
   39  * swap_func 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_func)(const void *, const void *),
   49           void (*swap_func)(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_func)
   55                 swap_func = (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 &&
   62                                         cmp_func(base + c, base + c + size) < 0)
   63                                 c += size;
   64                         if (cmp_func(base + r, base + c) >= 0)
   65                                 break;
   66                         swap_func(base + r, base + c, size);
   67                 }
   68         }
   69 
   70         /* sort */
   71         for (i = n - size; i > 0; i -= size) {
   72                 swap_func(base, base + i, size);
   73                 for (r = 0; r * 2 + size < i; r = c) {
   74                         c = r * 2 + size;
   75                         if (c < i - size &&
   76                                         cmp_func(base + c, base + c + size) < 0)
   77                                 c += size;
   78                         if (cmp_func(base + r, base + c) >= 0)
   79                                 break;
   80                         swap_func(base + r, base + c, size);
   81                 }
   82         }
   83 }
   84 
   85 EXPORT_SYMBOL(sort);
   86 
   87 #if 0
   88 /* a simple boot-time regression test */
   89 
   90 int cmpint(const void *a, const void *b)
   91 {
   92         return *(int *)a - *(int *)b;
   93 }
   94 
   95 static int sort_test(void)
   96 {
   97         int *a, i, r = 1;
   98 
   99         a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
  100         BUG_ON(!a);
  101 
  102         printk("testing sort()\n");
  103 
  104         for (i = 0; i < 1000; i++) {
  105                 r = (r * 725861) % 6599;
  106                 a[i] = r;
  107         }
  108 
  109         sort(a, 1000, sizeof(int), cmpint, NULL);
  110 
  111         for (i = 0; i < 999; i++)
  112                 if (a[i] > a[i+1]) {
  113                         printk("sort() failed!\n");
  114                         break;
  115                 }
  116 
  117         kfree(a);
  118 
  119         return 0;
  120 }
  121 
  122 module_init(sort_test);
  123 #endif

Cache object: 34322f3f51c8dfa981e589d3f3c527d4

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/lib/sort.c

FreeBSD/Linux Kernel Cross Reference
sys/lib/sort.c