[PATCH small 0/2] small: add new rlist helpers

[PATCH small 0/2] small: add new rlist helpers

[Vladimir Davydov]

This patch set adds two simple helpers for rlist, which are needed to
properly support savepoints in DDL transactions.

It also moves unit tests from tarantool to the small repository, where
they truly belong.

https://github.com/tarantool/small/tree/dv/rlist-reverse-cut

Vladimir Davydov (2):
  rlist: add unit test
  rlist: add cut and reverse methods

 small/rlist.h       |  34 +++++++++++
 test/CMakeLists.txt |   4 ++
 test/rlist.c        | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 test/rlist.result   | 105 ++++++++++++++++++++++++++++++++++
 4 files changed, 301 insertions(+)
 create mode 100644 test/rlist.c
 create mode 100644 test/rlist.result

-- 
2.11.0

[PATCH small 1/2] rlist: add unit test

[Vladimir Davydov]

Copied from tarantool/test/unit/rlist.
---
 test/CMakeLists.txt |   4 ++
 test/rlist.c        | 134 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 test/rlist.result   |  90 +++++++++++++++++++++++++++++++++++
 3 files changed, 228 insertions(+)
 create mode 100644 test/rlist.c
 create mode 100644 test/rlist.result

diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 84d59dcdfb4c..8317c652aee8 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -15,6 +15,9 @@ target_link_libraries(ibuf.test small)
 add_executable(obuf.test obuf.c)
 target_link_libraries(obuf.test small)
 
+add_executable(rlist.test rlist.c unit.c)
+target_link_libraries(rlist.test small)
+
 add_executable(rb.test rb.c)
 target_link_libraries(rb.test small)
 
@@ -73,6 +76,7 @@ add_test(rb ${CMAKE_CURRENT_BUILD_DIR}/rb.test)
 add_test(rb_aug ${CMAKE_CURRENT_BUILD_DIR}/rb_aug.test)
 add_test(rb_rand ${CMAKE_CURRENT_BUILD_DIR}/rb_rand.test)
 add_test(static ${CMAKE_CURRENT_BUILD_DIR}/static.test)
+add_test(rlist ${CMAKE_CURRENT_BUILD_DIR}/rlist.test)
 
 if(DEFINED SMALL_EMBEDDED)
     return()
