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>

1 files changed, 2 insertions, 0 deletions

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
 }