[pacman-dev] [PATCH] Improved alpm_list_mmerge() performance (fixed coding style)

[Dan McGee]

On Wed, Aug 24, 2011 at 11:01 AM, Diogo Sousa <diogogsousa at gmail.com> wrote:
> Improved alpm_list_mmerge() performance by removing an extra
> pass to obtain the tail node.
>
> This was actually suggested by a TODO comment.
>
> I hope the coding style is ok this time :)
>
> Thanks
>
> Signed-off-by: Diogo Sousa <diogogsousa at gmail.com>
> ---

Thanks! Note that if you put supplementary comments below the '---'
like this, they won't end up in git but are helpful for things like
your coding style comment. I killed that from the git commit message
since it doesn't add anything there.

>  lib/libalpm/alpm_list.c |   25 +++++++++++++++----------
>  1 files changed, 15 insertions(+), 10 deletions(-)
>
> diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c
> index 83b9824..0ab9356 100644
> --- a/lib/libalpm/alpm_list.c
> +++ b/lib/libalpm/alpm_list.c
> @@ -206,12 +206,18 @@ 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)
> +       if(left == NULL) {
>                return right;
> -       if(right == NULL)
> +       }
> +       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;
> @@ -242,19 +248,18 @@ 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;
>        }
> -
> -       /* Find our tail pointer
> -        * TODO maintain this in the algorithm itself */
> -       lp = newlist;
> -       while(lp && lp->next) {
> -               lp = lp->next;
> +       else {
> +               tail_ptr = lp;
>        }
> -       newlist->prev = lp;
> +
> +       newlist->prev = tail_ptr;
>
>        return newlist;
>  }
> --
> 1.7.6
>
>
>