Ping?
On Mon, Nov 16, 2015 at 10:09:29AM -0800, Serguey Parkhomovsky wrote:
> Hi Philip,
>
> Thanks for the detailed explanation on comparison functions for qsort. I
> have looked through your changes, and have only found one issue:
>
> > 2) totalcmp(A,B) and totalcmp(B,A) both return <0 if both A and B have
> > name==0 and cycleno!=0, and they both return >0 if both A and B have
> > naem==0 and cycleno==0, violating the consistency requirement.
>
> The logic is still not quite right with totalcmp; it is still
> inconsistent where both A and B have:
> * name == 0 && cycleno == 0 (both return -1)
> * name != 0 && cycleno == 0 (both return -1)
> * name != 0 && cycleno != 0 (both return -1)
>
> As well, if name == 0 && cycleno != 0, the code will drop through and
> there will be a null pointer dereference:
>
> if ( *(np1 -> name) != '_' && *(np2 -> name) == '_' )
> return -1;
> if ( *(np1 -> name) == '_' && *(np2 -> name) != '_' )
> return 1;
>
> What do you think of the following diff? I've put some of the boolean logic
> into variables to enhance readability.
>
> Index: arcs.c
> ===================================================================
> RCS file: /cvs/src/usr.bin/gprof/arcs.c,v
> retrieving revision 1.13
> diff -u -p -u -r1.13 arcs.c
> --- arcs.c 20 Aug 2015 22:32:41 -0000 1.13
> +++ arcs.c 16 Nov 2015 17:41:55 -0000
> @@ -95,9 +95,14 @@ addarc(nltype *parentp, nltype *childp,
> nltype **topsortnlp;
>
> int
> -topcmp(nltype **npp1, nltype **npp2)
> +topcmp(const void *v1, const void *v2)
> {
> - return (*npp1) -> toporder - (*npp2) -> toporder;
> + const nltype * const *npp1 = v1;
> + const nltype * const *npp2 = v2;
> +
> + if ((*npp1) -> toporder < (*npp2) -> toporder)
> + return -1;
> + return (*npp1) -> toporder > (*npp2) -> toporder;
> }
>
> nltype **
> Index: gprof.h
> ===================================================================
> RCS file: /cvs/src/usr.bin/gprof/gprof.h,v
> retrieving revision 1.14
> diff -u -p -u -r1.14 gprof.h
> --- gprof.h 19 Oct 2013 13:51:40 -0000 1.14
> +++ gprof.h 16 Nov 2015 17:41:55 -0000
> @@ -281,10 +281,10 @@ void sortchildren(nltype *);
> void sortmembers(nltype *);
> void sortparents(nltype *);
> void tally(struct rawarc *);
> -int timecmp(nltype **, nltype **);
> +int timecmp(const void *, const void *);
> void timepropagate(nltype *);
> -int topcmp(nltype **, nltype **);
> -int totalcmp(nltype **, nltype **);
> +int topcmp(const void *, const void *);
> +int totalcmp(const void *, const void *);
>
> #define LESSTHAN -1
> #define EQUALTO 0
> Index: printgprof.c
> ===================================================================
> RCS file: /cvs/src/usr.bin/gprof/printgprof.c,v
> retrieving revision 1.13
> diff -u -p -u -r1.13 printgprof.c
> --- printgprof.c 20 Aug 2015 22:32:41 -0000 1.13
> +++ printgprof.c 16 Nov 2015 17:41:55 -0000
> @@ -35,7 +35,7 @@
> #include "gprof.h"
> #include "pathnames.h"
>
> -int namecmp(nltype **, nltype **);
> +int namecmp(const void *, const void *);
>
> void
> printprof()
> @@ -66,21 +66,19 @@ printprof()
> }
>
> int
> -timecmp(nltype **npp1, nltype **npp2)
> +timecmp(const void *v1, const void *v2)
> {
> - double timediff;
> - long calldiff;
> + const nltype * const *npp1 = v1;
> + const nltype * const *npp2 = v2;
>
> - timediff = (*npp2) -> time - (*npp1) -> time;
> - if ( timediff > 0.0 )
> + if ((*npp2) -> time < (*npp1) -> time)
> + return -1;
> + if ((*npp2) -> time > (*npp1) -> time)
> return 1 ;
> - if ( timediff < 0.0 )
> + if ((*npp2) -> ncall < (*npp1) -> ncall)
> return -1;
> - calldiff = (*npp2) -> ncall - (*npp1) -> ncall;
> - if ( calldiff > 0 )
> + if ((*npp2) -> ncall > (*npp1) -> ncall)
> return 1;
> - if ( calldiff < 0 )
> - return -1;
> return( strcmp( (*npp1) -> name , (*npp2) -> name ) );
> }
>
> @@ -233,26 +231,37 @@ printgprof(nltype **timesortnlp)
> * all else being equal, sort by names.
> */
> int
> -totalcmp(nltype **npp1, nltype **npp2)
> +totalcmp(const void *v1, const void *v2)
> {
> - nltype *np1 = *npp1;
> - nltype *np2 = *npp2;
> - double diff;
> -
> - diff = ( np1 -> propself + np1 -> propchild )
> - - ( np2 -> propself + np2 -> propchild );
> - if ( diff < 0.0 )
> + const nltype *np1 = *(const nltype **)v1;
> + const nltype *np2 = *(const nltype **)v2;
> + double t1, t2;
> + int np1noname, np2noname, np1cyclehdr, np2cyclehdr;
> +
> + t1 = np1 -> propself + np1 -> propchild;
> + t2 = np2 -> propself + np2 -> propchild;
> + if ( t2 > t1 )
> return 1;
> - if ( diff > 0.0 )
> + if ( t2 < t1 )
> return -1;
> - if ( np1 -> name == 0 && np1 -> cycleno != 0 )
> +
> + np1noname = ( np1 -> name == 0 );
> + np2noname = ( np2 -> name == 0 );
> + np1cyclehdr = ( np1noname && np1 -> cycleno != 0 );
> + np2cyclehdr = ( np2noname && np2 -> cycleno != 0 );
> +
> + if ( np1cyclehdr && !np2cyclehdr )
> return -1;
> - if ( np2 -> name == 0 && np2 -> cycleno != 0 )
> + else if ( !np1cyclehdr && np2cyclehdr )
> return 1;
> - if ( np1 -> name == 0 )
> +
> + if ( np1noname && !np2noname )
> return -1;
> - if ( np2 -> name == 0 )
> + else if ( !np1noname && np2noname )
> return 1;
> + else if ( np1noname && np2noname )
> + return 0;
> +
> if ( *(np1 -> name) != '_' && *(np2 -> name) == '_' )
> return -1;
> if ( *(np1 -> name) == '_' && *(np2 -> name) != '_' )
> @@ -642,8 +651,11 @@ printblurb(const char *blurbname)
> }
>
> int
> -namecmp(nltype **npp1, nltype **npp2)
> +namecmp(const void *v1, const void *v2)
> {
> + const nltype * const *npp1 = v1;
> + const nltype * const *npp2 = v2;
> +
> return( strcmp( (*npp1) -> name , (*npp2) -> name ) );
> }
>
