diff options
author | Xavier Chantry <shiningxc@gmail.com> | 2009-10-11 02:38:33 +0200 |
---|---|---|
committer | Dan McGee <dan@archlinux.org> | 2009-10-11 15:28:10 -0500 |
commit | 3dc87851cc5990d358cf985d8e79dffeb2d91a21 (patch) | |
tree | 415ac62ab7700fdee800503e3bc1c6bfbfb81f0e /lib/libalpm | |
parent | 14ab02e289668e30d33c473e00fc43e5dc457644 (diff) |
alpm_list : add new alpm_list_diff_sorted function
This is more efficient than alpm_list_diff since it assumes the two lists
are sorted. And also we get the two sides of the diff.
Even sorting should more efficient than the current list_diff. Sorting the
two lists should be O(n*log(n)+m*log(m)) while the current list_diff is
O(n*m). So I also reimplemented list_diff using list_diff_sorted.
Signed-off-by: Xavier Chantry <shiningxc@gmail.com>
Signed-off-by: Dan McGee <dan@archlinux.org>
Diffstat (limited to 'lib/libalpm')
-rw-r--r-- | lib/libalpm/alpm_list.c | 85 | ||||
-rw-r--r-- | lib/libalpm/alpm_list.h | 2 |
2 files changed, 70 insertions, 17 deletions
diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index 127f72ac..17bdfdf4 100644 --- a/lib/libalpm/alpm_list.c +++ b/lib/libalpm/alpm_list.c @@ -644,11 +644,65 @@ char SYMEXPORT *alpm_list_find_str(const alpm_list_t *haystack, } /** - * @brief Find the items in list `lhs` that are not present in list `rhs`. + * @brief Find the differences between list `left` and list `right` + * + * The two lists must be sorted. Items only in list `left` are added to the + * `onlyleft` list. Items only in list `right` are added to the `onlyright` + * list. * - * Entries are not duplicated. Operation is O(m*n). The first list is stepped - * through one node at a time, and for each node in the first list, each node - * in the second list is compared to it. + * @param left the first list + * @param right the second list + * @param fn the comparison function + * @param onlyleft pointer to the first result list + * @param onlyright pointer to the second result list + * + */ +void SYMEXPORT alpm_list_diff_sorted(alpm_list_t *left, + alpm_list_t *right, alpm_list_fn_cmp fn, + alpm_list_t **onlyleft, alpm_list_t **onlyright) +{ + alpm_list_t *l = left; + alpm_list_t *r = right; + + if(!onlyleft && !onlyright) { + return; + } + + while (l != NULL && r != NULL) { + int cmp = fn(l->data, r->data); + if(cmp < 0) { + if(onlyleft) { + *onlyleft = alpm_list_add(*onlyleft, l->data); + } + l = l->next; + } + else if(cmp > 0) { + if(onlyright) { + *onlyright = alpm_list_add(*onlyright, r->data); + } + r = r->next; + } else { + l = l->next; + r = r->next; + } + } + while (l != NULL) { + if(onlyleft) { + *onlyleft = alpm_list_add(*onlyleft, l->data); + } + l = l->next; + } + while (r != NULL) { + if(onlyright) { + *onlyright = alpm_list_add(*onlyright, r->data); + } + r = r->next; + } +} + + +/** + * @brief Find the items in list `lhs` that are not present in list `rhs`. * * @param lhs the first list * @param rhs the second list @@ -659,21 +713,18 @@ char SYMEXPORT *alpm_list_find_str(const alpm_list_t *haystack, alpm_list_t SYMEXPORT *alpm_list_diff(const alpm_list_t *lhs, const alpm_list_t *rhs, alpm_list_fn_cmp fn) { - const alpm_list_t *i, *j; + alpm_list_t *left, *right; alpm_list_t *ret = NULL; - for(i = lhs; i; i = i->next) { - int found = 0; - for(j = rhs; j; j = j->next) { - if(fn(i->data, j->data) == 0) { - found = 1; - break; - } - } - if(!found) { - ret = alpm_list_add(ret, i->data); - } - } + left = alpm_list_copy(lhs); + left = alpm_list_msort(left, alpm_list_count(left), fn); + right = alpm_list_copy(rhs); + right = alpm_list_msort(right, alpm_list_count(right), fn); + + alpm_list_diff_sorted(left, right, fn, &ret, NULL); + + alpm_list_free(left); + alpm_list_free(right); return(ret); } diff --git a/lib/libalpm/alpm_list.h b/lib/libalpm/alpm_list.h index f079ecfd..48e91173 100644 --- a/lib/libalpm/alpm_list.h +++ b/lib/libalpm/alpm_list.h @@ -78,6 +78,8 @@ void *alpm_list_find(const alpm_list_t *haystack, const void *needle, alpm_list_ void *alpm_list_find_ptr(const alpm_list_t *haystack, const void *needle); char *alpm_list_find_str(const alpm_list_t *haystack, const char *needle); alpm_list_t *alpm_list_diff(const alpm_list_t *lhs, const alpm_list_t *rhs, alpm_list_fn_cmp fn); +void alpm_list_diff_sorted(alpm_list_t *left, alpm_list_t *right, + alpm_list_fn_cmp fn, alpm_list_t **onlyleft, alpm_list_t **onlyright); #ifdef __cplusplus } |