On Sunday 27 February 2005 22:25, Matt Mackall wrote:
> On Sun, Feb 27, 2005 at 02:17:51PM +0100, Andreas Gruenbacher wrote:
> > Matt,
> >
> > On Monday 31 January 2005 08:34, Matt Mackall wrote:
> > > This patch adds a generic array sorting library routine. This is meant
> > > to replace qsort, which has two problem areas for kernel use.
> >
> > the sort function is broken. When sorting the integer array {1, 2, 3, 4,
> > 5}, I'm getting {2, 3, 4, 5, 1} as a result. Can you please have a look?
>
> Which kernel? There was an off-by-one for odd array sizes in the
> original posted version that was quickly spotted:
>
> http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2
>.6.11-rc4-mm1/broken-out/sort-fix.patch
Okay, I didn't notice the off-by-one fix. It's still broken though; see the
attached user-space test.
> I've since tested all sizes 1 - 1000 with 100 random arrays each, so
> I'm fairly confident it's now fixed.
Famous last words ;)
Thanks,
--
Andreas Gruenbacher <[EMAIL PROTECTED]>
SUSE Labs, SUSE LINUX PRODUCTS GMBH
/*
* A fast, small, non-recursive O(nlog n) sort for the Linux kernel
*
* Jan 23 2005 Matt Mackall <[EMAIL PROTECTED]>
*/
#include <stdlib.h>
#include <stdio.h>
void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}
/*
* sort - sort an array of elements
* @base: pointer to data to sort
* @num: number of elements
* @size: size of each element
* @cmp: pointer to comparison function
* @swap: pointer to swap function or NULL
*
* This function does a heapsort on the given array. You may provide a
* swap function optimized to your element type.
*
* Sorting time is O(n log n) both on average and worst-case. While
* qsort is about 20% faster on average, it suffers from exploitable
* O(n*n) worst-case behavior and extra memory requirements that make
* it less suitable for kernel use.
*/
void sort(void *base, size_t num, size_t size,
int (*cmp)(const void *, const void *),
void (*swap)(void *, void *, int size))
{
/* pre-scale counters for performance */
int i = (num/2) * size, n = num * size, c, r;
if (!swap)
swap = generic_swap;
/* heapify */
for ( ; i >= 0; i -= size) {
for (r = i; r * 2 < n; r = c) {
c = r * 2;
if (c < n - size && cmp(base + c, base + c + size) < 0)
c += size;
if (cmp(base + r, base + c) >= 0)
break;
swap(base + r, base + c, size);
}
}
/* sort */
for (i = n - size; i >= 0; i -= size) {
swap(base, base + i, size);
for (r = 0; r * 2 < i; r = c) {
c = r * 2;
if (c < i - size && cmp(base + c, base + c + size) < 0)
c += size;
if (cmp(base + r, base + c) >= 0)
break;
swap(base + r, base + c, size);
}
}
}
int cmp(const int *a, const int *b)
{
return b - a;
}
int main(void)
{
int a[] = { 1, 2, 3, 4, 5 };
size_t n;
for (n = 0; n < sizeof(a)/sizeof(a[0]); n++)
printf("%d ", a[n]);
puts("");
sort(a, sizeof(a)/sizeof(a[0]), sizeof(a[0]),
(int (*)(const void *, const void *))cmp, NULL);
for (n = 0; n < sizeof(a)/sizeof(a[0]); n++)
printf("%d ", a[n]);
puts("");
return 0;
}
