From 268d0bbcbed29b684af7478467bab4bdc2785636 Mon Sep 17 00:00:00 2001 From: Diogo Sousa Date: Wed, 24 Aug 2011 17:01:11 +0100 Subject: Improved alpm_list_mmerge() performance (fixed coding style) Improved alpm_list_mmerge() performance by removing an extra pass to obtain the tail node. This was actually suggested by a TODO comment. Signed-off-by: Diogo Sousa Signed-off-by: Dan McGee --- lib/libalpm/alpm_list.c | 25 +++++++++++++++---------- 1 file changed, 15 insertions(+), 10 deletions(-) (limited to 'lib/libalpm') diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index 83b9824c..0ab9356c 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; } -- cgit v1.2.3-70-g09d2