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

cc/base/rtree.h

 // 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.
 
 #ifndef CC_BASE_RTREE_H_
 #define CC_BASE_RTREE_H_
 
 #include <stddef.h>
 #include <stdint.h>
 
 #include <vector>
 
 #include "cc/base/cc_export.h"
-#include "cc/base/contiguous_container.h"
 #include "ui/gfx/geometry/rect.h"
 
 namespace cc {
 
 // The following description and most of the implementation is borrowed from
 // Skia's SkRTree implementation.
 //
 // An R-Tree implementation. In short, it is a balanced n-ary tree containing a
 // hierarchy of bounding rectangles.
 //
@@ skipping 29 matching lines @@
         continue;
 
       branches.push_back(Branch());
       Branch& branch = branches.back();
       branch.bounds = bounds;
       branch.index = i;
     }
 
     num_data_elements_ = branches.size();
     if (num_data_elements_ == 1u) {
+      nodes_.reserve(1);
       Node* node = AllocateNodeAtLevel(0);
       node->num_children = 1;
       node->children[0] = branches[0];
       root_.subtree = node;
       root_.bounds = branches[0].bounds;
     } else if (num_data_elements_ > 1u) {
+      // Determine a reasonable upper bound on the number of nodes to prevent
+      // reallocations. This is basically (n**d - 1) / (n - 1), which is the
+      // number of nodes in a complete tree with n branches at each node. In the
+      // code n = |branch_count|, d = |depth|. However, we normally would have
+      // kMaxChildren branch factor, but that can be broken if some children
+      // don't have enough nodes. That can happen for at most kMinChildren nodes
+      // (since otherwise, we'd create a new node).
+      size_t branch_count = kMaxChildren;
+      double depth = log(branches.size()) / log(branch_count);
+      size_t node_count =
+          static_cast<size_t>((std::pow(branch_count, depth) - 1) /
+                              (branch_count - 1)) +
+          kMinChildren;

[danakj, 2016/12/19 22:20:50]

clang format why

[vmpstr, 2016/12/19 22:51:27]

v_v

+      nodes_.reserve(node_count);
+
       root_ = BuildRecursive(&branches, 0);
     }
+    // We should've wasted at most kMinChildren nodes.
+    DCHECK_LE(nodes_.capacity() - nodes_.size(), kMinChildren);
   }
 
   template <typename Container>
   void Build(const Container& items) {
     Build(items, [](const gfx::Rect& bounds) { return bounds; });
   }
 
   void Search(const gfx::Rect& query, std::vector<size_t>* results) const;
 
   gfx::Rect GetBounds() const;
 
  private:
   // These values were empirically determined to produce reasonable performance
   // in most cases.
-  enum { MIN_CHILDREN = 6, MAX_CHILDREN = 11 };
+  enum { kMinChildren = 6 };
+  enum { kMaxChildren = 11 };
 
   struct Node;
   struct Branch {
     // When the node level is 0, then the node is a leaf and the branch has a
     // valid index pointing to an element in the vector that was used to build
     // this rtree. When the level is not 0, it's an internal node and it has a
     // valid subtree pointer.
     union {
       Node* subtree;
       size_t index;
     };
     gfx::Rect bounds;
   };
 
   struct Node {
     uint16_t num_children;
     uint16_t level;
-    Branch children[MAX_CHILDREN];
+    Branch children[kMaxChildren];
   };
 
   void SearchRecursive(Node* root,
                        const gfx::Rect& query,
                        std::vector<size_t>* results) const;
 
   // Consumes the input array.
   Branch BuildRecursive(std::vector<Branch>* branches, int level);
   Node* AllocateNodeAtLevel(int level);
 
   // This is the count of data elements (rather than total nodes in the tree)
   size_t num_data_elements_;
   Branch root_;
-  ContiguousContainer<Node> nodes_;
+  std::vector<Node> nodes_;
 };
 
 }  // namespace cc
 
 #endif  // CC_BASE_RTREE_H_