cc: Change RTree nodes container to be a vector (with reserve).

cc/base/rtree_unittest.cc

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/base/rtree.h"
 
 #include <stddef.h>
 
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace cc {
 
+TEST(RTreeTest, ReserveNodesDoesntDcheck) {
+  // Make sure that anywhere between 0 and 1000 rects, our reserve math in rtree
+  // is correct. (This test would DCHECK if broken either in
+  // RTree::AllocateNodeAtLevel, indicating that the capacity calculation was
+  // too small or in RTree::Build, indicating the capacity was too large).
+  for (int i = 0; i < 1000; ++i) {
+    std::vector<gfx::Rect> rects;
+    for (int j = 0; j < i; ++j)
+      rects.push_back(gfx::Rect(j, i, 1, 1));
+    RTree rtree;
+    rtree.Build(rects);
+  }
+}
+
 TEST(RTreeTest, NoOverlap) {
   std::vector<gfx::Rect> rects;
   for (int y = 0; y < 50; ++y) {
     for (int x = 0; x < 50; ++x) {
       rects.push_back(gfx::Rect(x, y, 1, 1));
     }
   }
 
   RTree rtree;
   rtree.Build(rects);
@@ skipping 65 matching lines @@
   rects.push_back(gfx::Rect(0, 0, 10, 10));
   rects.push_back(gfx::Rect(5, 5, 5, 5));
 
   RTree rtree;
   rtree.Build(rects);
 
   ASSERT_EQ(gfx::Rect(0, 0, 10, 10), rtree.GetBounds());
 }
 
 }  // namespace cc