Test multideque

cc/resources/resource_pool_unittest.cc

Index: cc/resources/resource_pool_unittest.cc
diff --git a/cc/resources/resource_pool_unittest.cc b/cc/resources/resource_pool_unittest.cc
index bde9d748b7e9f72218312ed9aa494b668bd4192e..9007d76bd43bd056b205cdcb9accee95939c5bdf 100644
--- a/cc/resources/resource_pool_unittest.cc
+++ b/cc/resources/resource_pool_unittest.cc
@@ -4,6 +4,9 @@
 
 #include "cc/resources/resource_pool.h"
 
+#include <iostream>
+#include <map>
+
 #include "base/run_loop.h"
 #include "base/thread_task_runner_handle.h"
 #include "cc/resources/resource_util.h"
@@ -218,5 +221,234 @@ TEST_F(ResourcePoolTest, UnusedResourcesEventuallyFreed) {
   EXPECT_EQ(0u, resource_pool_->GetTotalMemoryUsageForTesting());
 }
 
+struct TestResource {
+  explicit TestResource(const gfx::Size& size) { this->size = size; }
+
+  gfx::Size size;
+  // uint64_t content_id;
+};
+
+class TestQueueBase {
+ public:
+  virtual TestResource* Create(const gfx::Size& size) = 0;
+  virtual TestResource* Traverse(const gfx::Size& size) = 0;
+  virtual void AppendToUnused(TestResource* resource) = 0;
+  virtual void RemoveAll() = 0;
+};
+
+class TestDeque : public TestQueueBase {
+ public:
+  TestResource* Create(const gfx::Size& size) override {
+    return new TestResource(size);
+  }
+
+  // Test traversing logic from ResourcePool::AcquireResource.
+  TestResource* Traverse(const gfx::Size& size) override {
+    for (DQ::iterator it = unused_.begin(); it != unused_.end(); ++it) {
+      TestResource* resource = *it;
+      if (resource->size == size) {
+        unused_.erase(it);
+        return resource;
+      }
+    }
+
+    return nullptr;
+  }
+
+  void AppendToUnused(TestResource* resource) override {
+    unused_.push_front(resource);
+  }
+
+  void RemoveAll() override {
+    for (DQ::iterator it = unused_.begin(); it != unused_.end(); ++it) {
+      delete *it;
+    }
+    unused_.clear();
+  }
+
+ private:
+  typedef std::deque<TestResource*> DQ;
+  DQ unused_;
+};
+
+class TestMultiDeque : public TestQueueBase {
+ public:
+  TestResource* Create(const gfx::Size& size) override {
+    return new TestResource(size);
+  }
+
+  // Test traversing logic from ResourcePool::AcquireResource.
+  TestResource* Traverse(const gfx::Size& size) override {
+    Key key = std::make_pair(size.width(), size.height());
+    DQM::iterator kit = unused_.find(key);
+
+    if (kit != unused_.end()) {
+      DQ* dq = kit->second;
+
+      for (DQ::iterator it = dq->begin(); it != dq->end(); ++it) {
+        TestResource* resource = *it;
+        if (resource->size == size) {
+          dq->erase(it);
+          return resource;
+        }
+      }
+    }
+
+    return nullptr;
+  }
+
+  void AppendToUnused(TestResource* resource) override {
+    Key key = std::make_pair(resource->size.width(), resource->size.height());
+    DQM::iterator kit = unused_.find(key);
+    if (kit != unused_.end()) {
+      DQ* dq = kit->second;
+      dq->push_front(resource);
+    } else {
+      DQ* dq = new DQ;
+      dq->push_front(resource);
+      unused_[key] = dq;
+    }
+  }
+
+  void RemoveAll() override {
+    for (DQM::iterator kit = unused_.begin(); kit != unused_.end(); ++kit) {
+      DQ* dq = kit->second;
+      for (DQ::iterator it = dq->begin(); it != dq->end(); ++it) {
+        delete *it;
+      }
+      delete dq;
+    }
+    unused_.clear();
+  }
+
+ private:
+  typedef std::pair<int, int> Key;
+  typedef std::deque<TestResource*> DQ;
+  typedef std::map<Key, DQ*> DQM;
+  DQM unused_;
+};
+
+void DoQueueOperations(TestQueueBase* queue,
+                       int how_many,
+                       int tile_round_up,
+                       int tile_size_max,
+                       bool reverse_find) {
+  gfx::Size size;
+  int rounds = tile_size_max / tile_round_up;
+  const int r_max = rounds * rounds * how_many;
+  TestResource* resource[r_max];
+  // Create and append n resources.
+  int i = 0;
+  for (int w = tile_round_up; w <= tile_size_max; w += tile_round_up) {
+    for (int h = tile_round_up; h <= tile_size_max; h += tile_round_up) {
+      size = gfx::Size(w, h);
+      for (int j = 0; j < how_many; ++j)
+        resource[i++] = queue->Create(size);
+    }
+  }
+
+  for (i = 0; i < r_max; ++i)
+    queue->AppendToUnused(resource[i]);
+
+  // Find resource from unused.
+  TestResource* result = nullptr;
+  if (reverse_find) {
+    for (int w = tile_round_up; w <= tile_size_max; w += tile_round_up) {
+      for (int h = tile_round_up; h <= tile_size_max; h += tile_round_up) {
+        size = gfx::Size(w, h);
+        for (int j = 0; j < how_many; ++j) {
+          result = queue->Traverse(size);
+          EXPECT_NE(nullptr, result);
+          delete result;
+        }
+      }
+    }
+  } else {
+    for (int w = tile_size_max; w >= tile_round_up; w -= tile_round_up) {
+      for (int h = tile_size_max; h >= tile_round_up; h -= tile_round_up) {
+        size = gfx::Size(w, h);
+        for (int j = 0; j < how_many; ++j) {
+          result = queue->Traverse(size);
+          EXPECT_NE(nullptr, result);
+          delete result;
+        }
+      }
+    }
+  }
+}
+
+void RunTestQueueCommon(TestQueueBase* queue,
+                        std::string test_name,
+                        int how_many,
+                        int tile_round_up,
+                        int tile_size_max) {
+  // Actual Test {{
+  // Add resource size to be found at the end of queue.
+  base::TimeTicks start = base::TimeTicks::Now();
+  for (int k = 0; k < 10000; ++k) {
+    DoQueueOperations(queue, how_many, tile_round_up, tile_size_max, false);
+    DoQueueOperations(queue, how_many, tile_round_up, tile_size_max, true);
+  }
+  base::TimeDelta delta = base::TimeTicks::Now() - start;
+  LOG(INFO) << "\n" << test_name << " (" << delta.InMicroseconds() << " µs)";
+  // Actual Test }}
+}
+
+void RunTestDeque(std::string test_name,
+                  int how_many,
+                  int tile_round_up,
+                  int tile_size_max) {
+  TestDeque queue;
+  RunTestQueueCommon(&queue, test_name, how_many, tile_round_up, tile_size_max);
+}
+
+void RunTestMultiDeque(std::string test_name,
+                       int how_many,
+                       int tile_round_up,
+                       int tile_size_max) {
+  TestMultiDeque queue;
+  RunTestQueueCommon(&queue, test_name, how_many, tile_round_up, tile_size_max);
+}
+
+TEST_F(ResourcePoolTest, TestDequeSingle) {
+  RunTestDeque("TestDequeSingle", 1, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeSingle) {
+  RunTestMultiDeque("TestMultiDequeSingle", 1, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestDequeManyOfOneSize) {
+  RunTestDeque("TestDequeManyOfOneSize", 50, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeManyOfOneSize) {
+  RunTestMultiDeque("TestMultiDequeManyOfOneSize", 50, 64, 64);
+}
+
+TEST_F(ResourcePoolTest, TestDequeOneOfEachSize) {
+  RunTestDeque("TestDequeOneOfEachSize", 1, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeOneOfEachSize) {
+  RunTestMultiDeque("TestMultiDequeOneOfEachSize", 1, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestDequeManyOfEachSize) {
+  RunTestDeque("TestDequeManyOfEachSize", 5, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeManyOfEachSize) {
+  RunTestMultiDeque("TestMultiDequeManyOfEachSize", 5, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestDequeTooManyOfEachSize) {
+  RunTestDeque("TestDequeTooManyOfEachSize", 20, 64, 512);
+}
+
+TEST_F(ResourcePoolTest, TestMultiDequeTooManyOfEachSize) {
+  RunTestMultiDeque("TestMultiDequeTooManyOfEachSize", 20, 64, 512);
+}
+
 }  // namespace
 }  // namespace cc