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

On Wed, Aug 24, 2011 at 11:01 AM, Diogo Sousa 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 ---

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