Re: [PATCH 1/4] help.c::uniq: plug a leak

[Jeff King <peff@peff.net>]

On Sun, May 06, 2012 at 02:55:27PM +0800, Tay Ray Chuan wrote:

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