From cbb053a26a17b074b351be46bb26573863a82062 Mon Sep 17 00:00:00 2001 From: "Eric S. Raymond" Date: Fri, 12 Sep 2003 03:48:23 +0000 Subject: [PATCH] Compact for faster qsort. --- report.c | 31 +++++++++++++++++++------------ 1 file changed, 19 insertions(+), 12 deletions(-) diff --git a/report.c b/report.c index ba177a5..d614b71 100644 --- a/report.c +++ b/report.c @@ -283,7 +283,7 @@ static int sortmatch(const void *a, const void *b) void emit_report(struct sorthash_t *obarray, int hashcount) /* report our results */ { - struct match_t *hitlist, *match; + struct match_t *hitlist, *match, *copy; int mergecount; hitlist = reduce_matches(obarray, &hashcount); @@ -292,20 +292,27 @@ void emit_report(struct sorthash_t *obarray, int hashcount) report_time("%d range groups after merging", mergecount); report_time("Reduction done"); - qsort(hitlist, hashcount, sizeof(struct match_t), sortmatch); - for (match = hitlist; match < hitlist + hashcount; match++) - if (match->nmatches) - { - int i; + /* + * A little extra effort so we can generate a sirted report. + * Compact the match list in order to cut the n log n qsort time + */ + for (copy = match = hitlist; match < hitlist + hashcount; match++) + if (match->nmatches && copy < match) + *copy++ = *match; + qsort(hitlist, mergecount, sizeof(struct match_t), sortmatch); - for (i=0; i < match->nmatches; i++) - { - struct sorthash_t *rp = match->matches+i; + for (match = hitlist; match < hitlist + mergecount; match++) + { + int i; - printf("%s:%d:%d\n", rp->file, rp->hash.start, rp->hash.end); - } - printf("%%%%\n"); + for (i=0; i < match->nmatches; i++) + { + struct sorthash_t *rp = match->matches+i; + + printf("%s:%d:%d\n", rp->file, rp->hash.start, rp->hash.end); } + printf("%%%%\n"); + } /* free(hitlist); */ } -- 2.43.0