X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=hashtable.h;h=b7cac67410c287004e9861d14db91c4afc0367dd;hb=9cf7a4cf4ce3caa33c27b4211db3d987a6b103ec;hp=81772a8f039addae09c726c0f7bf3e37ab626ef1;hpb=c9864e7765924f7236797648a1aa2fe3f4efd06f;p=c11tester.git

diff --git a/hashtable.h b/hashtable.h
index 81772a8f..b7cac674 100644
--- a/hashtable.h
+++ b/hashtable.h
@@ -258,6 +258,7 @@ public:
 	 */
 	_Val remove(_Key key) {
 		struct hashlistnode<_Key, _Val> *search;
+		struct hashlistnode<_Key, _Val> *replace;
 
 		/* HashTable cannot handle 0 as a key */
 		if (!key) {
@@ -280,14 +281,40 @@ public:
 			if (!search->key) {
 				if (!search->val)
 					break;
-			} else
-			if (equals(search->key, key)) {
-				_Val v=search->val;
-				//empty out this bin
-				search->val=(_Val) 1;
-				search->key=0;
-				size--;
-				return v;
+			} else {
+				// The case where an item is found
+				if (equals(search->key, key)) {
+					unsigned int j = index;
+					_Val v = search->val;
+					size--;
+
+					// Idea: keep bins contiguous
+					while (true) {
+						search->val = 0;
+						search->key = 0;
+
+						while (true) {
+							j = (j + 1) & capacitymask;
+							replace = &table[j];
+
+							if (!replace->key && !replace->val) {
+								return v;
+							}
+
+							unsigned int hash = hash_function(replace->key) & capacitymask;
+							if (index <= j && index < hash && hash <= j)
+								continue;
+							else if (index > j && (index < hash || hash <= j) )
+								continue;
+							else
+								break;
+						}
+
+						table[index] = table[j];
+						index = j;
+						search = &table[index];
+					}
+				}
 			}
 			index++;
 		} while (true);