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