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

Vladimir Davydov vdavydov.dev at gmail.com
Fri Jul 19 20:59:55 MSK 2019


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




More information about the Tarantool-patches mailing list