summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNagy Gabor <ngaba@bibl.u-szeged.hu>2007-11-20 09:11:40 +0100
committerDan McGee <dan@archlinux.org>2007-11-20 23:31:40 -0600
commit4696ad6cad9c659728e9e061689728fc0417ad73 (patch)
treed196162c7528243711886558e7c18a32009e697d
parent967a78f5e476030c2d13104a7dadc5ce4daf5882 (diff)
downloadpacman-4696ad6cad9c659728e9e061689728fc0417ad73.tar.xz
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>
-rw-r--r--lib/libalpm/alpm_list.c33
-rw-r--r--lib/libalpm/alpm_list.h1
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);