New alpm_list_join function

This O(1) function joins 2 lists.

Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
Signed-off-by: Dan McGee <dan@archlinux.org>

2 files changed, 34 insertions, 0 deletions

diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c
index e854cf63..69cd3479 100644
--- a/lib/libalpm/alpm_list.c
+++ b/lib/libalpm/alpm_list.c
@@ -185,6 +185,39 @@ alpm_list_t SYMEXPORT *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_
 }
 
 /**
+ * @brief Join two lists.
+ * The two lists must be independent. Do not free the original lists after
+ * calling this function, as this is not a copy operation. The list pointers
+ * passed in should be considered invalid after calling this function.
+ *
+ * @param first  the first list
+ * @param second the second list
+ *
+ * @return the resultant joined list
+ */
+alpm_list_t SYMEXPORT *alpm_list_join(alpm_list_t *first, alpm_list_t *second)
+{
+	alpm_list_t *tmp;
+
+	if (first == NULL) {
+		return second;
+	}
+	if (second == NULL) {
+		return first;
+	}
+	/* tmp is the last element of the first list */
+	tmp = first->prev;
+	/* link the first list to the second */
+	tmp->next = second;
+	/* link the second list to the first */
+	first->prev = second->prev;
+	/* set the back reference to the tail */
+	second->prev = tmp;
+
+	return(first);
+}
+
+/**
  * @brief Merge the two sorted sublists into one sorted list.
  *
  * @param left  the first list
diff --git a/lib/libalpm/alpm_list.h b/lib/libalpm/alpm_list.h
index a24aa8db..262d5e22 100644
--- a/lib/libalpm/alpm_list.h
+++ b/lib/libalpm/alpm_list.h
@@ -54,6 +54,7 @@ void alpm_list_free_inner(alpm_list_t *list, alpm_list_fn_free fn);
 /* item mutators */
 alpm_list_t *alpm_list_add(alpm_list_t *list, void *data);
 alpm_list_t *alpm_list_add_sorted(alpm_list_t *list, void *data, alpm_list_fn_cmp fn);
+alpm_list_t *alpm_list_join(alpm_list_t *first, alpm_list_t *second);
 alpm_list_t *alpm_list_mmerge(alpm_list_t *left, alpm_list_t *right, alpm_list_fn_cmp fn);
 alpm_list_t *alpm_list_msort(alpm_list_t *list, int n, alpm_list_fn_cmp fn);
 alpm_list_t *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_list_fn_cmp fn, void **data);