[Issue 4475] Improving the compiler 'in' associative array can return just a bool

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4475



--- Comment #11 from hsteoh at quickfur.ath.cx 2013-08-15 12:03:49 PDT ---
(In reply to comment #10)
[...]
> Associative arrays have to grow when you keep adding key-value pairs, I presume
> this is done allocating a new larger hash (probably 2 or 4 times larger), and
> copying data in it. In such situation aren't the pointers to the items becoming
> invalid? Even if the doubling is done with a realloc, it can sometimes not be
> able to reallocate in place.

The reason it works, is because the hash table itself doesn't contain the
actual key/value pairs; it just contains pointers to linked-lists of these
key/value pairs. So the hash table can be modified however you like, but the
key/value pairs stays in the same memory address.

This would work even if we used something other than linked-lists for the
key/value pairs, e.g., trees, because the key/value pairs would just have some
pointers to neighbouring nodes, and during AA rehash (or add/delete) all that
happens is that some of these pointers get reassigned, but the node itself
(containing the key/value pair) remains in the same memory address. This kind
of implementation avoids copying/moving of keys and values, so I'd expect any
good AA implementation to do something similar.

I'm pretty sure that it's generally expected that AA implementations should
obey the principle that iterators (i.e. pointers to key/value) are not
invalidated by add/delete, otherwise it would greatly reduce the usefulness of
AA's. I'm not too sure about this also holding for rehash, but the current AA
implementation does indeed preserve references across rehash as well (though it
does break iteration order if you trigger a rehash in the middle of iterating
over the AA -- but you won't get invalid pointers out of it).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------