summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorXavier Chantry <shiningxc@gmail.com>2009-10-11 02:38:33 +0200
committerDan McGee <dan@archlinux.org>2009-10-11 22:28:10 +0200
commit3dc87851cc5990d358cf985d8e79dffeb2d91a21 (patch)
tree415ac62ab7700fdee800503e3bc1c6bfbfb81f0e /lib
parent14ab02e289668e30d33c473e00fc43e5dc457644 (diff)
downloadpacman-3dc87851cc5990d358cf985d8e79dffeb2d91a21.tar.gz
pacman-3dc87851cc5990d358cf985d8e79dffeb2d91a21.tar.xz
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')
-rw-r--r--lib/libalpm/alpm_list.c85
-rw-r--r--lib/libalpm/alpm_list.h2
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
}