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 is more efficient than the current list_diff, so we might want to drop it and use only list_diff_sorted instead. Signed-off-by: Xavier Chantry <[email protected]> --- lib/libalpm/alpm_list.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++ lib/libalpm/alpm_list.h | 2 + 2 files changed, 51 insertions(+), 0 deletions(-) diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c index 127f72a..04a749f 100644 --- a/lib/libalpm/alpm_list.c +++ b/lib/libalpm/alpm_list.c @@ -644,6 +644,55 @@ char SYMEXPORT *alpm_list_find_str(const alpm_list_t *haystack, } /** + * @brief Find the items in list `left` that are not present in list `right` and vice-versa. + * + * 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. + * + * @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) { + *onlyleft = alpm_list_add(*onlyleft, l->data); + l = l->next; + } + else if(cmp > 0) { + *onlyright = alpm_list_add(*onlyright, r->data); + r = r->next; + } else { + l = l->next; + r = r->next; + } + } + while (l != NULL) { + *onlyleft = alpm_list_add(*onlyleft, l->data); + l = l->next; + } + while (r != NULL) { + *onlyright = alpm_list_add(*onlyright, r->data); + r = r->next; + } +} + + +/** * @brief Find the items in list `lhs` that are not present in list `rhs`. * * Entries are not duplicated. Operation is O(m*n). The first list is stepped diff --git a/lib/libalpm/alpm_list.h b/lib/libalpm/alpm_list.h index f079ecf..48e9117 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 } -- 1.6.4.4