diff --git a/test/rlist.c b/test/rlist.c
new file mode 100644
index 000000000000..e840eb58c6c3
--- /dev/null
+++ b/test/rlist.c
@@ -0,0 +1,134 @@
+#include "unit.h"
+#include "../small/rlist.h"
+
+#define ITEMS		7
+
+struct test {
+	int no;
+	struct rlist list;
+};
+
+static struct test items[ITEMS];
+
+static RLIST_HEAD(head);
+static RLIST_HEAD(head2);
+
+int
+main(void)
+{
+	int i;
+	struct test *it;
+	struct rlist *rlist;
+
+	header();
+	plan(87);
+	ok(rlist_empty(&head), "list is empty");
+	for (i = 0; i < ITEMS; i++) {
+		items[i].no = i;
+		rlist_add_tail(&head, &(items[i].list));
+	}
+	RLIST_HEAD(empty_list);
+	ok(rlist_empty(&empty_list), "rlist_nil is empty");
+	ok(rlist_empty(&head2), "head2 is empty");
+	rlist_swap(&head2, &empty_list);
+	ok(rlist_empty(&empty_list), "rlist_nil is empty after swap");
+	ok(rlist_empty(&head2), "head2 is empty after swap");
+	rlist_swap(&head, &head2);
+	ok(rlist_empty(&head), "head is empty after swap");
+	is(rlist_first(&head2), &items[0].list, "first item");
+	is(rlist_last(&head2), &items[ITEMS - 1].list, "last item");
+	i = 0;
+	rlist_foreach(rlist, &head2) {
+		is(rlist, &items[i].list, "element (foreach) %d", i);
+		i++;
+	}
+	rlist_foreach_reverse(rlist, &head2) {
+		i--;
+		is(rlist, &items[i].list, "element (foreach_reverse) %d", i);
+	}
+	rlist_swap(&head2, &head);
+
+
+	is(rlist_first(&head), &items[0].list, "first item");
+	isnt(rlist_first(&head), &items[ITEMS - 1].list, "first item");
+
+	is(rlist_last(&head), &items[ITEMS - 1].list, "last item");
+	isnt(rlist_last(&head), &items[0].list, "last item");
+
+	is(rlist_next(&head), &items[0].list, "rlist_next");
+	is(rlist_prev(&head), &items[ITEMS - 1].list, "rlist_prev");
+
+	i = 0;
+	rlist_foreach(rlist, &head) {
+		is(rlist, &items[i].list, "element (foreach) %d", i);
+		i++;
+	}
+	rlist_foreach_reverse(rlist, &head) {
+		i--;
+		is(rlist, &items[i].list, "element (foreach_reverse) %d", i);
+	}
+
+
+	is(rlist_entry(&items[0].list, struct test, list), &items[0],
+		"rlist_entry");
+	is(rlist_first_entry(&head, struct test, list), &items[0],
+		"rlist_first_entry");
+	is(rlist_next_entry(&items[0], list), &items[1], "rlist_next_entry");
+	is(rlist_prev_entry(&items[2], list), &items[1], "rlist_prev_entry");
+
+
+	i = 0;
+	rlist_foreach_entry(it, &head, list) {
+		is(it, items + i, "element (foreach_entry) %d", i);
+		i++;
+	}
+	rlist_foreach_entry_reverse(it, &head, list) {
+		i--;
+		is(it, items + i, "element (foreach_entry_reverse) %d", i);
+	}
+
+	rlist_del(&items[2].list);
+	ok(rlist_empty(&head2), "head2 is empty");
+	rlist_move(&head2, &items[3].list);
+	ok(!rlist_empty(&head2), "head2 isnt empty");
+	is(rlist_first_entry(&head2, struct test, list),
+					&items[3], "Item was moved");
+	rlist_move_tail(&head2, &items[4].list);
+	rlist_foreach_entry(it, &head, list) {
+		is(it, items + i, "element (second deleted) %d", i);
+		i++;
+		if (i == 2)
+			i += 3;
+	}
+	rlist_foreach_entry_reverse(it, &head, list) {
+		i--;
+		if (i == 4)
+			i -= 3;
+		is(it, items + i, "element (second deleted) %d", i);
+	}
+
+
+	rlist_create(&head);
+	ok(rlist_empty(&head), "list is empty");
+	for (i = 0; i < ITEMS; i++) {
+		items[i].no = i;
+		rlist_add(&head, &(items[i].list));
+	}
+	i = 0;
+	rlist_foreach_entry_reverse(it, &head, list) {
+		is(it, items + i, "element (foreach_entry_reverse) %d", i);
+		i++;
+	}
+	rlist_foreach_entry(it, &head, list) {
+		i--;
+		is(it, items + i, "element (foreach_entry) %d", i);
+	}
+	rlist_create(&head);
+	rlist_add_entry(&head, &items[0], list);
+	ok(rlist_prev_entry_safe(&items[0], &head, list) == NULL,
+	   "prev is null");
+
+	int rc = check_plan();
+	footer();
+	return rc;
+}
diff --git a/test/rlist.result b/test/rlist.result
new file mode 100644
index 000000000000..197e83bbf17d
--- /dev/null
+++ b/test/rlist.result
@@ -0,0 +1,90 @@
+	*** main ***
+1..87
+ok 1 - list is empty
+ok 2 - rlist_nil is empty
+ok 3 - head2 is empty
+ok 4 - rlist_nil is empty after swap
+ok 5 - head2 is empty after swap
+ok 6 - head is empty after swap
+ok 7 - first item
+ok 8 - last item
+ok 9 - element (foreach) 0
+ok 10 - element (foreach) 1
+ok 11 - element (foreach) 2
+ok 12 - element (foreach) 3
+ok 13 - element (foreach) 4
+ok 14 - element (foreach) 5
+ok 15 - element (foreach) 6
+ok 16 - element (foreach_reverse) 6
+ok 17 - element (foreach_reverse) 5
+ok 18 - element (foreach_reverse) 4
+ok 19 - element (foreach_reverse) 3
+ok 20 - element (foreach_reverse) 2
+ok 21 - element (foreach_reverse) 1
+ok 22 - element (foreach_reverse) 0
+ok 23 - first item
+ok 24 - first item
+ok 25 - last item
+ok 26 - last item
+ok 27 - rlist_next
+ok 28 - rlist_prev
+ok 29 - element (foreach) 0
+ok 30 - element (foreach) 1
+ok 31 - element (foreach) 2
+ok 32 - element (foreach) 3
+ok 33 - element (foreach) 4
+ok 34 - element (foreach) 5
+ok 35 - element (foreach) 6
+ok 36 - element (foreach_reverse) 6
+ok 37 - element (foreach_reverse) 5
+ok 38 - element (foreach_reverse) 4
+ok 39 - element (foreach_reverse) 3
+ok 40 - element (foreach_reverse) 2
+ok 41 - element (foreach_reverse) 1
+ok 42 - element (foreach_reverse) 0
+ok 43 - rlist_entry
+ok 44 - rlist_first_entry
+ok 45 - rlist_next_entry
+ok 46 - rlist_prev_entry
+ok 47 - element (foreach_entry) 0
+ok 48 - element (foreach_entry) 1
+ok 49 - element (foreach_entry) 2
+ok 50 - element (foreach_entry) 3
+ok 51 - element (foreach_entry) 4
+ok 52 - element (foreach_entry) 5
+ok 53 - element (foreach_entry) 6
+ok 54 - element (foreach_entry_reverse) 6
+ok 55 - element (foreach_entry_reverse) 5
+ok 56 - element (foreach_entry_reverse) 4
+ok 57 - element (foreach_entry_reverse) 3
+ok 58 - element (foreach_entry_reverse) 2
+ok 59 - element (foreach_entry_reverse) 1
+ok 60 - element (foreach_entry_reverse) 0
+ok 61 - head2 is empty
+ok 62 - head2 isnt empty
+ok 63 - Item was moved
+ok 64 - element (second deleted) 0
+ok 65 - element (second deleted) 1
+ok 66 - element (second deleted) 5
+ok 67 - element (second deleted) 6
+ok 68 - element (second deleted) 6
+ok 69 - element (second deleted) 5
+ok 70 - element (second deleted) 1
+ok 71 - element (second deleted) 0
+ok 72 - list is empty
+ok 73 - element (foreach_entry_reverse) 0
+ok 74 - element (foreach_entry_reverse) 1
+ok 75 - element (foreach_entry_reverse) 2
+ok 76 - element (foreach_entry_reverse) 3
+ok 77 - element (foreach_entry_reverse) 4
+ok 78 - element (foreach_entry_reverse) 5
+ok 79 - element (foreach_entry_reverse) 6
+ok 80 - element (foreach_entry) 6
+ok 81 - element (foreach_entry) 5
+ok 82 - element (foreach_entry) 4
+ok 83 - element (foreach_entry) 3
+ok 84 - element (foreach_entry) 2
+ok 85 - element (foreach_entry) 1
+ok 86 - element (foreach_entry) 0
+ok 87 - prev is null
+	*** main: done ***
-- 
2.11.0

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

