Use a linear allocator for the RTree

Change-Id: I5e04c28a0c65378a26b1b99bcfeed4331591e265

2 files changed, 79 insertions, 62 deletions

diff --git a/Source/WebCore/platform/graphics/android/context/RTree.cpp b/Source/WebCore/platform/graphics/android/context/RTree.cpp
index 5ba4622..fef30b3 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.cpp
+++ b/Source/WebCore/platform/graphics/android/context/RTree.cpp
@@ -29,11 +29,15 @@
 #include "config.h"
 
 #include "RTree.h"
+
 #include "AndroidLog.h"
+#include "LinearAllocator.h"
 
 namespace RTree {
 
+#ifdef DEBUG
 static unsigned gID = 0;
+#endif
 
 class Element;
 
@@ -124,20 +128,22 @@ RTree::RTree(int M)
     m_maxChildren = M;
     m_listA = new ElementList(M);
     m_listB = new ElementList(M);
-    m_root = new Node(this);
+    m_allocator = new WebCore::LinearAllocator(sizeof(Node));
+    m_root = Node::create(this);
 }
 
 RTree::~RTree()
 {
     delete m_listA;
     delete m_listB;
-    delete m_root;
+    deleteNode(m_root);
+    delete m_allocator;
 }
 
 void RTree::insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload)
 {
-    Element* e = new Element(this, bounds.x(), bounds.y(),
-                             bounds.maxX(), bounds.maxY(), payload);
+    Node* e = Node::create(this, bounds.x(), bounds.y(),
+                           bounds.maxX(), bounds.maxY(), payload);
     m_root->insert(e);
 }
 
@@ -153,7 +159,22 @@ void RTree::remove(WebCore::IntRect& clip)
 
 void RTree::display()
 {
+#ifdef DEBUG
     m_root->drawTree();
+#endif
+}
+
+void* RTree::allocateNode()
+{
+    return m_allocator->alloc();
+}
+
+void RTree::deleteNode(Node* n)
+{
+    if (n) {
+        n->~Node();
+        m_allocator->dealloc(n);
+    }
 }
 
 //////////////////////////////////////////////////////////////////////
@@ -205,32 +226,40 @@ void ElementList::removeAll()
 }
 
 void ElementList::display() {
+#ifdef DEBUG
     for (unsigned int i = 0; i < m_nbChildren; i++)
         m_children[i]->display(0);
+#endif
 }
 
 //////////////////////////////////////////////////////////////////////
 // Node
 
-Node::Node(RTree* t)
+Node::Node(RTree* t, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload)
     : m_tree(t)
     , m_parent(0)
     , m_children(0)
     , m_nbChildren(0)
-    , m_minX(0)
-    , m_minY(0)
-    , m_maxX(0)
-    , m_maxY(0)
+    , m_payload(payload)
+    , m_minX(minx)
+    , m_minY(miny)
+    , m_maxX(maxx)
+    , m_maxY(maxy)
 #ifdef DEBUG
     , m_tid(gID++)
 #endif
 {
+#ifdef DEBUG
     ALOGV("-> New Node %d", m_tid);
+#endif
 }
 
 Node::~Node()
 {
+    for (unsigned i = 0; i < m_nbChildren; i++)
+        m_tree->deleteNode(m_children[i]);
     delete[] m_children;
+    delete m_payload;
 }
 
 void Node::setParent(Node* node)
@@ -241,8 +270,10 @@ void Node::setParent(Node* node)
 void Node::insert(Node* node)
 {
     Node* N = findNode(node);
+#ifdef DEBUG
     ALOGV("-> Insert Node %d (%d, %d) in node %d",
           node->m_tid, node->m_minX, node->m_minY, N->m_tid);
+#endif
     N->add(node);
 }
 
@@ -363,8 +394,10 @@ Node* Node::split()
         elementB = m_children[m_nbChildren - 1];
     }
 
+#ifdef DEBUG
     ALOGV("split Node %d, dx: %d dy: %d elem A is %d, elem B is %d",
         m_tid, dx, dy, elementA->m_tid, elementB->m_tid);
+#endif
 
     // Let's use some temporary lists to do the split
     ElementList* listA = m_tree->m_listA;
@@ -401,7 +434,7 @@ Node* Node::split()
     for (unsigned int i = 0; i < listA->m_nbChildren; i++)
         add(listA->m_children[i]);
 
-    Node* NN = new Node(m_tree);
+    Node* NN = Node::create(m_tree);
     for (unsigned int i = 0; i < listB->m_nbChildren; i++)
         NN->add(listB->m_children[i]);
 
@@ -417,8 +450,10 @@ void Node::adjustTree(Node* N, Node* NN)
 {
     if (N->isRoot() && NN) {
         // build new root
-        Node* root = new Node(m_tree);
+        Node* root = Node::create(m_tree);
+#ifdef DEBUG
         ALOGV("-> node %d created as new root", root->m_tid);
+#endif
         root->add(N);
         root->add(NN);
         m_tree->m_root = root;
@@ -437,15 +472,14 @@ static int gNbNodes = 0;
 static int gNbElements = 0;
 #endif
 
+#ifdef DEBUG
 void Node::drawTree(int level)
 {
     if (level == 0) {
         ALOGV("\n*** show tree ***\n");
-#ifdef DEBUG
         gMaxLevel = 0;
         gNbNodes = 0;
         gNbElements = 0;
-#endif
     }
 
     display(level);
@@ -454,7 +488,6 @@ void Node::drawTree(int level)
         m_children[i]->drawTree(level + 1);
     }
 
-#ifdef DEBUG
     if (gMaxLevel < level)
         gMaxLevel = level;
 
@@ -470,14 +503,16 @@ void Node::drawTree(int level)
                gNbNodes, gNbNodes * sizeof(Node), sizeof(Node),
                gNbElements, gNbElements * sizeof(Element), sizeof(Element));
     }
