From c35fcafc261eb9c0f5aff1a608568b38ddc01f66 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Sun, 17 Mar 2013 15:11:48 +1030 Subject: [PATCH] list: list_append_list / list_prepend_list Operations for moving the entire contents of a list. Signed-off-by: Rusty Russell --- ccan/list/list.h | 62 +++++++++++++++++ ccan/list/test/run-prepend_list.c | 111 ++++++++++++++++++++++++++++++ 2 files changed, 173 insertions(+) create mode 100644 ccan/list/test/run-prepend_list.c diff --git a/ccan/list/list.h b/ccan/list/list.h index faad86f5..8e2f6df0 100644 --- a/ccan/list/list.h +++ b/ccan/list/list.h @@ -371,6 +371,68 @@ static inline const void *list_tail_(const struct list_head *h, size_t off) #define list_for_each_safe(h, i, nxt, member) \ list_for_each_safe_off(h, i, nxt, list_off_var_(i, member)) +/** + * list_append_list - empty one list onto the end of another. + * @to: the list to append into + * @from: the list to empty. + * + * This takes the entire contents of @from and moves it to the end of + * @to. After this @from will be empty. + * + * Example: + * struct list_head adopter; + * + * list_append_list(&adopter, &parent->children); + * assert(list_empty(&parent->children)); + * parent->num_children = 0; + */ +static inline void list_append_list(struct list_head *to, + struct list_head *from) +{ + struct list_node *from_tail = list_debug(from)->n.prev; + struct list_node *to_tail = list_debug(to)->n.prev; + + /* Sew in head and entire list. */ + to->n.prev = from_tail; + from_tail->next = &to->n; + to_tail->next = &from->n; + from->n.prev = to_tail; + + /* Now remove head. */ + list_del(&from->n); + list_head_init(from); +} + +/** + * list_prepend_list - empty one list into the start of another. + * @to: the list to prepend into + * @from: the list to empty. + * + * This takes the entire contents of @from and moves it to the start + * of @to. After this @from will be empty. + * + * Example: + * list_prepend_list(&adopter, &parent->children); + * assert(list_empty(&parent->children)); + * parent->num_children = 0; + */ +static inline void list_prepend_list(struct list_head *to, + struct list_head *from) +{ + struct list_node *from_tail = list_debug(from)->n.prev; + struct list_node *to_head = list_debug(to)->n.next; + + /* Sew in head and entire list. */ + to->n.next = &from->n; + from->n.prev = &to->n; + to_head->prev = from_tail; + from_tail->next = to_head; + + /* Now remove head. */ + list_del(&from->n); + list_head_init(from); +} + /** * list_for_each_off - iterate through a list of memory regions. * @h: the list_head diff --git a/ccan/list/test/run-prepend_list.c b/ccan/list/test/run-prepend_list.c new file mode 100644 index 00000000..d382f5a8 --- /dev/null +++ b/ccan/list/test/run-prepend_list.c @@ -0,0 +1,111 @@ +#include +#include +#include +#include + +static bool list_expect(struct list_head *h, ...) +{ + va_list ap; + struct list_node *n = &h->n, *expected; + + va_start(ap, h); + while ((expected = va_arg(ap, struct list_node *)) != NULL) { + n = n->next; + if (n != expected) + return false; + } + return (n->next == &h->n); +} + +int main(int argc, char *argv[]) +{ + struct list_head h1, h2; + struct list_node n[4]; + + plan_tests(40); + + list_head_init(&h1); + list_head_init(&h2); + + /* Append an empty list to an empty list. */ + list_append_list(&h1, &h2); + ok1(list_empty(&h1)); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + + /* Prepend an empty list to an empty list. */ + list_prepend_list(&h1, &h2); + ok1(list_empty(&h1)); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + + /* Append an empty list to a non-empty list */ + list_add(&h1, &n[0]); + list_append_list(&h1, &h2); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h1, &n[0], NULL)); + + /* Prepend an empty list to a non-empty list */ + list_prepend_list(&h1, &h2); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h1, &n[0], NULL)); + + /* Append a non-empty list to an empty list. */ + list_append_list(&h2, &h1); + ok1(list_empty(&h1)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h2, &n[0], NULL)); + + /* Prepend a non-empty list to an empty list. */ + list_prepend_list(&h1, &h2); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h1, &n[0], NULL)); + + /* Prepend a non-empty list to non-empty list. */ + list_add(&h2, &n[1]); + list_prepend_list(&h1, &h2); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h1, &n[1], &n[0], NULL)); + + /* Append a non-empty list to non-empty list. */ + list_add(&h2, &n[2]); + list_append_list(&h1, &h2); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h1, &n[1], &n[0], &n[2], NULL)); + + /* Prepend a 2-entry list to a 2-entry list. */ + list_del_from(&h1, &n[2]); + list_add(&h2, &n[2]); + list_add_tail(&h2, &n[3]); + list_prepend_list(&h1, &h2); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h1, &n[2], &n[3], &n[1], &n[0], NULL)); + + /* Append a 2-entry list to a 2-entry list. */ + list_del_from(&h1, &n[2]); + list_del_from(&h1, &n[3]); + list_add(&h2, &n[2]); + list_add_tail(&h2, &n[3]); + list_append_list(&h1, &h2); + ok1(list_empty(&h2)); + ok1(list_check(&h1, NULL)); + ok1(list_check(&h2, NULL)); + ok1(list_expect(&h1, &n[1], &n[0], &n[2], &n[3], NULL)); + + return exit_status(); +} -- 2.39.2