Re: [PATCH 1/4] help.c::uniq: plug a leak
- From
Jeff King <peff@peff.net>
- Date
- May 6, 2012, 08:12 UTC
- Message-ID
- <20120506081213.GA27878@sigill.intra.peff.net>
- In-Reply-To
- <1336287330-7215-2-git-send-email-rctay89@gmail.com>
On Sun, May 06, 2012 at 02:55:27PM +0800, Tay Ray Chuan wrote:
Show 25 quoted lines
> static void uniq(struct cmdnames *cmds)
> {
> - int i, j;
> + int i, j, c = 0;
>
> if (!cmds->cnt)
> return;
>
> for (i = j = 1; i < cmds->cnt; i++)
> - if (strcmp(cmds->names[i]->name, cmds->names[i-1]->name))
> + if (strcmp(cmds->names[i]->name, cmds->names[i-1]->name)) {
> +
> + /* The i-1 entry was the cth duplicate
> + * Guarantees c=0
> + */
> + for (; c >= 1; c--)
> + free(cmds->names[i - c]);
> +
> cmds->names[j++] = cmds->names[i];
> + } else {
> + c++;
> + }
>
> cmds->cnt = j;
> }Freeing the strings at the end of each run of duplicates is confusing to read. And your implementation is buggy: if there are duplicates at the very end of the list, you would never free them (you would need to check 'c' again at the end of the loop).
I think you avoided freeing as you go because that invalidates the i-1 element that we use in the comparison. However, we can observe that the j-1 element can serve the same purpose, as it is either:
1. Exactly i-1, when the loop begins (and until we see a duplicate).
2. The same pointer that was stored at i-1 (if it was not a duplicate,
and we just copied it into place). 3. A pointer to an equivalent string (i.e., we rejected i-1 _because_
it was identical to j-1).So this shorter patch should be sufficient (though I didn't actually test it):
diff --git a/help.c b/help.c index 69d483d..d3868b3 100644 --- a/help.c +++ b/help.c @@ -43,9 +43,12 @@ static void uniq(struct cmdnames *cmds) if (!cmds->cnt) return; - for (i = j = 1; i < cmds->cnt; i++) - if (strcmp(cmds->names[i]->name, cmds->names[i-1]->name)) + for (i = j = 1; i < cmds->cnt; i++) { + if (!strcmp(cmds->names[i]->name, cmds->names[j-1]->name)) + free(cmds->names[i]); + else cmds->names[j++] = cmds->names[i]; + } cmds->cnt = j; }