[MPlayer-cvslog] CVS: main/libmpdemux aviheader.c,1.63,1.64

[Reimar Döffinger]

Hi,
> On Saturday 01 January 2005 09:39, D Richard Felker III wrote:
> > On Sat, Jan 01, 2005 at 01:16:55AM -0500, D Richard Felker III wrote:
> > > On Fri, Dec 31, 2004 at 05:02:50PM +0100, Reimar Döffinger CVS wrote:
> > > > CVS change done by Reimar Döffinger CVS
> > > >
> > > > Update of /cvsroot/mplayer/main/libmpdemux
> > > > In directory mail:/var2/tmp/cvs-serv30117/libmpdemux
> > > >
> > > > Modified Files:
> > > >  aviheader.c
> > > > Log Message:
> > > > fix quicksort to avoid stack overflow and extreme runtimes
> > > >
> > > >
> > > > Index: aviheader.c
> > > > ===================================================================
> > > > RCS file: /cvsroot/mplayer/main/libmpdemux/aviheader.c,v
> > > > retrieving revision 1.63
> > > > retrieving revision 1.64
> > > > diff -u -r1.63 -r1.64
> > > > --- aviheader.c 20 Oct 2004 02:13:33 -0000 1.63
> > > > +++ aviheader.c 31 Dec 2004 16:02:47 -0000 1.64
> > > > @@ -44,15 +44,25 @@
> > > >      return 0;
> > > >  }
> > > >
> > > > -/*
> > > > +/**
> > > >   * Simple quicksort for AVIINDEXENTRYs
> > > > + * To avoid too deep recursion, the bigger part is handled
> > > > iteratively, + * thus limiting recursion to log2(n) levels.
> > > > + * The pivot element is randomized to "even out" otherwise extreme
> > > > cases. */
> > > >  static void avi_idx_quicksort(AVIINDEXENTRY *idx, int from, int to)
> > > >  {
> > > >      AVIINDEXENTRY temp;
> > > > -    int lo = to;
> > > > -    int hi = from;
> > > > -    off_t pivot_ofs = AVI_IDX_OFFSET(&idx[(from + to) / 2]);
> > > > +    int lo;
> > > > +    int hi;
> > > > +    off_t pivot_ofs;
> > > > +    int pivot_idx;
> > > > +  while (from < to) {
> > > > +    pivot_idx = from;
> > > > +    pivot_idx += rand() % (to - from + 1);
> > >
> > > imnsho using rand() is forbidden. it corrupts the state of the caller.
> >
> > not to mention, it also makes debugging hell by making the program
> > non-deterministic.
> 
> iam a little curious why libc qsort() isnt simply used?

This is an alternative I asked about when posting the patch. What speaks
against it from my view is:
1) I don't know if all libc on strange systems implement it.
2) There is no specification whatsoever of how this sorting algorithm
should behave - e.g. if it is a stable sort. I don't know if this is
relevant in this case, but it will lead into debugging hell as well IMHO...
3) That it has to use callbacks for comparison puts limits on
performance, although the implementation (usually?) is much better I
have to admit.

The bugreport (#86) contains a patch that does it this way, feel free to
apply it if you really think it is better.

Greetings,
Reimar Döffinger