From 4696ad6cad9c659728e9e061689728fc0417ad73 Mon Sep 17 00:00:00 2001 From: Nagy Gabor Date: Tue, 20 Nov 2007 09:11:40 +0100 Subject: New alpm_list_join function This O(1) function joins 2 lists. Signed-off-by: Nagy Gabor Signed-off-by: Dan McGee --- lib/libalpm/alpm_list.c | 33 +++++++++++++++++++++++++++++++++ lib/libalpm/alpm_list.h | 1 + 2 files changed, 34 insertions(+) (limited to 'lib/libalpm') 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 @@ -184,6 +184,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. * 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); -- cgit v1.2.3-24-g4f1b