cc: Change Nodes collection to use base::ContiguousContainer instead of deque.

cc/base/rtree.cc

 // Copyright (c) 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 <stdint.h>
 
+#include <algorithm>
 #include <cmath>
 
 #include "base/logging.h"
+#include "base/numerics/saturated_arithmetic.h"
 
 namespace cc {
 
-RTree::RTree() : num_data_elements_(0u) {}
+RTree::RTree() : num_data_elements_(0u), nodes_(sizeof(Node)) {}
 
 RTree::~RTree() {}
 
 RTree::Node* RTree::AllocateNodeAtLevel(int level) {
-  nodes_.push_back(Node());
-  Node& node = nodes_.back();
+  Node& node = nodes_.AllocateAndConstruct<Node>();
   node.num_children = 0;
   node.level = level;
   return &node;
 }
 
 RTree::Branch RTree::BuildRecursive(std::vector<Branch>* branches, int level) {
   // Only one branch.  It will be the root.
   if (branches->size() == 1)
     return (*branches)[0];
 
@@ skipping 36 matching lines @@
         }
       }
       Node* node = AllocateNodeAtLevel(level);
       node->num_children = 1;
       node->children[0] = (*branches)[current_branch];
 
       Branch branch;
       branch.bounds = (*branches)[current_branch].bounds;
       branch.subtree = node;
       ++current_branch;
+      int x = branch.bounds.x();
+      int y = branch.bounds.y();
+      int right = branch.bounds.right();
+      int bottom = branch.bounds.bottom();
       for (int k = 1; k < increment_by && current_branch < branches->size();
            ++k) {
-        branch.bounds.Union((*branches)[current_branch].bounds);
+        // We use a custom union instead of gfx::Rect::Union here, since this
+        // bypasses some empty checks and extra setters, which improves
+        // performance.
+        auto& bounds = (*branches)[current_branch].bounds;
+        x = std::min(x, bounds.x());
+        y = std::min(y, bounds.y());
+        right = std::max(right, bounds.right());
+        bottom = std::max(bottom, bounds.bottom());
+
         node->children[k] = (*branches)[current_branch];
         ++node->num_children;
         ++current_branch;
       }
+      branch.bounds.SetRect(x, y, base::SaturatedSubtraction(right, x),
+                            base::SaturatedSubtraction(bottom, y));
+
       DCHECK_LT(new_branch_index, current_branch);
       (*branches)[new_branch_index] = branch;
       ++new_branch_index;
     }
   }
   branches->resize(new_branch_index);
   return BuildRecursive(branches, level + 1);
 }
 
 void RTree::Search(const gfx::Rect& query, std::vector<size_t>* results) const {
@@ skipping 12 matching lines @@
         SearchRecursive(node->children[i].subtree, query, results);
     }
   }
 }
 
 gfx::Rect RTree::GetBounds() const {
   return root_.bounds;
 }
 
 }  // namespace cc