From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Fri, 15 Feb 2019 16:26:50 +0300 From: Konstantin Osipov Subject: Re: [tarantool-patches] [PATCH v4 03/12] rlist: introduce rlist_add_tail_entry_sorted Message-ID: <20190215132650.GF24683@chai> References: <7f34e14d373180ce57bfea36e3eb333c2d5c6a6a.1548883137.git.v.shpilevoy@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <7f34e14d373180ce57bfea36e3eb333c2d5c6a6a.1548883137.git.v.shpilevoy@tarantool.org> To: tarantool-patches@freelists.org Cc: vdavydov.dev@gmail.com List-ID: * Vladislav Shpilevoy [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