[tarantool-patches] [PATCH v4 03/12] rlist: introduce rlist_add_tail_entry_sorted

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy at tarantool.org> [19/01/31 10:28]:
> 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

I don't mind having an insert into a sorted list, but
1) we're not stl, so this algorithm is not a generic one. Soon
   we'll get slist_insert_sorted, array_insert_sorted, etc.
2) I don't understand if there is any reason to use rlist in this
   case, why not use a red-black tree?
3) Why do we have the test in the server, while the library itself
   is a subproject? I believe the library does have unit tests,
   why not add tests there?


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov