[pacman-dev] [PATCH] Improved alpm_list_mmerge() performance

[Dave Reisner]

On Wed, Aug 24, 2011 at 03:29:54PM +0100, Diogo Sousa wrote:
> Improved alpm_list_mmerge() performance by removing an extra
> final linear search of the tail node. This was actually
> suggested by a TODO comment.
> 
> Signed-off-by: Diogo Sousa <diogogsousa at gmail.com>

Hi Diogo,

Thanks for your contribution. We'd love to take your patch, but we'll
need you to adhere to our coding style, in particular:

- tab intendation
- key = value
- always brace control statements (i notice we don't do this correctly
  at the first of this particular function)

You can get a full style guide in the HACKING file at the base of the
repo. If you'd like to clean up the styling in the remainder of this
function, please do that in a separate patch (preferrably prior to this
one).

Thanks again,
dave

> ---
>  lib/libalpm/alpm_list.c |   18 ++++++++++--------
>  1 files changed, 10 insertions(+), 8 deletions(-)
> 
> diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c
> index 83b9824..d50dce1 100644
> --- a/lib/libalpm/alpm_list.c
> +++ b/lib/libalpm/alpm_list.c
> @@ -206,13 +206,17 @@ alpm_list_t SYMEXPORT *alpm_list_join(alpm_list_t *first, alpm_list_t *second)
>   */
>  alpm_list_t SYMEXPORT *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn)
>  {
> -	alpm_list_t *newlist, *lp;
> +	alpm_list_t *newlist, *lp, *tail_ptr, *left_tail_ptr, *right_tail_ptr;
>  
>  	if(left == NULL)
>  		return right;
>  	if(right == NULL)
>  		return left;
>  
> +        /* Save tail node pointers for future use */
> +	left_tail_ptr=left->prev;
> +	right_tail_ptr=right->prev;
> +
>  	if(fn(left->data, right->data) <= 0) {
>  		newlist = left;
>  		left = left->next;
> @@ -242,19 +246,17 @@ alpm_list_t SYMEXPORT *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, a
>  	if(left != NULL) {
>  		lp->next = left;
>  		left->prev = lp;
> +		tail_ptr=left_tail_ptr;
>  	}
>  	else if(right != NULL) {
>  		lp->next = right;
>  		right->prev = lp;
> +		tail_ptr=right_tail_ptr;
>  	}
> +	else
> +		tail_ptr=lp;
>  
> -	/* Find our tail pointer
> -	 * TODO maintain this in the algorithm itself */
> -	lp = newlist;
> -	while(lp && lp->next) {
> -		lp = lp->next;
> -	}
> -	newlist->prev = lp;
> +	newlist->prev = tail_ptr;
>  
>  	return newlist;
>  }
> -- 
> 1.7.6
> 
>