From 3dc87851cc5990d358cf985d8e79dffeb2d91a21 Mon Sep 17 00:00:00 2001 From: Xavier Chantry Date: Sun, 11 Oct 2009 02:38:33 +0200 Subject: 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 Signed-off-by: Dan McGee --- lib/libalpm/alpm_list.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'lib/libalpm/alpm_list.h') 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 } -- cgit v1.2.3-24-g4f1b