www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - efficient and safe way to iterate on associative array?

reply aki <aki google.com> writes:
Is it okay to modify associative array while iterating it?

import std.stdio;

void main() {
	string[string] hash = [ "k1":"v1", "k2":"v2" ];
	auto r = hash.byKeyValue();
	while(!r.empty) {
		auto key = r.front.key;
		auto value = r.front.value;
		r.popFront();
		writefln("key=%s, value=%s", key, value);
		// may not modify 'hash' here ?
		hash = null;
	}
}

I guess probably it's not.
Then, my question is are there an efficient and safe way to 
iterate on an associative array even if there are possibility to 
be modified while iterating?
I'm writing interpreter and want to make my language to be safe; 
even malicious script cannot fall it in 'core dump' state. It is 
okay if it causes undefined behavior like throw or instant exit 
from loop, but not crash.

Thanks, Aki.
Mar 04 2016
next sibling parent reply Minas Mina <minas_0 hotmail.co.uk> writes:
On Friday, 4 March 2016 at 13:53:22 UTC, aki wrote:
 Is it okay to modify associative array while iterating it?

 import std.stdio;

 void main() {
 	string[string] hash = [ "k1":"v1", "k2":"v2" ];
 	auto r = hash.byKeyValue();
 	while(!r.empty) {
 		auto key = r.front.key;
 		auto value = r.front.value;
 		r.popFront();
 		writefln("key=%s, value=%s", key, value);
 		// may not modify 'hash' here ?
 		hash = null;
 	}
 }

 I guess probably it's not.
 Then, my question is are there an efficient and safe way to 
 iterate on an associative array even if there are possibility 
 to be modified while iterating?
 I'm writing interpreter and want to make my language to be 
 safe; even malicious script cannot fall it in 'core dump' 
 state. It is okay if it causes undefined behavior like throw or 
 instant exit from loop, but not crash.

 Thanks, Aki.
I think what you can do is extract its contents to an array, iterate it and modify it as you like, and then insert back to another associative array. I don't think it's efficient but I don't know if it's possible to do something else.
Mar 04 2016
parent JR <sunspyre gmail.com> writes:
On Friday, 4 March 2016 at 14:16:55 UTC, Minas Mina wrote:
 On Friday, 4 March 2016 at 13:53:22 UTC, aki wrote:
 I think what you can do is extract its contents to an array, 
 iterate it and modify it as you like, and then insert back to 
 another associative array. I don't think it's efficient but I 
 don't know if it's possible to do something else.
You can populate an array of key values (here string, so string[]) of the entries to delete, then iterate through it afterwards and call .remove to clean up. http://dpaste.dzfl.pl/b63a8e8e5c3b
Mar 04 2016
prev sibling next sibling parent Mike Parker <aldacron gmail.com> writes:
On Friday, 4 March 2016 at 13:53:22 UTC, aki wrote:
 Is it okay to modify associative array while iterating it?

 import std.stdio;

 void main() {
 	string[string] hash = [ "k1":"v1", "k2":"v2" ];
 	auto r = hash.byKeyValue();
 	while(!r.empty) {
 		auto key = r.front.key;
 		auto value = r.front.value;
 		r.popFront();
 		writefln("key=%s, value=%s", key, value);
 		// may not modify 'hash' here ?
 		hash = null;
 	}
 }

 I guess probably it's not.
 Then, my question is are there an efficient and safe way to 
 iterate on an associative array even if there are possibility 
 to be modified while iterating?
 I'm writing interpreter and want to make my language to be 
 safe; even malicious script cannot fall it in 'core dump' 
 state. It is okay if it causes undefined behavior like throw or 
 instant exit from loop, but not crash.
It is not safe to modify an aa when iterating with .byKey, .byValue, or .byKeyValue. You can safely do it with .keys and .values, but these allocate so it isn't likely to be the most efficient. Your best bet if it's something you need to do frequently is probably what JR recommended.
Mar 04 2016
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/4/16 8:53 AM, aki wrote:
 Is it okay to modify associative array while iterating it?

 import std.stdio;

 void main() {
      string[string] hash = [ "k1":"v1", "k2":"v2" ];
      auto r = hash.byKeyValue();
      while(!r.empty) {
          auto key = r.front.key;
          auto value = r.front.value;
          r.popFront();
          writefln("key=%s, value=%s", key, value);
          // may not modify 'hash' here ?
          hash = null;
      }
 }

 I guess probably it's not.
 Then, my question is are there an efficient and safe way to iterate on
 an associative array even if there are possibility to be modified while
 iterating?
 I'm writing interpreter and want to make my language to be safe; even
 malicious script cannot fall it in 'core dump' state. It is okay if it
 causes undefined behavior like throw or instant exit from loop, but not
 crash.

 Thanks, Aki.
You cannot add or remove keys. You can modify values for existing keys. Note, in your code, this would not cause a problem, since setting hash to null just removes the reference from the local variable 'hash', it does not alter the AA in any way. In dcollections, all containers support "purging", or iterating through elements, removing the current element if desired before moving to the next. But I haven't touched this library in ages, I don't know if it still compiles even. -Steve
Mar 04 2016
parent aki <aki google.com> writes:
On Friday, 4 March 2016 at 16:46:35 UTC, Steven Schveighoffer 
wrote:
 You cannot add or remove keys. You can modify values for 
 existing keys.

 Note, in your code, this would not cause a problem, since 
 setting hash to null just removes the reference from the local 
 variable 'hash', it does not alter the AA in any way.

 In dcollections, all containers support "purging", or iterating 
 through elements, removing the current element if desired 
 before moving to the next. But I haven't touched this library 
 in ages, I don't know if it still compiles even.

 -Steve
Thank you for it. Now I know. I will copy and modify AA source to customize. (src/rt/aaA.d) I wonder what if D support safe variant like safeByKeyValue. Actually it seems easy (in aaA.d): bool _aaRangeEmpty(Range r) { return r.impl is null || r.idx == r.dim; } can be changed to: bool _aaRangeEmptySafe(Range r) { if(r.impl is null || r.idx >= r.dim) return true; if (!r.buckets[r.idx].filled) throw xxxException(); return false; } It can become safe by a cost of small overhead. -- Aki.
Mar 04 2016