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