[Vladimir Davydov]

---
 small/rlist.h     | 34 ++++++++++++++++++++++++++++++++++
 test/rlist.c      | 26 +++++++++++++++++++++++++-
 test/rlist.result | 17 ++++++++++++++++-
 3 files changed, 75 insertions(+), 2 deletions(-)

diff --git a/small/rlist.h b/small/rlist.h
index b32ed975739e..7b4547ae6da2 100644
--- a/small/rlist.h
+++ b/small/rlist.h
@@ -234,6 +234,40 @@ 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;
+}
+
+/**
+ * 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);
+}
+
+/**
  * list head initializer
  */
 #define RLIST_HEAD_INITIALIZER(name) { &(name), &(name) }
diff --git a/test/rlist.c b/test/rlist.c
index e840eb58c6c3..8e4d1b190713 100644
--- a/test/rlist.c
+++ b/test/rlist.c
@@ -21,7 +21,7 @@ main(void)
 	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,30 @@ 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));
+	}
+	rlist_reverse(&head);
+	i = 0;
+	rlist_foreach_entry(it, &head, list) {
+		is(it, items + i, "element (reverse) %d", i);
+		i++;
+	}
+	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 ***
-- 
2.11.0

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

[Vladimir Davydov]

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 ***

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

[Konstantin Osipov]

