httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dean Gaudet <dgau...@arctic.org>
Subject Re: [PATCH] DoS fix
Date Sun, 09 Aug 1998 02:56:16 GMT


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 ;) 

> 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.

Dean


Mime
View raw message