[PATCH 1/3] list: list_add_after and list_add_before functions

[PATCH 1/3] list: list_add_after and list_add_before functions

[Eric Wong]

These make it easy to add a new element before or after an
existing element in the middle of the list.

The existing list_add and list_add_tail functions are trivially
reimplemented on top of these new functions.

Signed-off-by: Eric Wong <normalperson@yhbt.net>
---
 ccan/list/list.h     | 68 +++++++++++++++++++++++++++++++++++++++++++++-------
 ccan/list/test/run.c | 40 ++++++++++++++++++++++++++++++-
 2 files changed, 98 insertions(+), 10 deletions(-)

diff --git a/ccan/list/list.h b/ccan/list/list.h
index cdd5eeb..5c1159f 100644
--- a/ccan/list/list.h
+++ b/ccan/list/list.h
@@ -158,6 +158,36 @@ static inline void list_node_init(struct list_node *n)
 }
 
 /**
+ * list_add_after - add an entry after an existing node in a linked list
+ * @h: the list_head to add the node to (for debugging)
+ * @p: the existing list_node to add the node after
+ * @n: the new list_node to add to the list.
+ *
+ * The existing list_node must already be a member of the list.
+ * The new list_node does not need to be initialized; it will be overwritten.
+ *
+ * Example:
+ *	struct child c1, c2, c3;
+ *	LIST_HEAD(h);
+ *
+ *	list_add_tail(&h, &c1.list);
+ *	list_add_tail(&h, &c3.list);
+ *	list_add_after(&h, &c1.list, &c2.list);
+ */
+#define list_add_after(h, p, n) list_add_after_(h, p, n, LIST_LOC)
+static inline void list_add_after_(struct list_head *h,
+				   struct list_node *p,
+				   struct list_node *n,
+				   const char *abortstr)
+{
+	n->next = p->next;
+	n->prev = p;
+	p->next->prev = n;
+	p->next = n;
+	(void)list_debug(h, abortstr);
+}
+
+/**
  * list_add - add an entry at the start of a linked list.
  * @h: the list_head to add the node to
  * @n: the list_node to add to the list.
@@ -175,10 +205,34 @@ static inline void list_add_(struct list_head *h,
 			     struct list_node *n,
 			     const char *abortstr)
 {
-	n->next = h->n.next;
-	n->prev = &h->n;
-	h->n.next->prev = n;
-	h->n.next = n;
+	list_add_after_(h, &h->n, n, abortstr);
+}
+
+/**
+ * list_add_before - add an entry before an existing node in a linked list
+ * @h: the list_head to add the node to (for debugging)
+ * @p: the existing list_node to add the node before
+ * @n: the new list_node to add to the list.
+ *
+ * The existing list_node must already be a member of the list.
+ * The new list_node does not need to be initialized; it will be overwritten.
+ *
+ * Example:
+ *	list_head_init(&h);
+ *	list_add_tail(&h, &c1.list);
+ *	list_add_tail(&h, &c3.list);
+ *	list_add_before(&h, &c3.list, &c2.list);
+ */
+#define list_add_before(h, p, n) list_add_before_(h, p, n, LIST_LOC)
+static inline void list_add_before_(struct list_head *h,
+				    struct list_node *p,
+				    struct list_node *n,
+				    const char *abortstr)
+{
+	n->next = p;
+	n->prev = p->prev;
+	p->prev->next = n;
+	p->prev = n;
 	(void)list_debug(h, abortstr);
 }
 
@@ -197,11 +251,7 @@ static inline void list_add_tail_(struct list_head *h,
 				  struct list_node *n,
 				  const char *abortstr)
 {
-	n->next = &h->n;
-	n->prev = h->n.prev;
-	h->n.prev->next = n;
-	h->n.prev = n;
-	(void)list_debug(h, abortstr);
+	list_add_before_(h, &h->n, n, abortstr);
 }
 
 /**
diff --git a/ccan/list/test/run.c b/ccan/list/test/run.c
index 88c3835..2f1acc7 100644
--- a/ccan/list/test/run.c
+++ b/ccan/list/test/run.c
@@ -25,7 +25,7 @@ int main(int argc, char *argv[])
 	opaque_t *q, *nq;
 	struct list_head opaque_list = LIST_HEAD_INIT(opaque_list);
 
-	plan_tests(70);
+	plan_tests(79);
 	/* Test LIST_HEAD, LIST_HEAD_INIT, list_empty and check_list */
 	ok1(list_empty(&static_list));
 	ok1(list_check(&static_list, NULL));
@@ -215,5 +215,43 @@ int main(int argc, char *argv[])
 	ok1(list_top(&parent.children, struct child, list) == NULL);
 	ok1(list_tail(&parent.children, struct child, list) == NULL);
 	ok1(list_pop(&parent.children, struct child, list) == NULL);
+
+	/* Test list_add_before and list_add_after */
+	list_add(&parent.children, &c1.list);
+	list_add_after(&parent.children, &c1.list, &c2.list);
+	ok1(list_check(&parent.children, "list_add_after"));
+
+	i = 0;
+	list_for_each(&parent.children, c, list) {
+		switch (i++) {
+		case 0:
+			ok1(c == &c1);
+			break;
+		case 1:
+			ok1(c == &c2);
+			break;
+		}
+	}
+	ok1(i == 2);
+
+	list_add_before(&parent.children, &c2.list, &c3.list);
+	ok1(list_check(&parent.children, "list_add_before"));
+
+	i = 0;
+	list_for_each(&parent.children, c, list) {
+		switch (i++) {
+		case 0:
+			ok1(c == &c1);
+			break;
+		case 1:
+			ok1(c == &c3);
+			break;
+		case 2:
+			ok1(c == &c2);
+			break;
+		}
+	}
+	ok1(i == 3);
+
 	return exit_status();
 }
