summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDiogo Sousa <diogogsousa@gmail.com>2011-08-24 17:01:11 +0100
committerDan McGee <dan@archlinux.org>2011-08-24 11:27:11 -0500
commit268d0bbcbed29b684af7478467bab4bdc2785636 (patch)
tree2aba63252b0c934b17f64e72b23d1ba11f671a11
parent30d978a966c1d2a619acc49f204e4da1e0010c83 (diff)
downloadpacman-268d0bbcbed29b684af7478467bab4bdc2785636.tar.xz
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 <diogogsousa@gmail.com> Signed-off-by: Dan McGee <dan@archlinux.org>
-rw-r--r--lib/libalpm/alpm_list.c25
1 files changed, 15 insertions, 10 deletions
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;
}