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.

2 files changed, 51 insertions, 35 deletions

diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index de4e990..59766f4 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -200,26 +200,11 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 	 * {@inheritDoc}
 	 */
 	public override bool unset (K key, out V? value = null) {
-		Node<K,V>** node = lookup_node (key);
-		if (*node != null) {
-			Node<K,V> next = (owned) (*node)->next;
-
-			if (&value != null) {
-				value = (owned) (*node)->value;
-			}
-
-			(*node)->key = null;
-			(*node)->value = null;
-			delete *node;
-
-			*node = (owned) next;
-
-			_nnodes--;
-			resize ();
-			_stamp++;
-			return true;
+		bool b = unset_helper (key, out value);
+		if(b) {
+			resize();
 		}
-		return false;
+		return b;
 	}
 
 	/**
@@ -246,7 +231,31 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		return new MapIterator<K,V> (this);
 	}
 
-	private void resize () {
+	private inline bool unset_helper (K key, out V? value = null) {
+		Node<K,V>** node = lookup_node (key);
+		if (*node != null) {
+			Node<K,V> next = (owned) (*node)->next;
+
+			if (&value != NULL) {
+				value = (owned) (*node)->value;
+			}
+
+			(*node)->key = null;
+			(*node)->value = null;
+			delete *node;
+
+			*node = (owned) next;
+
+			_nnodes--;
+			_stamp++;
+			return true;
+		} else {
+			value = null;
+		}
+		return false;
+	}
+
+	private inline void resize () {
 		if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 		    (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
 			int new_array_size = (int) SpacedPrimes.closest (_nnodes);
diff --git a/gee/hashset.vala b/gee/hashset.vala
index 717e5e2..2d83511 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -128,22 +128,11 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 	 * {@inheritDoc}
 	 */
 	public override bool remove (G key) {
-		Node<G>** node = lookup_node (key);
-		if (*node != null) {
-			assert (*node != null);
-			Node<G> next = (owned) (*node)->next;
-
-			(*node)->key = null;
-			delete *node;
-
-			*node = (owned) next;
-
-			_nnodes--;
+		bool b = remove_helper(key);
+		if(b) {
 			resize ();
-			_stamp++;
-			return true;
 		}
-		return false;
+		return b;
 	}
 
 	/**
@@ -162,6 +151,24 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 		resize ();
 	}
 
+	private inline bool remove_helper (G key) {
+		Node<G>** node = lookup_node (key);
+		if (*node != null) {
+			assert (*node != null);
+			Node<G> next = (owned) (*node)->next;
+
+			(*node)->key = null;
+			delete *node;
+
+			*node = (owned) next;
+
+			_nnodes--;
+			_stamp++;
+			return true;
+		}
+		return false;
+	}
+
 	private void resize () {
 		if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 		    (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
@@ -260,7 +267,7 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 			assert (_stamp == _set._stamp);
 			assert (_node != null);
 			has_next ();
-			_set.remove (_node.key);
+			_set.remove_helper (_node.key);
 			_node = null;
 			_stamp = _set._stamp;
 		}