[PATCH v4 03/12] rlist: introduce rlist_add_tail_entry_sorted

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

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 <stdio.h>
 #include <stdarg.h>
+#include <limits.h>
+#include <time.h>
 #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)