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