SkTDynamicHash: support remove() without needing Deleted().

tests/DynamicHashTest.cpp

 #include "Test.h"
 #include "SkTDynamicHash.h"
 
 namespace {
 
 struct Entry {
     int key;
     double value;
 };
 const int& GetKey(const Entry& entry) { return entry.key; }
@@ skipping 95 matching lines @@
     ASSERT(hash.find(1) != NULL);
     ASSERT(hash.find(1)->value == 2.0);
     ASSERT(hash.find(5) != NULL);
     ASSERT(hash.find(5)->value == 3.0);
 
     // These aren't in the hash.
     ASSERT(hash.find(2) == NULL);
     ASSERT(hash.find(9) == NULL);
 }
 
-static void test_remove(skiatest::Reporter* reporter) {
+static void test_easy_remove(skiatest::Reporter* reporter) {
     Hash hash(4);
     ASSERT(hash.capacity() == 4);
 
     // These collide.
     Entry a = { 1, 2.0 };
     Entry b = { 5, 3.0 };
-    Entry c = { 9, 4.0 };
 
     hash.add(&a);
+    ASSERT(hash.count() == 1);
+    ASSERT(hash.countCollisions(1) == 0);
+
     hash.add(&b);
-    hash.remove(1);
-    // a should be marked deleted, and b should still be findable.
+    ASSERT(hash.count() == 2);
+    ASSERT(hash.countCollisions(1) == 0);
+    ASSERT(hash.countCollisions(5) == 1);
 
-    ASSERT(hash.find(1) == NULL);
-    ASSERT(hash.find(5) != NULL);
-    ASSERT(hash.find(5)->value == 3.0);
+    hash.remove(5);
+    ASSERT(hash.count() == 1);
+    ASSERT(hash.countCollisions(1) == 0);
+}
 
-    // This will go in the same slot as 'a' did before.
-    ASSERT(hash.countCollisions(9) == 0);
+static void test_interesting_remove(skiatest::Reporter* reporter) {
+    Hash hash(8);
+    ASSERT(hash.capacity() == 8);
+
+    // These collide.
+    Entry a = { 1,  2.0 };
+    Entry b = { 9,  3.0 };
+    Entry c = { 17, 4.0 };
+    Entry d = { 25, 5.0 };
+
+    // This will trigger interesting behavior in remove.
+    hash.add(&a);
+    hash.add(&b);
     hash.add(&c);
-    ASSERT(hash.find(9) != NULL);
-    ASSERT(hash.find(9)->value == 4.0);
-    ASSERT(hash.find(5) != NULL);
-    ASSERT(hash.find(5)->value == 3.0);
+    hash.remove(9);
+
+    // a shouldn't have moved.
+    ASSERT(hash.find(1) != NULL);
+    ASSERT(hash.find(1)->value == 2.0);
+    ASSERT(hash.countCollisions(1) == 0);
+    // c should have moved into b's position.
+    ASSERT(hash.find(17) != NULL);
+    ASSERT(hash.find(17)->value == 4.0);
+    ASSERT(hash.countCollisions(17) == 1);
+
+    hash.add(&d);
+    // a shouldn't have moved.
+    ASSERT(hash.find(1) != NULL);
+    ASSERT(hash.find(1)->value == 2.0);
+    ASSERT(hash.countCollisions(1) == 0);
+    // c shouldn't have moved.
+    ASSERT(hash.find(17) != NULL);
+    ASSERT(hash.find(17)->value == 4.0);
+    ASSERT(hash.countCollisions(17) == 1);
+    // d's after both of them.
+    ASSERT(hash.find(25) != NULL);
+    ASSERT(hash.find(25)->value == 5.0);
+    ASSERT(hash.countCollisions(25) == 2);
 }
 
 static void test_dynamic_hash(skiatest::Reporter* reporter) {
     test_growth(reporter);
     test_add(reporter);
     test_lookup(reporter);
-    test_remove(reporter);
+    test_easy_remove(reporter);
+    test_interesting_remove(reporter);
 }
 
 #include "TestClassDef.h"
 DEFINE_TESTCLASS("DynamicHash", DynamicHashTestClass, test_dynamic_hash);