On 26-Aug-23 15:12, Daniel Stenberg wrote:
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).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?
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.
OpenPGP_signature
Description: OpenPGP digital signature
-- Unsubscribe: https://lists.haxx.se/mailman/listinfo/curl-library Etiquette: https://curl.se/mail/etiquette.html
