From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Thu, 25 Jul 2019 17:31:43 +0300 From: Vladimir Davydov Subject: Re: [PATCH small 2/2] rlist: add cut and reverse methods Message-ID: <20190725143143.GO24631@esperanza> References: <0f029a60d21aef7e47e500b2d12931447279bebd.1563559036.git.vdavydov.dev@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <0f029a60d21aef7e47e500b2d12931447279bebd.1563559036.git.vdavydov.dev@gmail.com> To: tarantool-patches@freelists.org List-ID: 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 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 ***