From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladimir Davydov Subject: [PATCH small 2/2] rlist: add cut and reverse methods Date: Fri, 19 Jul 2019 20:59:55 +0300 Message-Id: <0f029a60d21aef7e47e500b2d12931447279bebd.1563559036.git.vdavydov.dev@gmail.com> In-Reply-To: References: In-Reply-To: References: To: tarantool-patches@freelists.org List-ID: --- 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