Is D associative array thread safe, and will it relocate memory when add or delete a value?

[Martin Nowak]

On Wed, 07 Dec 2011 14:51:49 +0100, Steven Schveighoffer  
<schveiguy at yahoo.com> wrote:

> On Wed, 07 Dec 2011 04:00:34 -0500, Jonathan M Davis  
> <jmdavisProg at gmx.com> wrote:
>
>> On Wednesday, December 07, 2011 09:10:16 Martin Nowak wrote:
>>> On Wed, 07 Dec 2011 08:59:32 +0100, raojm <raojm at 91ne.com> 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
On a second thought that was wrong, D's AA do allocate one node per value,
so pointers to the values won't get invalidated. But simple optimizations
as adding a freelist would break this.
Depending on your application you should either lock access or
have a look at implementing a lock-free map.

>>
>> 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