[PATCH small 2/2] rlist: add cut and reverse methods
Vladimir Davydov
vdavydov.dev at gmail.com
Thu Jul 25 17:31:43 MSK 2019
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 at 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 ***
More information about the Tarantool-patches
mailing list