From 3d74240c155b68ae0d59a5942048aa1db3e29b01 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Fri, 24 Oct 2014 22:02:29 +0000 Subject: [PATCH 1/1] list: list_swap to exchange elements This allows deleting and re-inserting an element in place of the deleted element without branching. Signed-off-by: Eric Wong Reviewed-by: David Gibson Signed-off-by: Rusty Russell --- ccan/list/list.h | 33 +++++++++++++++++++++++++++++++++ ccan/list/test/run.c | 23 +++++++++++++++++++++-- 2 files changed, 54 insertions(+), 2 deletions(-) diff --git a/ccan/list/list.h b/ccan/list/list.h index 5c1159f4..983675b8 100644 --- a/ccan/list/list.h +++ b/ccan/list/list.h @@ -368,6 +368,39 @@ static inline void list_del_from(struct list_head *h, struct list_node *n) list_del(n); } +/** + * list_swap - swap out an entry from an (unknown) linked list for a new one. + * @o: the list_node to replace from the list. + * @n: the list_node to insert in place of the old one. + * + * Note that this leaves @o in an undefined state; it can be added to + * another list, but not deleted/swapped again. + * + * See also: + * list_del() + * + * Example: + * struct child x1, x2; + * LIST_HEAD(xh); + * + * list_add(&xh, &x1.list); + * list_swap(&x1.list, &x2.list); + */ +#define list_swap(o, n) list_swap_(o, n, LIST_LOC) +static inline void list_swap_(struct list_node *o, + struct list_node *n, + const char* abortstr) +{ + (void)list_debug_node(o, abortstr); + *n = *o; + n->next->prev = n; + n->prev->next = n; +#ifdef CCAN_LIST_DEBUG + /* Catch use-after-del. */ + o->next = o->prev = NULL; +#endif +} + /** * list_entry - convert a list_node back into the structure containing it. * @n: the list_node diff --git a/ccan/list/test/run.c b/ccan/list/test/run.c index 2f1acc78..30674459 100644 --- a/ccan/list/test/run.c +++ b/ccan/list/test/run.c @@ -19,13 +19,13 @@ static LIST_HEAD(static_list); int main(int argc, char *argv[]) { struct parent parent; - struct child c1, c2, c3, *c, *n; + struct child c1, c2, c3, x1, *c, *n; unsigned int i; struct list_head list = LIST_HEAD_INIT(list); opaque_t *q, *nq; struct list_head opaque_list = LIST_HEAD_INIT(opaque_list); - plan_tests(79); + plan_tests(84); /* Test LIST_HEAD, LIST_HEAD_INIT, list_empty and check_list */ ok1(list_empty(&static_list)); ok1(list_check(&static_list, NULL)); @@ -253,5 +253,24 @@ int main(int argc, char *argv[]) } ok1(i == 3); + /* test list_swap */ + list_swap(&c3.list, &x1.list); + ok1(list_check(&parent.children, "list_swap")); + i = 0; + list_for_each(&parent.children, c, list) { + switch (i++) { + case 0: + ok1(c == &c1); + break; + case 1: + ok1(c == &x1); + break; + case 2: + ok1(c == &c2); + break; + } + } + ok1(i == 3); + return exit_status(); } -- 2.39.2