Re: [PATCH small 2/2] rlist: add cut and reverse methods

[Vladimir Davydov <vdavydov.dev@gmail.com>]

On Fri, Jul 19, 2019 at 08:59:55PM +0300, Vladimir Davydov wrote:
> +/**
> + * reverse a list in-place
> + */
> +static inline void
> +rlist_reverse(struct rlist *head)
> +{
> +	struct rlist *item = head;
> +	do {
> +		struct rlist *next = item->next;
> +		item->next = item->prev;
> +		item->prev = next;
> +		item = next;
> +	} while (item != head);
> +}

As pointed out by Kostja, it isn't a good idea to call rlist_reverse()
on a hot path. It's better to iterate the list backwards. So the new
patch adds rlist_foreach_entry_safe_reverse helper instead:

From bdd85896d788b7965e46b8dae9a80bdfc958b0a3 Mon Sep 17 00:00:00 2001
From: Vladimir Davydov <vdavydov.dev@gmail.com>
Date: Fri, 19 Jul 2019 16:15:49 +0300
Subject: [PATCH] rlist: add cut and foreach_safe_reverse helpers


diff --git a/small/rlist.h b/small/rlist.h
index b32ed975739e..2b0bcb474e77 100644
--- a/small/rlist.h
+++ b/small/rlist.h
@@ -233,6 +233,25 @@ rlist_splice_tail(struct rlist *head1, struct rlist *head2)
 	}
 }
 
+/**
+ * move the initial part of list head2, up to but excluding item,
+ * to list head1; the old content of head1 is discarded
+ */
+static inline void
+rlist_cut_before(struct rlist *head1, struct rlist *head2, struct rlist *item)
+{
+	if (head1->next == item) {
+		rlist_create(head1);
+		return;
+	}
+	head1->next = head2->next;
+	head1->next->prev = head1;
+	head1->prev = item->prev;
+	head1->prev->next = head1;
+	head2->next = item;
+	item->prev = head2;
+}
+
 /**
  * list head initializer
  */
@@ -364,6 +383,15 @@ delete from one list and add_tail as another's head
 	     ((tmp) = rlist_next_entry((item), member));                \
 	     (item) = (tmp))
 
+/**
+ * foreach backward through all list entries safe against removal
+ */
+#define rlist_foreach_entry_safe_reverse(item, head, member, tmp)	\
+	for ((item) = rlist_last_entry((head), typeof(*item), member);	\
+	     &item->member != (head) &&					\
+	     ((tmp) = rlist_prev_entry((item), member));		\
+	     (item) = (tmp))
+
 #if defined(__cplusplus)
 } /* extern "C" */
 #endif /* defined(__cplusplus) */
diff --git a/test/rlist.c b/test/rlist.c
index e840eb58c6c3..83d42434a324 100644
--- a/test/rlist.c
+++ b/test/rlist.c
@@ -17,11 +17,11 @@ int
 main(void)
 {
 	int i;
-	struct test *it;
+	struct test *it, *tmp;
 	struct rlist *rlist;
 
 	header();
-	plan(87);
+	plan(102);
 	ok(rlist_empty(&head), "list is empty");
 	for (i = 0; i < ITEMS; i++) {
 		items[i].no = i;
@@ -128,6 +128,34 @@ main(void)
 	ok(rlist_prev_entry_safe(&items[0], &head, list) == NULL,
 	   "prev is null");
 
+	rlist_create(&head);
+	for (i = 0; i < ITEMS; i++) {
+		items[i].no = i;
+		rlist_add(&head, &(items[i].list));
+	}
+	i = 0;
+	rlist_foreach_entry_safe_reverse(it, &head, list, tmp) {
+		rlist_del_entry(it, list);
+		is(it, items + i, "element (reverse) %d", i);
+		i++;
+	}
+	for (i = 0; i < ITEMS; i++) {
+		items[i].no = i;
+		rlist_add_tail(&head, &(items[i].list));
+	}
+	rlist_cut_before(&head2, &head, head.next);
+	ok(rlist_empty(&head2), "list is empty");
+	rlist_cut_before(&head2, &head, &items[ITEMS / 2].list);
+	i = 0;
+	rlist_foreach_entry(it, &head2, list) {
+		is(it, items + i, "element (first half) %d", i);
+		i++;
+	}
+	rlist_foreach_entry(it, &head, list) {
+		is(it, items + i, "element (second half) %d", i);
+		i++;
+	}
+
 	int rc = check_plan();
 	footer();
 	return rc;
diff --git a/test/rlist.result b/test/rlist.result
index 197e83bbf17d..f79cf8abcaa9 100644
--- a/test/rlist.result
+++ b/test/rlist.result
@@ -1,5 +1,5 @@
 	*** main ***
-1..87
+1..102
 ok 1 - list is empty
 ok 2 - rlist_nil is empty
 ok 3 - head2 is empty
@@ -87,4 +87,19 @@ ok 84 - element (foreach_entry) 2
 ok 85 - element (foreach_entry) 1
 ok 86 - element (foreach_entry) 0
 ok 87 - prev is null
+ok 88 - element (reverse) 0
+ok 89 - element (reverse) 1
+ok 90 - element (reverse) 2
+ok 91 - element (reverse) 3
+ok 92 - element (reverse) 4
+ok 93 - element (reverse) 5
+ok 94 - element (reverse) 6
+ok 95 - list is empty
+ok 96 - element (first half) 0
+ok 97 - element (first half) 1
+ok 98 - element (first half) 2
+ok 99 - element (second half) 3
+ok 100 - element (second half) 4
+ok 101 - element (second half) 5
+ok 102 - element (second half) 6
 	*** main: done ***