sort.c 2.5 KB

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