[PATCH 1/2] Ensure qsort recursion depth is bounded

[Corinna Vinschen]

On Mar 14 17:54, Håkan Lindqvist wrote:
> > -----Original Message-----
> > From: Corinna Vinschen <vinschen@redhat.com>
> > Sent: den 13 mars 2018 13:53
> > To: newlib@sourceware.org
> > Cc: Håkan Lindqvist <hakan.lindqvist@enea.com>
> > Subject: Re: [PATCH 1/2] Ensure qsort recursion depth is bounded
> > 
> > On Mar 12 15:44, Håkan Lindqvist wrote:
> > > From 9d2f1fc59b8338f54c13dba4dac01d8751ceb8df Mon Sep 17 00:00:00
> > 2001
> > > From: Hakan Lindqvist <hakan.lindqvist@enea.com>
> > > Date: Mon, 12 Mar 2018 13:51:07 +0100
> > > Subject: [PATCH 1/2] Ensure qsort recursion depth is bounded
> > >
> > > The qsort algorithm splits the input array in three parts. The left
> > > and right parts may need further sorting. One of them is sorted by
> > > recursion, the other by iteration. This update ensures that it is the
> > > smaller part that is chosen for recursion.
> > >
> > > By choosing the smaller part, each recursion level will handle less
> > > than half the array of the previous recursion level. Hence the
> > > recursion depth is bounded to be less than log2(n) i.e. 1 level per
> > > significant bit in the array size n.
> > >
> > > The update also includes code comments explaining the algorithm.
> > 
> > The patch looks good at first glance.  Would you mind to outline how you
> > tested it?
> > 
> 
> I wrote a test program, It mostly tests sorting random data, but also specific patterns. I'll include it below. 
> It's not "production quality"; there is lots of stuff from when I was testing different things. Sorry about that.
> 
> You can use command line arguments to select different patterns. Mostly random patterns, but also special pattern using negative -r values.
> 
> The program contains ifdeffed stuff. Some of it is for timing measurements with facilities from the OS we make. Other parts are some measurement probe stuff another version of qsort that I used to verify the recursion depth, and for when I was experimenting with other another patch.

Patchset pushed.


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/newlib/attachments/20180316/cc7f1119/attachment.sig>