* Vladimir Davydov <vdavydov.dev@gmail.com> [19/07/25 17:36]:

The tests for both functions should cover an empty list and a list
with 1 element.

Otherwise lgtm.


-- 
Konstantin Osipov, Moscow, Russia

[tarantool-patches] Re: [PATCH small 0/2] small: add new rlist helpers

[Konstantin Osipov]

* Vladimir Davydov <vdavydov.dev@gmail.com> [19/07/19 21:03]:
> This patch set adds two simple helpers for rlist, which are needed to
> properly support savepoints in DDL transactions.
> 
> It also moves unit tests from tarantool to the small repository, where
> they truly belong.
> 
> https://github.com/tarantool/small/tree/dv/rlist-reverse-cut

small unit tests were run as part of tarantool coverage on
purpose, to ensure that they pass on all platforms where tarantool
is built


-- 
Konstantin Osipov, Moscow, Russia

Re: [tarantool-patches] Re: [PATCH small 0/2] small: add new rlist helpers

[Vladimir Davydov]

On Fri, Jul 19, 2019 at 09:53:34PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [19/07/19 21:03]:
> > This patch set adds two simple helpers for rlist, which are needed to
> > properly support savepoints in DDL transactions.
> > 
> > It also moves unit tests from tarantool to the small repository, where
> > they truly belong.
> > 
> > https://github.com/tarantool/small/tree/dv/rlist-reverse-cut
> 
> small unit tests were run as part of tarantool coverage on
> purpose, to ensure that they pass on all platforms where tarantool
> is built

Okay. They are still run from the tarantool repository - via small/ test
suite. This patch simply moves rlist test from unit/ to small/, where
other small-related tests (such as rb) are located.

[tarantool-patches] Re: [PATCH small 0/2] small: add new rlist helpers

[Konstantin Osipov]

* Vladimir Davydov <vdavydov.dev@gmail.com> [19/07/19 22:44]:
> On Fri, Jul 19, 2019 at 09:53:34PM +0300, Konstantin Osipov wrote:
> > * Vladimir Davydov <vdavydov.dev@gmail.com> [19/07/19 21:03]:
> > > This patch set adds two simple helpers for rlist, which are needed to
> > > properly support savepoints in DDL transactions.
> > > 
> > > It also moves unit tests from tarantool to the small repository, where
> > > they truly belong.
> > > 
> > > https://github.com/tarantool/small/tree/dv/rlist-reverse-cut
> > 
> > small unit tests were run as part of tarantool coverage on
> > purpose, to ensure that they pass on all platforms where tarantool
> > is built
> 
> Okay. They are still run from the tarantool repository - via small/ test
> suite. This patch simply moves rlist test from unit/ to small/, where
> other small-related tests (such as rb) are located.

Ah, got it.

-- 
Konstantin Osipov, Moscow, Russia

Re: [PATCH small 0/2] small: add new rlist helpers

[Vladimir Davydov]

Added a few more tests as requested by Kostja and pushed to master.