[PATCH 1/1] rlist: introduce rlist_add_tail_entry_sorted

[Vladislav Shpilevoy]

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.
---
Branch: https://github.com/tarantool/small/tree/gerold103/sorted-list

 small/rlist.h | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/small/rlist.h b/small/rlist.h
index b32ed97..cd6d3e0 100644
--- a/small/rlist.h
+++ b/small/rlist.h
@@ -233,6 +233,16 @@ rlist_splice_tail(struct rlist *head1, struct rlist *head2)
 	}
 }
 
+/** Insert a new item into a list right after another item. */
+static inline void
+rlist_insert_after(struct rlist *item, struct rlist *new_item)
+{
+	new_item->prev = item;
+	new_item->next = item->next;
+	item->next = new_item;
+	new_item->next->prev = new_item;
+}
+
 /**
  * list head initializer
  */
@@ -312,6 +322,25 @@ rlist_splice_tail(struct rlist *head1, struct rlist *head2)
 #define rlist_add_tail_entry(head, item, member)			\
 	rlist_add_tail((head), &(item)->member)
 
+#define rlist_insert_after_entry(item, new_item, member)		\
+	rlist_insert_after(&(item)->member, &(new_item)->member)
+
+/**
+ * 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).
+ */
+#define rlist_add_tail_entry_sorted(head, pos, item, member, cmp)	\
+	rlist_foreach_entry_reverse(pos, head, member) {		\
+		if (cmp((pos), (item)) <= 0) {				\
+			rlist_insert_after_entry(pos, item, member);	\
+			break;						\
+		}							\
+	}								\
+	if (&(pos)->member == (head))					\
+		rlist_add_entry(head, item, member);
+
 /**
 delete from one list and add as another's head
 */
-- 
2.17.2 (Apple Git-113)