-#endif
 }
+#endif
 
+#ifdef DEBUG
 void Node::display(int level)
 {
     ALOGV("%*sNode %d - %d, %d, %d, %d (%d x %d)",
       2*level, "", m_tid, m_minX, m_minY, m_maxX, m_maxY, m_maxX - m_minX, m_maxY - m_minY);
 }
+#endif
 
 bool Node::overlap(int minx, int miny, int maxx, int maxy)
 {
@@ -490,7 +525,7 @@ bool Node::overlap(int minx, int miny, int maxx, int maxy)
 void Node::search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list)
 {
     if (isElement() && overlap(minx, miny, maxx, maxy))
-        list.append(((Element*)this)->m_payload);
+        list.append(this->m_payload);
 
     for (unsigned int i = 0; i < m_nbChildren; i++) {
         if (m_children[i]->overlap(minx, miny, maxx, maxy))
@@ -516,30 +551,4 @@ void Node::remove(int minx, int miny, int maxx, int maxy)
     }
 }
 
-//////////////////////////////////////////////////////////////////////
-// Element
-
-Element::Element(RTree* tree, int pminx, int pminy, int pmaxx, int pmaxy, WebCore::RecordingData* p)
-    : Node(tree)
-    , m_payload(p)
-{
-    m_minX = pminx;
-    m_minY = pminy;
-    m_maxX = pmaxx;
-    m_maxY = pmaxy;
-    ALOGV("-> New element %d (%d, %d) - (%d x %d)",
-          m_tid, m_minX, m_minY, m_maxX - m_minX, m_maxY - m_minY);
-}
-
-Element::~Element()
-{
-    delete m_payload;
-}
-
-void Element::display(int level)
-{
-    ALOGV("%*selement %d (%d, %d, %d, %d) - (%d x %d)", 2*level, "",
-          m_tid, m_minX, m_minY, m_maxX, m_maxY, m_maxX - m_minX, m_maxY - m_minY);
-}
-
-}
+} // Namespace RTree
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.h b/Source/WebCore/platform/graphics/android/context/RTree.h
index d7df750..6b53d55 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.h
+++ b/Source/WebCore/platform/graphics/android/context/RTree.h
@@ -32,6 +32,8 @@
 
 namespace WebCore {
 
+class LinearAllocator;
+
 class RecordingData {
 public:
     RecordingData(GraphicsOperation::Operation* ops, int orderBy)
@@ -46,7 +48,7 @@ public:
     GraphicsOperation::Operation* m_operation;
 };
 
-}
+} // namespace WebCore
 
 namespace RTree {
 
@@ -67,12 +69,16 @@ public:
     void remove(WebCore::IntRect& clip);
     void display();
 
+    void* allocateNode();
+    void deleteNode(Node* n);
+
 private:
 
     Node* m_root;
     unsigned m_maxChildren;
     ElementList* m_listA;
     ElementList* m_listB;
+    WebCore::LinearAllocator* m_allocator;
 
     friend class Node;
 };
@@ -104,16 +110,26 @@ class Node {
 public:
     static Node* gRoot;
 
-    Node(RTree* t);
-    virtual ~Node();
+    static Node* create(RTree* tree) {
+        return create(tree, 0, 0, 0, 0, 0);
+    }
+
+    static Node* create(RTree* tree, int minx, int miny, int maxx, int maxy,
+                        WebCore::RecordingData* payload) {
+        return new (tree->allocateNode()) Node(tree, minx, miny, maxx, maxy, payload);
+    }
+
+    ~Node();
 
     void insert(Node* n);
     void search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list);
     void remove(int minx, int miny, int maxx, int maxy);
-    void drawTree(int level = 0);
-    virtual void display(int level = 0);
+
+    // Intentionally not implemented as Node* is custom allocated, we don't want to use this
+    void operator delete(void*);
 
 private:
+    Node(RTree* tree, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload);
 
     void setParent(Node* n);
     Node* findNode(Node* n);
@@ -129,7 +145,7 @@ private:
     bool overlap(int minx, int miny, int maxx, int maxy);
     bool inside(int minx, int miny, int maxx, int maxy);
 
-    virtual bool isElement() { return false; }
+    bool isElement() { return m_payload; }
     bool isRoot();
 
 private:
@@ -140,6 +156,8 @@ private:
     Node** m_children;
     unsigned m_nbChildren;
 
+    WebCore::RecordingData* m_payload;
+
 public:
 
     int m_minX;
@@ -148,22 +166,12 @@ public:
     int m_maxY;
 
 #ifdef DEBUG
+    void drawTree(int level = 0);
+    void display(int level = 0);
     unsigned m_tid;
 #endif
 };
 
-class Element : public Node {
-public:
-
-    Element(RTree* tree, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload);
-    virtual ~Element();
-    virtual bool isElement() { return true; }
-
-    virtual void display(int level = 0);
-
-    WebCore::RecordingData* m_payload;
-};
-
-}
+} // namespace RTree
 
 #endif // RTree_h