https://bugs.kde.org/show_bug.cgi?id=367995
--- Comment #18 from Philippe Waroquiers <philippe.waroqui...@skynet.be> ---
(In reply to Ruurd Beerstra from comment #15)
Thanks for all your work on this, I think this is useful
(I have not yet looked in depth, but I think this might be used
for the 'self-hosting' of valgrind, as valgrind uses pools).
> Part of the inefficiency is that it has to restart the scan after modifying
> the list. Can't help that.
> Also, I can't find any other way in valgrind to find the chunks with a
> particular address-range other than a brute-force scan.
It is effectively the scan restart which makes it quadratic.
The brute-force scan is reasonable: that will be O(n), and
avoiding this linear scan would imply overhead for the non mempool
uses.
Such mempool functionalities will often be used by applications
that use a lot of (small) blocks, so it would be better to avoid this quadratic
aspect.
Various techniques can be used for that, I think the best/easiest
is to add a function
void* VG_(HT_remove_at_Iter) ( VgHashTable *table)
which removes the item at the current position of the iterator
ensuring that after the removal the iterator is such that VG_(HT_next)
will return the element following the one just removed (or NULL, if the removed
element was the last element).
This removal will not cause problems (no hash table resize, and proper
maintenance of the iter and chains).
Philippe
NB: more generally, as an hash table can only have one single iterator, it
would be
possible to allow calls to the other removal functions, but I think it is
better to
have a special function for that).
Handling additions during iteration is more problematic, due to possible hash
table resize.
--
You are receiving this mail because:
You are watching all bug changes.
