summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAaron Griffin <aaron@archlinux.org>2007-01-11 17:44:39 +0000
committerAaron Griffin <aaron@archlinux.org>2007-01-11 17:44:39 +0000
commit2a457c531978dc59b38b4bdbcc22dc3d8bdecbb6 (patch)
treea069680ce28623ee96ed030924e41471cc9f292d
parent2ae56f4bc9cf3b155f009de601a8aa23a407ce4e (diff)
downloadpacman-2a457c531978dc59b38b4bdbcc22dc3d8bdecbb6.tar.xz
* Jürgen Hötzel <juergen@hoetzel.info>
_alpm_db_load_pkgcache: use mergesort to improve performance
-rw-r--r--lib/libalpm/cache.c5
-rw-r--r--lib/libalpm/list.c82
-rw-r--r--lib/libalpm/list.h3
3 files changed, 87 insertions, 3 deletions
diff --git a/lib/libalpm/cache.c b/lib/libalpm/cache.c
index ccba3bd6..6aa517cf 100644
--- a/lib/libalpm/cache.c
+++ b/lib/libalpm/cache.c
@@ -44,6 +44,7 @@
int _alpm_db_load_pkgcache(pmdb_t *db, unsigned char infolevel)
{
pmpkg_t *info;
+ int count = 0;
/* The group cache needs INFRQ_DESC as well */
/*unsigned char infolevel = INFRQ_DEPENDS | INFRQ_DESC;*/
@@ -61,9 +62,11 @@ int _alpm_db_load_pkgcache(pmdb_t *db, unsigned char infolevel)
info->origin = PKG_FROM_CACHE;
info->data = db;
/* add to the collection */
- db->pkgcache = _alpm_list_add_sorted(db->pkgcache, info, _alpm_pkg_cmp);
+ db->pkgcache = _alpm_list_add(db->pkgcache, info);
+ count++;
}
+ db->pkgcache = _alpm_list_msort(db->pkgcache, count, _alpm_pkg_cmp);
return(0);
}
diff --git a/lib/libalpm/list.c b/lib/libalpm/list.c
index 47c31990..61a87113 100644
--- a/lib/libalpm/list.c
+++ b/lib/libalpm/list.c
@@ -31,7 +31,7 @@
pmlist_t *_alpm_list_new()
{
pmlist_t *list = NULL;
-
+
list = (pmlist_t *)malloc(sizeof(pmlist_t));
if(list == NULL) {
return(NULL);
@@ -134,6 +134,84 @@ pmlist_t *_alpm_list_add_sorted(pmlist_t *list, void *data, _alpm_fn_cmp fn)
return(list);
}
+/* return nth element from list (starting with 0) */
+pmlist_t* _alpm_list_nth(pmlist_t *list, int n) {
+ while (n--)
+ list = list->next;
+ return list;
+}
+
+/* merge the two sorted sublists into one sorted list */
+pmlist_t* _alpm_list_mmerge(pmlist_t *left, pmlist_t *right, _alpm_fn_cmp fn) {
+ pmlist_t *newlist;
+ pmlist_t *lp;
+
+ if (left == NULL)
+ return right;
+ if (right == NULL)
+ return left;
+
+ if (fn(left->data, right->data) <= 0) {
+ newlist = left;
+ left = left->next;
+ }
+ else {
+ newlist = right;
+ right = right->next;
+ }
+ newlist->prev = NULL;
+ newlist->next = NULL;
+ newlist->last = NULL;
+ lp = newlist;
+
+ while ((left != NULL) && (right != NULL)) {
+ if (fn(left->data, right->data) <= 0) {
+ lp->next = left;
+ left->prev = lp;
+ left = left->next;
+ }
+ else {
+ lp->next = right;
+ right->prev = lp;
+ right = right->next;
+ }
+ lp = lp->next;
+ lp->next = NULL;
+ newlist->last = lp;
+ }
+ if (left != NULL) {
+ lp->next = left;
+ left->prev = lp;
+ newlist->last = left->last;
+ }
+ else if (right != NULL) {
+ lp->next = right;
+ right->prev = lp;
+ newlist->last = right->last;
+ }
+ return newlist;
+}
+
+/* sort an list of size n using mergesort algorithm */
+pmlist_t* _alpm_list_msort(pmlist_t *list, int len, _alpm_fn_cmp fn) {
+ if (len > 1 ) {
+ pmlist_t *left = list;
+ pmlist_t *lastleft = _alpm_list_nth(list, len/2 - 1);
+ pmlist_t *right = lastleft->next;
+ /* update rights last element, to previous last element*/
+ right->last = left->last;
+ /* update lefts last element */
+ left->last = lastleft;
+ /* terminate first list */
+ lastleft->next = NULL;
+
+ left = _alpm_list_msort(left, len/2, fn);
+ right = _alpm_list_msort(right, len - (len/2), fn);
+ list = _alpm_list_mmerge(left, right, fn);
+ }
+ return list;
+}
+
/* Remove an item in a list. Use the given comparaison function to find the
* item.
* If the item is found, 'data' is pointing to the removed element.
@@ -210,7 +288,7 @@ int _alpm_list_is_in(void *needle, pmlist_t *haystack)
}
/* Test for existence of a string in a pmlist_t
- */
+*/
int _alpm_list_is_strin(char *needle, pmlist_t *haystack)
{
pmlist_t *lp;
diff --git a/lib/libalpm/list.h b/lib/libalpm/list.h
index 3fdc01ad..a065b01e 100644
--- a/lib/libalpm/list.h
+++ b/lib/libalpm/list.h
@@ -43,6 +43,9 @@ pmlist_t *_alpm_list_new(void);
void _alpm_list_free(pmlist_t *list, _alpm_fn_free fn);
pmlist_t *_alpm_list_add(pmlist_t *list, void *data);
pmlist_t *_alpm_list_add_sorted(pmlist_t *list, void *data, _alpm_fn_cmp fn);
+pmlist_t* _alpm_list_mmerge(pmlist_t *left, pmlist_t *right, _alpm_fn_cmp fn);
+pmlist_t* _alpm_list_msort(pmlist_t *list, int len, _alpm_fn_cmp fn);
+pmlist_t* _alpm_list_nth(pmlist_t *list, int n);
pmlist_t *_alpm_list_remove(pmlist_t *haystack, void *needle, _alpm_fn_cmp fn, void **data);
int _alpm_list_count(const pmlist_t *list);
int _alpm_list_is_in(void *needle, pmlist_t *haystack);