GNOME Bugzilla – Bug 671327
HashSet.Iterator.remove() doesn't preserve iteration order
Last modified: 2012-03-06 21:11:24 UTC
Depending on the hash function being used, and the size of the HashSet, it's possible that calling iter.remove() on a HashSet iterator will cause the hash set to be resized and thus break the iteration order. This results in the loop not visiting every element of the set. Simple test case attached. I guess one solution could be to have HashSet.Iterator.remove() call a special remove_node_without_resizing() method on the HashSet, and then for the HashSet to be resized (if necessary) when the iterator's finalised, instead.
Created attachment 208966 [details] HashSet iteration test case Here's a simple test case. It creates a set of 50 consecutive integers, then iterates over it and removes all of them…except that not all of them are removed.
(In reply to comment #0) > I guess one solution could be to have HashSet.Iterator.remove() call a special > remove_node_without_resizing() method on the HashSet, and then for the HashSet > to be resized (if necessary) when the iterator's finalised, instead. That wouldn't work as the iterator might be invalidated in between: var iter = myset.iterator (); while (iter.next ()) { message ("Removing %u", iter.get ()); iter.remove (); } // Previously valid code - should be invalid? unowned Thread<bool> t = Thread.create<bool>(() => { myset.add(1234); return false; } iter = null; t.join(); myset.add(5678); I guess we can simply postpone resizing the set until Collection.add etc.
This problem has been fixed in the development version. The fix will be available in the next major software release. Thank you for your bug report. commit c4d157cdcd367f5d87e5a31de0bfcd838b7332cb Author: Maciej Piechotka <uzytkownik2@gmail.com> Date: Tue Mar 6 20:52:45 2012 +0000 Don't resize after deletion from hashtable in iterator, fixes #671327 Depending on sizes of array and hash function resize might alter the iteration order. It meant that some elements might not be visited and some might be visited twice. commit 90830d07d0ff0fe3424a71b5c0d8d02e3d679ebb Author: Maciej Piechotka <uzytkownik2@gmail.com> Date: Tue Mar 6 20:52:45 2012 +0000 Don't resize after deletion from hashtable in iterator, fixes #671327 Depending on sizes of array and hash function resize might alter the iteration order. It meant that some elements might not be visited and some might be visited twice.