From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladislav Shpilevoy Subject: [PATCH 1/1] rlist: introduce rlist_add_tail_entry_sorted Date: Thu, 31 Jan 2019 00:31:24 +0300 Message-Id: To: tarantool-patches@freelists.org Cc: 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. --- 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)