From: Omar Polo <op@omarpolo.com>
Subject: Re: avoid malloc for duplicate check in got_pathlist_insert()
To: Stefan Sperling <stsp@stsp.name>
Cc: gameoftrees@openbsd.org
Date: Wed, 18 May 2022 17:31:58 +0200

Stefan Sperling <stsp@stsp.name> wrote:
> Perform duplicate check using data which was passed in, instead of
> first copying to a newly allocated object which must be freed again
> if a duplicate is found.
> 
> ok?

sure, seems a good idea to delay the allocation.  ok op

> diff cb1e84170470cee5b0156bcc3828050bd7edfac9 644b4477d07cb6b03533823301257ae2655402d4
> blob - d0ec896bd7350a9da6048dc4c9ee1020412b2d56
> blob + f4b3d337163db35814aa20bf256f110b9febeb41
> --- lib/path.c
> +++ lib/path.c
> @@ -224,17 +224,11 @@ got_pathlist_insert(struct got_pathlist_entry **insert
>      struct got_pathlist_head *pathlist, const char *path, void *data)
>  {
>  	struct got_pathlist_entry *new, *pe;
> +	size_t path_len = strlen(path);
>  
>  	if (inserted)
>  		*inserted = NULL;
>  
> -	new = malloc(sizeof(*new));
> -	if (new == NULL)
> -		return got_error_from_errno("malloc");
> -	new->path = path;
> -	new->path_len = strlen(path);
> -	new->data = data;
> -
>  	/*
>  	 * Many callers will provide paths in a somewhat sorted order while
>  	 * constructing a path list from inputs such as tree objects or
> @@ -244,21 +238,24 @@ got_pathlist_insert(struct got_pathlist_entry **insert
>  	 */
>  	pe = TAILQ_LAST(pathlist, got_pathlist_head);
>  	while (pe) {
> -		int cmp = got_path_cmp(pe->path, new->path,
> -		    pe->path_len, new->path_len);
> -		if (cmp == 0) {
> -			free(new); /* duplicate */
> -			return NULL;
> -		} else if (cmp < 0) {
> -			TAILQ_INSERT_AFTER(pathlist, pe, new, entry);
> -			if (inserted)
> -				*inserted = new;
> -			return NULL;
> -		}
> +		int cmp = got_path_cmp(pe->path, path, pe->path_len, path_len);
> +		if (cmp == 0)
> +			return NULL;  /* duplicate */
> +		else if (cmp < 0)
> +			break;
>  		pe = TAILQ_PREV(pe, got_pathlist_head, entry);
>  	}
>  
> -	TAILQ_INSERT_HEAD(pathlist, new, entry);
> +	new = malloc(sizeof(*new));
> +	if (new == NULL)
> +		return got_error_from_errno("malloc");
> +	new->path = path;
> +	new->path_len = path_len;
> +	new->data = data;
> +	if (pe)
> +		TAILQ_INSERT_AFTER(pathlist, pe, new, entry);
> +	else
> +		TAILQ_INSERT_HEAD(pathlist, new, entry);
>  	if (inserted)
>  		*inserted = new;
>  	return NULL;