[pacman-dev] [PATCH] Improved alpm_list_mmerge() performance

[Diogo Sousa]

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 <diogogsousa at gmail.com>
---
 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