summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorDan McGee <dan@archlinux.org>2011-12-31 20:25:53 -0600
committerDan McGee <dan@archlinux.org>2012-01-02 12:58:51 -0600
commit496f7b4f642af43beeafc1476294da56b433a587 (patch)
treec07ac1f4dc8a9959ed111f3b88d33306f91c545e /lib
parent566f5210ce23e1d869472c49ae87ab56cf577468 (diff)
downloadpacman-496f7b4f642af43beeafc1476294da56b433a587.tar.xz
alpm_list_msort: inline alpm_list_nth() call
This reduces the number of functions we call by log(n) in this function, and the inlined version is trivial and barely increases the size of the function. Signed-off-by: Dan McGee <dan@archlinux.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/libalpm/alpm_list.c21
1 files changed, 14 insertions, 7 deletions
diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c
index cad6d096..83ba9dca 100644
--- a/lib/libalpm/alpm_list.c
+++ b/lib/libalpm/alpm_list.c
@@ -204,7 +204,8 @@ alpm_list_t SYMEXPORT *alpm_list_join(alpm_list_t *first, alpm_list_t *second)
*
* @return the resultant list
*/
-alpm_list_t SYMEXPORT *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn)
+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, *tail_ptr, *left_tail_ptr, *right_tail_ptr;
@@ -273,17 +274,23 @@ alpm_list_t SYMEXPORT *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, a
*
* @return the resultant list
*/
-alpm_list_t SYMEXPORT *alpm_list_msort(alpm_list_t *list, size_t n, alpm_list_fn_cmp fn)
+alpm_list_t SYMEXPORT *alpm_list_msort(alpm_list_t *list, size_t n,
+ alpm_list_fn_cmp fn)
{
if(n > 1) {
- alpm_list_t *left = list;
- alpm_list_t *lastleft = alpm_list_nth(list, n/2 - 1);
- alpm_list_t *right = lastleft->next;
+ size_t half = n / 2;
+ size_t i = half - 1;
+ alpm_list_t *left = list, *lastleft = list, *right;
+
+ while(i--) {
+ lastleft = lastleft->next;
+ }
+ right = lastleft->next;
/* terminate first list */
lastleft->next = NULL;
- left = alpm_list_msort(left, n/2, fn);
- right = alpm_list_msort(right, n - (n/2), fn);
+ left = alpm_list_msort(left, half, fn);
+ right = alpm_list_msort(right, n - half, fn);
list = alpm_list_mmerge(left, right, fn);
}
return list;