From: Vladislav Shpilevoy <v.shpilevoy@tarantool.org> To: tarantool-patches@freelists.org Cc: vdavydov.dev@gmail.com Subject: [PATCH 1/1] rlist: introduce rlist_add_tail_entry_sorted Date: Thu, 31 Jan 2019 00:31:24 +0300 [thread overview] Message-ID: <ff4a7279af79f7f49fedf7c32622ec2602de7644.1548883806.git.v.shpilevoy@tarantool.org> (raw) 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)
reply other threads:[~2019-01-30 21:31 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=ff4a7279af79f7f49fedf7c32622ec2602de7644.1548883806.git.v.shpilevoy@tarantool.org \ --to=v.shpilevoy@tarantool.org \ --cc=tarantool-patches@freelists.org \ --cc=vdavydov.dev@gmail.com \ --subject='Re: [PATCH 1/1] rlist: introduce rlist_add_tail_entry_sorted' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox