diff options
author | Aaron Griffin <aaron@archlinux.org> | 2007-01-11 17:44:39 +0000 |
---|---|---|
committer | Aaron Griffin <aaron@archlinux.org> | 2007-01-11 17:44:39 +0000 |
commit | 2a457c531978dc59b38b4bdbcc22dc3d8bdecbb6 (patch) | |
tree | a069680ce28623ee96ed030924e41471cc9f292d /lib | |
parent | 2ae56f4bc9cf3b155f009de601a8aa23a407ce4e (diff) |
* Jürgen Hötzel <juergen@hoetzel.info>
_alpm_db_load_pkgcache: use mergesort to improve performance
Diffstat (limited to 'lib')
-rw-r--r-- | lib/libalpm/cache.c | 5 | ||||
-rw-r--r-- | lib/libalpm/list.c | 82 | ||||
-rw-r--r-- | lib/libalpm/list.h | 3 |
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); |