On Wed, 07 Dec 2011 04:00:34 -0500, Jonathan M Davis <[email protected]> wrote:

On Wednesday, December 07, 2011 09:10:16 Martin Nowak wrote:
On Wed, 07 Dec 2011 08:59:32 +0100, raojm <[email protected]> wrote:
> Is D associative array  thread safe, and  will it relocate memory when
> add or delete a value?
>
> Where I can find the implemention.

No it's not, and yes it has to relocate memory.
It's working as a hashtable not a binary tree, so all
pointers will be invalidated by adding/removing.
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d

Yeah. AFAIK, it's impossible to have a hash table which doesn't risk
reallocating something when adding a value to it, unless you limit how many
elements it can hold or somesuch, which would make it considerably less
useful. Typically, when a hash table gets full enough, it rehashes itself, which definitely involves allocating more memory, and possible reallocating a large portion of what it's already allocated. So, there's no way that an AA can avoid the risk of reallocating when elements are added to it, pretty much regardless of its implementation. It's an attribute of the data structure.

dcollections' HashMap does not invalidate cursors when adding data, even when a rehash is done. The rehash routine specifically is written to make this possible.

However, it does invalidate ranges.

Note that for any hash implementation, the only thing that needs to be reallocated is the bucket array. In many implementations, this is not where the data is stored.

-Steve

Reply via email to