-- 
EW

[PATCH 2/3] list: list_swap to exchange elements

[Eric Wong]

This allows deleting and re-inserting an element in place
of the deleted element without branching.

Signed-off-by: Eric Wong <normalperson@yhbt.net>
---
 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 5c1159f..983675b 100644
--- a/ccan/list/list.h
+++ b/ccan/list/list.h
@@ -369,6 +369,39 @@ static inline void list_del_from(struct list_head *h, struct list_node *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
  * @type: the type of the entry
diff --git a/ccan/list/test/run.c b/ccan/list/test/run.c
index 2f1acc7..3067445 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();
 }
-- 
EW

[PATCH 3/3] list: add list_for_each_rev_safe

[Eric Wong]

Deleting while iterating backwards will be needed in the
Ruby st_foreach_reverse_check implementation if we decide
to port Ruby's st.c to use ccan/list.

ref: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/65408

Signed-off-by: Eric Wong <normalperson@yhbt.net>
---
 ccan/list/list.h     | 27 ++++++++++++++++++++++++++-
 ccan/list/test/run.c | 31 ++++++++++++++++++++++++++++++-
 2 files changed, 56 insertions(+), 2 deletions(-)

diff --git a/ccan/list/list.h b/ccan/list/list.h
index 983675b..b4a6cdf 100644
--- a/ccan/list/list.h
+++ b/ccan/list/list.h
@@ -527,6 +527,32 @@ static inline const void *list_tail_(const struct list_head *h, size_t off)
 	     i = container_of_var(i->member.prev, i, member))
 
 /**
+ * list_for_each_rev_safe - iterate through a list backwards,
+ * maybe during deletion
+ * @h: the list_head
+ * @i: the structure containing the list_node
+ * @nxt: the structure containing the list_node
+ * @member: the list_node member of the structure
+ *
+ * This is a convenient wrapper to iterate @i over the entire list backwards.
+ * It's a for loop, so you can break and continue as normal.  The extra
+ * variable * @nxt is used to hold the next element, so you can delete @i
+ * from the list.
+ *
+ * Example:
+ *	struct child *next;
+ *	list_for_each_rev_safe(&parent->children, child, next, list) {
+ *		printf("Name: %s\n", child->name);
+ *	}
+ */
+#define list_for_each_rev_safe(h, i, nxt, member)			\
+	for (i = container_of_var(list_debug(h,	LIST_LOC)->n.prev, i, member), \
+	     nxt = container_of_var(i->member.prev, i, member);		\
+	     &i->member != &(h)->n;					\
+	     i = nxt,							\
+	     nxt = container_of_var(i->member.prev, i, member))
+
+/**
  * list_for_each_safe - iterate through a list, maybe during deletion
  * @h: the list_head
  * @i: the structure containing the list_node
@@ -538,7 +564,6 @@ static inline const void *list_tail_(const struct list_head *h, size_t off)
  * @nxt is used to hold the next element, so you can delete @i from the list.
  *
  * Example:
- *	struct child *next;
  *	list_for_each_safe(&parent->children, child, next, list) {
  *		list_del(&child->list);
  *		parent->num_children--;
diff --git a/ccan/list/test/run.c b/ccan/list/test/run.c
index 3067445..7616af6 100644
--- a/ccan/list/test/run.c
+++ b/ccan/list/test/run.c
@@ -24,8 +24,9 @@ int main(int argc, char *argv[])
 	struct list_head list = LIST_HEAD_INIT(list);
 	opaque_t *q, *nq;
 	struct list_head opaque_list = LIST_HEAD_INIT(opaque_list);
+	LIST_HEAD(rev);
 
-	plan_tests(84);
+	plan_tests(92);
 	/* Test LIST_HEAD, LIST_HEAD_INIT, list_empty and check_list */
 	ok1(list_empty(&static_list));
 	ok1(list_check(&static_list, NULL));
@@ -148,6 +149,10 @@ int main(int argc, char *argv[])
 			list_del_from(&parent.children, &c->list);
 			break;
 		}
+
+		/* prepare for list_for_each_rev_safe test */
+		list_add(&rev, &c->list);
+
 		ok1(list_check(&parent.children, NULL));
 		if (i > 2)
 			break;
@@ -155,6 +160,30 @@ int main(int argc, char *argv[])
 	ok1(i == 3);
 	ok1(list_empty(&parent.children));
 
+	/* Test list_for_each_rev_safe, list_del and list_del_from. */
+	i = 0;
+	list_for_each_rev_safe(&rev, c, n, list) {
+		switch (i++) {
+		case 0:
+			ok1(c == &c1);
+			list_del(&c->list);
+			break;
+		case 1:
+			ok1(c == &c2);
+			list_del_from(&rev, &c->list);
+			break;
+		case 2:
+			ok1(c == &c3);
+			list_del_from(&rev, &c->list);
+			break;
+		}
+		ok1(list_check(&rev, NULL));
+		if (i > 2)
+			break;
+	}
+	ok1(i == 3);
+	ok1(list_empty(&rev));
+
 	/* Test list_node_init: safe to list_del after this. */
 	list_node_init(&c->list);
 	list_del(&c->list);
-- 
EW