On Wed, 07 Dec 2011 14:51:49 +0100, Steven Schveighoffer
<schvei...@yahoo.com> wrote:
On Wed, 07 Dec 2011 04:00:34 -0500, Jonathan M Davis
<jmdavisp...@gmx.com> wrote:
On Wednesday, December 07, 2011 09:10:16 Martin Nowak wrote:
On Wed, 07 Dec 2011 08:59:32 +0100, raojm <ra...@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
