httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ben Laurie <>
Subject Re: [PATCH] DoS fix
Date Sun, 09 Aug 1998 11:56:46 GMT
Dean Gaudet wrote:
> On Sat, 8 Aug 1998, Ben Laurie wrote:
> > Dean Gaudet wrote:
> > > +/* Curse libc and the fact that it doesn't guarantee a stable sort.  We
> > > + * have to enforce stability ourselves by using the order field. -djg
> > > + */
> >
> > Err? a) You are allowed to return 0 when they are equal
> If you pass qsort something like (a,1), (a,2), (b,3) (where the first
> value is the key, the second is some arbitrary data) it's not guaranteed
> to return (a,1), (a,2), (b,3) to you... it could return (a,2), (a,1),
> (b,3) -- it doesn't guarantee stability.  A "stable" sort is a sort in
> which otherwise equal keys retain their original relative order in the
> output.
> qsort is not a stable sort in general (unlike heapsort), but it's like a
> trivial tweak to make it stable... and I'm just annoyed that it's not
> mandated as part of the standard ;)

Ah, OK. Are we required to preserve order?

> > and b) if you
> > really care, compare a->val to b->val (the address, not the content).
> If only that would work... unfortunately, the values are from an
> ap_palloc(), which could range all over memory... only when they fit
> within one chunk would this trick work.

Yeah, I was just trying to give _an_ ordering, not preserve the existing
ordering. I know from experience that qsort can go O(n^2) on equal
values if care isn't taken to avoid that (in the implementation), and
that was what I was attempting to cure.

In short, I'd forgotten what "stable sort" meant. :-)



Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|
and Technical Director|Email: |
A.L. Digital Ltd,     |Apache-SSL author
London, England.      |"Apache: TDG"


View raw message