www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Can pointers to values inside associative arrays become invalid?

reply "Idan Arye" <GenericNPC gmail.com> writes:
I have an associative array, and I use the `in` operator to get a 
reference to a value inside it and store it in a pointer:

     int[string] aa;
     aa["myKey"] = 42;
     int* myPointer = "myKey" in aa;

Is it possible that due to rehashing or something D will decide 
to move the associative array's values around, resulting in 
`myPointer` no longer pointing to `aa["myKey"]`?
Jan 06 2015
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Tue, Jan 06, 2015 at 04:18:17PM +0000, Idan Arye via Digitalmars-d-learn
wrote:
 I have an associative array, and I use the `in` operator to get a
 reference to a value inside it and store it in a pointer:
 
     int[string] aa;
     aa["myKey"] = 42;
     int* myPointer = "myKey" in aa;
 
 Is it possible that due to rehashing or something D will decide to
 move the associative array's values around, resulting in `myPointer`
 no longer pointing to `aa["myKey"]`?
AFAIK, not in the current implementation. Each key/value pair is kept in its own bucket, and rehashing doesn't move the bucket's position in memory, only relinks it with the other hash structures. However, if you delete the key from the AA, you might have problems, as the current implementation will forcefully call GC.free() on the bucket, which makes any other pointers to it dangling. This is all implementation-dependent behaviour, though. If you need to rely on retaining pointers to keys/values, probably the better thing to do is to make your keys/values reference types, and keep the references to them instead of holding on to the pointer returned by 'in'. Relying on implementation-dependent behaviour is liable to come back to haunt you later when the implementation changes. T -- Latin's a dead language, as dead as can be; it killed off all the Romans, and now it's killing me! -- Schoolboy
Jan 06 2015
parent reply "Idan Arye" <GenericNPC gmail.com> writes:
On Tuesday, 6 January 2015 at 16:30:14 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:
 On Tue, Jan 06, 2015 at 04:18:17PM +0000, Idan Arye via 
 Digitalmars-d-learn wrote:
 I have an associative array, and I use the `in` operator to 
 get a
 reference to a value inside it and store it in a pointer:
 
     int[string] aa;
     aa["myKey"] = 42;
     int* myPointer = "myKey" in aa;
 
 Is it possible that due to rehashing or something D will 
 decide to
 move the associative array's values around, resulting in 
 `myPointer`
 no longer pointing to `aa["myKey"]`?
AFAIK, not in the current implementation. Each key/value pair is kept in its own bucket, and rehashing doesn't move the bucket's position in memory, only relinks it with the other hash structures. However, if you delete the key from the AA, you might have problems, as the current implementation will forcefully call GC.free() on the bucket, which makes any other pointers to it dangling. This is all implementation-dependent behaviour, though. If you need to rely on retaining pointers to keys/values, probably the better thing to do is to make your keys/values reference types, and keep the references to them instead of holding on to the pointer returned by 'in'. Relying on implementation-dependent behaviour is liable to come back to haunt you later when the implementation changes. T
I see... quite a shame there are no built-in data structures that provide forever-valid references to their members. Arrays can be reallocated, associative arrays can be rehased, and the stuff in std.collection does not expose the internal references...
Jan 06 2015
next sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Tue, Jan 06, 2015 at 05:39:50PM +0000, Idan Arye via Digitalmars-d-learn
wrote:
[...]
 I see... quite a shame there are no built-in data structures that
 provide forever-valid references to their members. Arrays can be
 reallocated, associative arrays can be rehased, and the stuff in
 std.collection does not expose the internal references...
Internal references are not exposed precisely because user code shouldn't depend on it. If you want forever-valid references to container members, just store references to your data instead of the data itself, e.g., MyStruct*[] (as long as you make sure your structs are allocated on the heap). Or use classes, which are reference types, e.g., elements of MyClass[] will be "forever valid". T -- The richest man is not he who has the most, but he who needs the least.
Jan 06 2015
prev sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/6/15 12:39 PM, Idan Arye wrote:
 On Tuesday, 6 January 2015 at 16:30:14 UTC, H. S. Teoh via
 Digitalmars-d-learn wrote:
 On Tue, Jan 06, 2015 at 04:18:17PM +0000, Idan Arye via
 Digitalmars-d-learn wrote:
 I have an associative array, and I use the `in` operator to get a
 reference to a value inside it and store it in a pointer:

     int[string] aa;
     aa["myKey"] = 42;
     int* myPointer = "myKey" in aa;

 Is it possible that due to rehashing or something D will decide to
 move the associative array's values around, resulting in `myPointer`
 no longer pointing to `aa["myKey"]`?
AFAIK, not in the current implementation. Each key/value pair is kept in its own bucket, and rehashing doesn't move the bucket's position in memory, only relinks it with the other hash structures. However, if you delete the key from the AA, you might have problems, as the current implementation will forcefully call GC.free() on the bucket, which makes any other pointers to it dangling. This is all implementation-dependent behaviour, though. If you need to rely on retaining pointers to keys/values, probably the better thing to do is to make your keys/values reference types, and keep the references to them instead of holding on to the pointer returned by 'in'. Relying on implementation-dependent behaviour is liable to come back to haunt you later when the implementation changes. T
I see... quite a shame there are no built-in data structures that provide forever-valid references to their members. Arrays can be reallocated, associative arrays can be rehased, and the stuff in std.collection does not expose the internal references...
Well, the AA will not move your value to another memory location unless you remove it. Even with a rehash. But this is NOT guaranteed, future implementations may be less friendly to it. In general, I would consider the value location to remain stable unless you modify the container in any way besides changing a value. -Steve
Jan 06 2015