From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladislav Shpilevoy Subject: [PATCH v4 03/12] rlist: introduce rlist_add_tail_entry_sorted Date: Thu, 31 Jan 2019 00:28:32 +0300 Message-Id: <7f34e14d373180ce57bfea36e3eb333c2d5c6a6a.1548883137.git.v.shpilevoy@tarantool.org> In-Reply-To: References: In-Reply-To: References: To: tarantool-patches@freelists.org Cc: kostja@tarantool.org, vdavydov.dev@gmail.com List-ID: Add an entry to an ascending sorted list. Scan is started from the tail. Applicable when new elements are usually already bigger than all other ones, since insertion into a sorted list is O(N). Necessary for SWIM implementation, where a list is stored of members, waiting for an ACK. Sometimes there can be inserted an indirect ACK, which deadline could be bigger, than deadlines of next direct ACKs. So new elements are inserted either into the tail, or almost into the tail. Order allows to stop checking next elements for an unacknowledged ping when on a next one deadline is not exceeded yet. Needed for #3234 --- src/lib/small | 2 +- test/unit/rlist.c | 40 +++++++++++++++++++++++++++++++++++++++- test/unit/rlist.result | 6 +++++- 3 files changed, 45 insertions(+), 3 deletions(-) diff --git a/src/lib/small b/src/lib/small index cdf7d4a8e..ff4a7279a 160000 --- a/src/lib/small +++ b/src/lib/small @@ -1 +1 @@ -Subproject commit cdf7d4a8e24ae465298d0ddacaf1aaed1085281e +Subproject commit ff4a7279af79f7f49fedf7c32622ec2602de7644 diff --git a/test/unit/rlist.c b/test/unit/rlist.c index c0c29a3f1..eb78adc7e 100644 --- a/test/unit/rlist.c +++ b/test/unit/rlist.c @@ -1,10 +1,12 @@ #include "small/rlist.h" #include #include +#include +#include #include "unit.h" -#define PLAN 87 +#define PLAN 91 #define ITEMS 7 @@ -19,9 +21,16 @@ static struct test items[ITEMS]; static RLIST_HEAD(head); static RLIST_HEAD(head2); +static inline int +cmp(struct test *a, struct test *b) +{ + return a->no - b->no; +} + int main(void) { + srand(time(NULL)); int i; struct test *it; struct rlist *rlist; @@ -132,6 +141,35 @@ main(void) rlist_add_entry(&head, &items[0], list); ok(rlist_prev_entry_safe(&items[0], &head, list) == NULL, "prev is null"); + + rlist_insert_after_entry(&items[0], &items[2], list); + it = rlist_first_entry(&head, struct test, list); + is(it, &items[0], "inserted after first, first is ok"); + it = rlist_next_entry(it, list); + is(it, &items[2], "inserted after first, second is ok"); + + rlist_insert_after_entry(&items[0], &items[1], list); + int is_sorted = 1; + i = 0; + rlist_foreach_entry(it, &head, list) + is_sorted = is_sorted && it == &items[i++]; + rlist_foreach_entry_reverse(it, &head, list) + is_sorted = is_sorted && it == &items[--i]; + ok(is_sorted, "after insertion into the middle the list is ok"); + + rlist_create(&head); + for (int i = 0; i < ITEMS; ++i) { + items[i].no = rand() % ITEMS; + rlist_add_tail_entry_sorted(&head, it, &items[i], list, cmp); + } + int prev = INT_MIN; + is_sorted = 1; + rlist_foreach_entry(it, &head, list) { + is_sorted = is_sorted && prev <= it->no; + prev = it->no; + } + ok(is_sorted, "the list is sorted"); + return check_plan(); } diff --git a/test/unit/rlist.result b/test/unit/rlist.result index fa99a87cf..b2239d8f9 100644 --- a/test/unit/rlist.result +++ b/test/unit/rlist.result @@ -1,4 +1,4 @@ -1..87 +1..91 ok 1 - list is empty ok 2 - rlist_nil is empty ok 3 - head2 is empty @@ -86,3 +86,7 @@ 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 - inserted after first, first is ok +ok 89 - inserted after first, second is ok +ok 90 - after insertion into the middle the list is ok +ok 91 - the list is sorted -- 2.17.2 (Apple Git-113)