Counterproposal to 182733007: Add iterator to SkTDynamicHash

tests/DynamicHashTest.cpp

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkTDynamicHash.h"
 #include "Test.h"
 
@@ skipping 17 matching lines @@
     int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
 
 private:
     typedef SkTDynamicHash<Entry, int, GetKey, GetHash, AreEqual> INHERITED;
 };
 
 }  // namespace
 
 #define ASSERT(x) REPORTER_ASSERT(reporter, x)
 
-static void test_growth(skiatest::Reporter* reporter) {
+DEF_TEST(DynamicHash_growth, reporter) {
     Entry a = { 1, 2.0 };
     Entry b = { 2, 3.0 };
     Entry c = { 3, 4.0 };
     Entry d = { 4, 5.0 };
     Entry e = { 5, 6.0 };
 
     Hash hash;
     ASSERT(hash.capacity() == 0);
 
     hash.add(&a);
     ASSERT(hash.capacity() == 4);
 
     hash.add(&b);
     ASSERT(hash.capacity() == 4);
 
     hash.add(&c);
     ASSERT(hash.capacity() == 4);
 
     hash.add(&d);
     ASSERT(hash.capacity() == 8);
 
     hash.add(&e);
     ASSERT(hash.capacity() == 8);
 
     ASSERT(hash.count() == 5);
 }
 
-static void test_add(skiatest::Reporter* reporter) {
+DEF_TEST(DynamicHash_add, reporter) {
     Hash hash;
     Entry a = { 1, 2.0 };
     Entry b = { 2, 3.0 };
 
     ASSERT(hash.count() == 0);
     hash.add(&a);
     ASSERT(hash.count() == 1);
     hash.add(&b);
     ASSERT(hash.count() == 2);
 }
 
-static void test_lookup(skiatest::Reporter* reporter) {
+DEF_TEST(DynamicHash_lookup, reporter) {
     Hash hash;
 
     // These collide.
     Entry a = { 1, 2.0 };
     Entry b = { 5, 3.0 };
 
     // Before we insert anything, nothing can collide.
     ASSERT(hash.countCollisions(1) == 0);
     ASSERT(hash.countCollisions(5) == 0);
     ASSERT(hash.countCollisions(9) == 0);
@@ skipping 14 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) {
+DEF_TEST(DynamicHash_remove, reporter) {
     Hash hash;
 
     // These collide.
     Entry a = { 1, 2.0 };
     Entry b = { 5, 3.0 };
     Entry c = { 9, 4.0 };
 
     hash.add(&a);
     hash.add(&b);
     hash.remove(1);
     // a should be marked deleted, and b should still be findable.
 
     ASSERT(hash.find(1) == NULL);
     ASSERT(hash.find(5) != NULL);
     ASSERT(hash.find(5)->value == 3.0);
 
     // This will go in the same slot as 'a' did before.
     ASSERT(hash.countCollisions(9) == 0);
     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);
 }
 
-DEF_TEST(DynamicHash, reporter) {
-    test_growth(reporter);
-    test_add(reporter);
-    test_lookup(reporter);
-    test_remove(reporter);
+DEF_TEST(DynamicHash_iterator, reporter) {
+    Hash hash;
+
+    int count = 0;
+    // this should fall out of loop immediately
+    for (Hash::Iter iter(&hash); !iter.done(); ++iter) {

[egdaniel, 2014/03/04 23:56:34]

Part of me feels like this done() function name is not commonly used in
iterators and thus may be less obvious when trying to use. But then again it
really isn't much different from a begin/end construct, just different names. So
I can be swayed either way.

[mtklein, 2014/03/05 00:13:05]

Yeah, I feel you.  I think .done() is actually the common idiom in Skia.  Try a
git grep done\(\) to have a look.  I'd have stuck with operator bool(), but I
realized that made the code inside Iter itself really hard to follow.

+        ++count;
+    }
+    ASSERT(0 == count);
+
+    // These collide.
+    Entry a = { 1, 2.0 };
+    Entry b = { 5, 3.0 };
+    Entry c = { 9, 4.0 };
+
+    hash.add(&a);
+    hash.add(&b);
+    hash.add(&c);
+
+    // should see all 3 unique keys when iterating over hash
+    count = 0;
+    int keys[3] = {0, 0, 0};
+    for (Hash::Iter iter(&hash); !iter.done(); ++iter) {
+        int key = (*iter).key;
+        keys[count] = key;
+        ASSERT(hash.find(key) != NULL);
+        ++count;
+    }
+    ASSERT(3 == count);
+    ASSERT(keys[0] != keys[1]);
+    ASSERT(keys[0] != keys[2]);
+    ASSERT(keys[1] != keys[2]);
+
+    // should see 2 unique keys when iterating over hash that aren't 1
+    hash.remove(1);
+    count = 0;
+    memset(keys,0,sizeof(keys));
+    for (Hash::Iter iter(&hash); !iter.done(); ++iter) {
+        int key = (*iter).key;
+        keys[count] = key;
+        ASSERT(key != 1);
+        ASSERT(hash.find(key) != NULL);
+        ++count;
+    }
+    ASSERT(2 == count);
+    ASSERT(keys[0] != keys[1]);
 }
+