summaryrefslogtreecommitdiffstats
path: root/lib/libalpm/list.c
diff options
context:
space:
mode:
authorAaron Griffin <aaron@archlinux.org>2007-01-11 18:44:39 +0100
committerAaron Griffin <aaron@archlinux.org>2007-01-11 18:44:39 +0100
commit2a457c531978dc59b38b4bdbcc22dc3d8bdecbb6 (patch)
treea069680ce28623ee96ed030924e41471cc9f292d /lib/libalpm/list.c
parent2ae56f4bc9cf3b155f009de601a8aa23a407ce4e (diff)
downloadpacman-2a457c531978dc59b38b4bdbcc22dc3d8bdecbb6.tar.gz
pacman-2a457c531978dc59b38b4bdbcc22dc3d8bdecbb6.tar.xz
* Jürgen Hötzel <juergen@hoetzel.info>
_alpm_db_load_pkgcache: use mergesort to improve performance
Diffstat (limited to 'lib/libalpm/list.c')
-rw-r--r--lib/libalpm/list.c82
1 files changed, 80 insertions, 2 deletions
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;