[libgee/0.6] Don't resize after deletion from hashtable in iterator, fixes #671327

[Maciej Marcin Piechotka <mpiechotka src gnome org>]

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.

 gee/hashmap.vala |   49 +++++++++++++++++++++++++++++--------------------
 gee/hashset.vala |   37 ++++++++++++++++++++++---------------
 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;
 		}