Re: Using qsort(3) in the kernel

[Johnny Billquist <bqt%softjar.se@localhost>]

Andrew Doran wrote:
> On Sun, Nov 16, 2008 at 03:38:24PM +0000, Matthias Scheler wrote:
>
> > On Sun, Nov 16, 2008 at 03:01:26PM +0000, Andrew Doran wrote:
> > > Module Name:    src
> > > Committed By:   ad
> > > Date:           Sun Nov 16 15:01:26 UTC 2008
> > >
> > > Modified Files:
> > >         src/sys/lib/libkern: Makefile libkern.h
> > > Added Files:
> > >         src/common/lib/libc/stdlib: qsort.c
> > > Removed Files:
> > >         src/lib/libc/stdlib: qsort.c
> > >
> > > Log Message:
> > > Make qsort() available in libkern.
> > Our implementation of qsort() uses recursion. That is IMHO a dangerous
> > thing to do in the kernel.
>
> Wow that is bad. I'll replace it with heapsort.
>
> Thanks for letting me know.

Well, quicksort is recursive by definition. So that should not have been 
a surprise for anyone.
However, it should use very little stack space for recursion, unless the 
implementation stinks.

But I think a heapsort is better to use in places like a kernel anyway.

        Johnny