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 <[email protected]> --- 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
