Messages in this thread | | | From | Andreas Gruenbacher <> | Subject | Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort() | Date | Sun, 27 Feb 2005 22:53:23 +0100 |
| |
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 <agruen@suse.de> SUSE Labs, SUSE LINUX PRODUCTS GMBH /* * A fast, small, non-recursive O(nlog n) sort for the Linux kernel * * Jan 23 2005 Matt Mackall <mpm@selenic.com> */
#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; }
| |