curl / Mailing Lists / curl-library / Single Mail
Buy commercial curl support from WolfSSL. We help you work out your issues, debug your libcurl applications, use the API, port to new platforms, add new features and more. With a team lead by the curl founder himself.

Re: Getting a list of easy handles in a multi handle - possible?

From: Timothe Litt <>
Date: Sat, 26 Aug 2023 16:19:07 -0400

On 26-Aug-23 15:12, Daniel Stenberg wrote:
> On Sat, 26 Aug 2023, Timothe Litt via curl-library wrote:
>> Not very efficient if there are lots of handles.  You will scan the
>> list O(n^2) looking for prev each time - or, I suppose create a hash.
> Between each invoke there may be N new handles added and M handles may
> have been removed. How would the hash work?
What I meant here was a hash table on the side of (parallel to) your
existing list.  Key is the handle, value is the corresponding list
index.  When looking for "prev", you do an O(1) hash lookup to get its
index.  Add 1, bounds check and return the next (or NULL).

  You can add and delete items from a hash table as the list changes,
though depending on the hash table's structure it may be cheaper to
simply mark items deleted (e.g. index -1).   To avoid compacting the
list on deletion (which would mean updating the hash values > the
deleted item), link unused entries into a freelist and hand them out
preferentially on a subsequent add.

Using an iterator as in my earlier note is a simpler solution to this
request - you look at the "next" slot in a copy of the list taken when
the iterator is created.  Any subsequent add/delete isn't reflected. And
the bookkeeping is invisible to the caller. But to make it thread safe
(and to avoid the complications of intermediate add/deletes), you are
best off copying the list.

(Note that with your scheme, you're assuming that  "prev" doesn't get
destroyed between calls.)

OTOH a hash table benefits all cases where you want to find an easy
handle in a multi handle.  Keeping the existing list simplifies the
change and it's usually more efficient to walk a linear list than a hash
table for operations that want to iterate over the set.

The hash table does cost some memory, and depending on the
implementation there may be a cost to expand it beyond a
forecast/initial size.

Timothe Litt
ACM Distinguished Engineer
This communication may not represent the ACM or my employer's views,
if any, on the matters discussed.

Received on 2023-08-26