Add some comments/cleanup

Change-Id: I71e41f1a76ac3e8e845d9636d57cf3896bb6ec0d

2 files changed, 192 insertions, 158 deletions

diff --git a/Source/WebCore/platform/graphics/android/context/RTree.cpp b/Source/WebCore/platform/graphics/android/context/RTree.cpp
index d2bc839..caa2fb4 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.cpp
+++ b/Source/WebCore/platform/graphics/android/context/RTree.cpp
@@ -48,18 +48,18 @@ static void recomputeBounds(int& minx, int& miny,
     // compute the bounds
 
     if (nbChildren) {
-        minx = children[0]->minx;
-        miny = children[0]->miny;
-        maxx = children[0]->maxx;
-        maxy = children[0]->maxy;
+        minx = children[0]->m_minX;
+        miny = children[0]->m_minY;
+        maxx = children[0]->m_maxX;
+        maxy = children[0]->m_maxY;
     }
 
     for (unsigned int i = 1; i < nbChildren; i++)
     {
-        minx = std::min(minx, children[i]->minx);
-        miny = std::min(miny, children[i]->miny);
-        maxx = std::max(maxx, children[i]->maxx);
-        maxy = std::max(maxy, children[i]->maxy);
+        minx = std::min(minx, children[i]->m_minX);
+        miny = std::min(miny, children[i]->m_minY);
+        maxx = std::max(maxx, children[i]->m_maxX);
+        maxy = std::max(maxy, children[i]->m_maxY);
     }
 
     if (area) {
@@ -69,13 +69,13 @@ static void recomputeBounds(int& minx, int& miny,
     }
 }
 
-int computeDeltaArea(Node* n, int& minx, int& miny,
+int computeDeltaArea(Node* node, int& minx, int& miny,
                      int& maxx, int& maxy)
 {
-    int newMinX = std::min(minx, n->minx);
-    int newMinY = std::min(miny, n->miny);
-    int newMaxX = std::max(maxx, n->maxx);
-    int newMaxY = std::max(maxy, n->maxy);
+    int newMinX = std::min(minx, node->m_minX);
+    int newMinY = std::min(miny, node->m_minY);
+    int newMaxX = std::max(maxx, node->m_maxX);
+    int newMaxY = std::max(maxy, node->m_maxY);
     int w = newMaxX - newMinX;
     int h = newMaxY - newMinY;
     return w * h;
@@ -83,145 +83,178 @@ int computeDeltaArea(Node* n, int& minx, int& miny,
 
 //////////////////////////////////////////////////////////////////////
 // RTree
+//////////////////////////////////////////////////////////////////////
+//
+// This is an implementation of the R-Tree data structure
+// "R-Trees - a dynamic index structure for spatial searching", Guttman(84)
+//
+// The structure works as follow -- elements have bounds, intermediate
+// nodes will also maintain bounds (the union of their children' bounds).
+//
+// Searching is simple -- we just traverse the tree comparing the bounds
+// until we find the elements we are interested in.
+//
+// Each node can have at most M children -- the performances / memory usage
+// is strongly impacted by a choice of a good M value (RTree::m_maxChildren).
+//
+// Inserting an element
+// --------------------
+//
+// To find the leaf node N where we can insert a new element (RTree::insert(),
+// Node::insert()), we need to traverse the tree, picking the branch where
+// adding the new element will result in the least growth of its bounds,
+// until we reach a leaf node (Node::findNode()).
+//
+// If the number of children of that leaf node is under M, we simply
+// insert it. Otherwise, if we reached maximum capacity for that leaf,
+// we split the list of children (Node::split()), creating two lists,
+// where each list' elements is as far as each other as possible
+// (to decrease the likelyhood of future splits).
+//
+// We can then assign one of the list to the original leaf node N, and
+// we then create a new node NN that we try to attach to N's parent.
+//
+// If N's parent is also full, we go up in the hierachy and repeat
+// (Node::adjustTree()).
+//
+//////////////////////////////////////////////////////////////////////
 
 RTree::RTree(int M)
 {
-    maxChildren = M;
-    listA = new ElementList(M);
-    listB = new ElementList(M);
-    root = new Node(this);
+    m_maxChildren = M;
+    m_listA = new ElementList(M);
+    m_listB = new ElementList(M);
+    m_root = new Node(this);
 }
 
 RTree::~RTree()
 {
-    delete listA;
-    delete listB;
-    delete root;
+    delete m_listA;
+    delete m_listB;
+    delete m_root;
 }
 
 void RTree::insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload)
 {
     Element* e = new Element(this, bounds.x(), bounds.y(),
                              bounds.maxX(), bounds.maxY(), payload);
-    root->insert(e);
+    m_root->insert(e);
 }
 
 void RTree::search(WebCore::IntRect& clip, Vector<WebCore::RecordingData*>&list)
 {
-    root->search(clip.x(), clip.y(), clip.maxX(), clip.maxY(), list);
+    m_root->search(clip.x(), clip.y(), clip.maxX(), clip.maxY(), list);
 }
 
 void RTree::display()
 {
-    root->drawTree();
+    m_root->drawTree();
 }
 
 //////////////////////////////////////////////////////////////////////
 // ElementList
 
 ElementList::ElementList(int size)
-    : nbChildren(0)
-    , minx(0)
-    , maxx(0)
-    , miny(0)
-    , maxy(0)
-    , area(0)
+    : m_nbChildren(0)
+    , m_minX(0)
+    , m_maxX(0)
+    , m_minY(0)
+    , m_maxY(0)
+    , m_area(0)
 {
-    children = new Node*[size];
+    m_children = new Node*[size];
 }
 
 ElementList::~ElementList()
 {
-    delete[] children;
+    delete[] m_children;
 }
 
-void ElementList::add(Node* n, bool doTighten)
+void ElementList::add(Node* node, bool doTighten)
 {
-    children[nbChildren] = n;
-    nbChildren++;
+    m_children[m_nbChildren] = node;
+    m_nbChildren++;
     if (doTighten)
         tighten();
 }
 
 void ElementList::tighten()
 {
-    recomputeBounds(minx, miny, maxx, maxy,
-                    nbChildren, children, &area);
+    recomputeBounds(m_minX, m_minY, m_maxX, m_maxY,
+                    m_nbChildren, m_children, &m_area);
 }
 
-int ElementList::delta(Node* n)
+int ElementList::delta(Node* node)
 {
-    return computeDeltaArea(n, minx, miny, maxx, maxy);
+    return computeDeltaArea(node, m_minX, m_minY, m_maxX, m_maxY);
 }
 
 void ElementList::removeAll()
 {
-    nbChildren = 0;
-    minx = 0;
-    maxx = 0;
-    miny = 0;
-    maxy = 0;
-    area = 0;
+    m_nbChildren = 0;
+    m_minX = 0;
+    m_maxX = 0;
+    m_minY = 0;
+    m_maxY = 0;
+    m_area = 0;
 }
 
 void ElementList::display() {
-    for (unsigned int i = 0; i < nbChildren; i++)
-        children[i]->display(0);
+    for (unsigned int i = 0; i < m_nbChildren; i++)
+        m_children[i]->display(0);
 }
 
 //////////////////////////////////////////////////////////////////////
 // Node
 
 Node::Node(RTree* t)
-    : tree(t)
-    , parent(0)
-    , children(0)
-    , nbChildren(0)
-    , minx(0)
-    , miny(0)
-    , maxx(0)
-    , maxy(0)
+    : m_tree(t)
+    , m_parent(0)
+    , m_children(0)
+    , m_nbChildren(0)
+    , m_minX(0)
+    , m_minY(0)
+    , m_maxX(0)
+    , m_maxY(0)
 #ifdef DEBUG
-    , tid(gID++)
+    , m_tid(gID++)
 #endif
 {
-#ifdef DEBUG
-    ALOGV("-> New Node %d", tid);
-#endif
+    ALOGV("-> New Node %d", m_tid);
 }
 
 Node::~Node()
 {
-    delete[] children;
+    delete[] m_children;
 }
 
 void Node::setParent(Node* node)
 {
-    parent = node;
+    m_parent = node;
 }
 
 void Node::insert(Node* node)
 {
     Node* N = findNode(node);
     ALOGV("-> Insert Node %d (%d, %d) in node %d",
-          node->tid, node->minx, node->miny, N->tid);
+          node->m_tid, node->m_minX, node->m_minY, N->m_tid);
     N->add(node);
 }
 
 Node* Node::findNode(Node* node)
 {
-    if (nbChildren == 0)
-        return parent ? parent : this;
+    if (m_nbChildren == 0)
+        return m_parent ? m_parent : this;
 
     // pick the child whose bounds will be extended least
 
-    Node* pick = children[0];
+    Node* pick = m_children[0];
     int minIncrease = pick->delta(node);
-    for (unsigned int i = 1; i < nbChildren; i++) {
-        int increase = children[i]->delta(node);
+    for (unsigned int i = 1; i < m_nbChildren; i++) {
+        int increase = m_children[i]->delta(node);
         if (increase < minIncrease) {
             minIncrease = increase;
-            pick = children[i];
+            pick = m_children[i];
         }
     }
 
@@ -230,24 +263,24 @@ Node* Node::findNode(Node* node)
 
 void Node::tighten()
 {
-    recomputeBounds(minx, miny, maxx, maxy,
-                    nbChildren, children, 0);
+    recomputeBounds(m_minX, m_minY, m_maxX, m_maxY,
+                    m_nbChildren, m_children, 0);
 }
 
 int Node::delta(Node* node)
 {
-    return computeDeltaArea(node, minx, miny, maxx, maxy);
+    return computeDeltaArea(node, m_minX, m_minY, m_maxX, m_maxY);
 }
 
 void Node::add(Node* node)
 {
     node->setParent(this);
-    if (!children)
-        children = new Node*[tree->maxChildren + 1];
-    children[nbChildren] = node;
-    nbChildren++;
+    if (!m_children)
+        m_children = new Node*[m_tree->m_maxChildren + 1];
+    m_children[m_nbChildren] = node;
+    m_nbChildren++;
     Node* NN = 0;
-    if (nbChildren > tree->maxChildren)
+    if (m_nbChildren > m_tree->m_maxChildren)
         NN = split();
     adjustTree(this, NN);
     tighten();
@@ -256,8 +289,8 @@ void Node::add(Node* node)
 void Node::remove(Node* node)
 {
     int nodeIndex = -1;
-    for (unsigned int i = 0; i < nbChildren; i++) {
-        if (children[i] == node) {
+    for (unsigned int i = 0; i < m_nbChildren; i++) {
+        if (m_children[i] == node) {
             nodeIndex = i;
             break;
         }
@@ -266,14 +299,14 @@ void Node::remove(Node* node)
         return;
 
     // compact
-    for (unsigned int i = nodeIndex; i < nbChildren-1; i++)
-        children[i] = children[i+1];
-    nbChildren--;
+    for (unsigned int i = nodeIndex; i < m_nbChildren - 1; i++)
+        m_children[i] = m_children[i + 1];
+    m_nbChildren--;
 }
 
 void Node::removeAll()
 {
-    nbChildren = 0;
+    m_nbChildren = 0;
 }
 
 Node* Node::split()
@@ -282,23 +315,23 @@ Node* Node::split()
     // The idea is to get elements as distant as possible
     // as we can, so that the resulting splitted lists
     // will be more likely to not overlap.
-    Node* minElementX = children[0];
-    Node* maxElementX = children[0];
-    Node* minElementY = children[0];
-    Node* maxElementY = children[0];
-    for (unsigned int i = 1; i < nbChildren; i++) {
-        if (children[i]->minx < minElementX->minx)
-            minElementX = children[i];
-        if (children[i]->miny < minElementY->miny)
-            minElementY = children[i];
-        if (children[i]->maxx >= maxElementX->maxx)
-            maxElementX = children[i];
-        if (children[i]->maxy >= maxElementY->maxy)
-            maxElementY = children[i];
+    Node* minElementX = m_children[0];
+    Node* maxElementX = m_children[0];
+    Node* minElementY = m_children[0];
+    Node* maxElementY = m_children[0];
+    for (unsigned int i = 1; i < m_nbChildren; i++) {
+        if (m_children[i]->m_minX < minElementX->m_minX)
+            minElementX = m_children[i];
+        if (m_children[i]->m_minY < minElementY->m_minY)
+            minElementY = m_children[i];
+        if (m_children[i]->m_maxX >= maxElementX->m_maxX)
+            maxElementX = m_children[i];
+        if (m_children[i]->m_maxY >= maxElementY->m_maxY)
+            maxElementY = m_children[i];
     }
 
-    int dx = maxElementX->maxx - minElementX->minx;
-    int dy = maxElementY->maxy - minElementY->miny;
+    int dx = maxElementX->m_maxX - minElementX->m_minX;
+    int dy = maxElementY->m_maxY - minElementY->m_minY;
 
     // assign the two seeds...
     Node* elementA = minElementX;
@@ -312,15 +345,16 @@ Node* Node::split()
     // If we get the same element, just get the first and
     // last element inserted...
     if (elementA == elementB) {
-        elementA = children[0];
-        elementB = children[nbChildren-1];
+        elementA = m_children[0];
+        elementB = m_children[m_nbChildren - 1];
     }
+
     ALOGV("split Node %d, dx: %d dy: %d elem A is %d, elem B is %d",
-        tid, dx, dy, elementA->tid, elementB->tid);
+        m_tid, dx, dy, elementA->m_tid, elementB->m_tid);
 
     // Let's use some temporary lists to do the split
-    ElementList* listA = tree->listA;
-    ElementList* listB = tree->listB;
+    ElementList* listA = m_tree->m_listA;
+    ElementList* listB = m_tree->m_listB;
     listA->removeAll();
     listB->removeAll();
 
@@ -332,55 +366,55 @@ Node* Node::split()
 
     // For any remaining elements, insert it into the list
     // resulting in the smallest growth
-    for (unsigned int i = 0; i < nbChildren; i++) {
-        Node* node = children[i];
+    for (unsigned int i = 0; i < m_nbChildren; i++) {
+        Node* node = m_children[i];
         int dA = listA->delta(node);
         int dB = listB->delta(node);
 
-        if (dA < dB && listA->nbChildren < tree->maxChildren)
+        if (dA < dB && listA->m_nbChildren < m_tree->m_maxChildren)
             listA->add(node);
-        else if (dB < dA && listB->nbChildren < tree->maxChildren)
+        else if (dB < dA && listB->m_nbChildren < m_tree->m_maxChildren)
             listB->add(node);
         else {
             ElementList* smallestList =
-                listA->nbChildren > listB->nbChildren ? listB : listA;
+                listA->m_nbChildren > listB->m_nbChildren ? listB : listA;
             smallestList->add(node);
         }
     }
 
     // Use the list to rebuild the nodes
     removeAll();
-    for (unsigned int i = 0; i < listA->nbChildren; i++)
-        add(listA->children[i]);
+    for (unsigned int i = 0; i < listA->m_nbChildren; i++)
+        add(listA->m_children[i]);
 
-    Node* NN = new Node(tree);
-    for (unsigned int i = 0; i < listB->nbChildren; i++)
-        NN->add(listB->children[i]);
+    Node* NN = new Node(m_tree);
+    for (unsigned int i = 0; i < listB->m_nbChildren; i++)
+        NN->add(listB->m_children[i]);
 
     return NN;
 }
 
 bool Node::isRoot()
 {
-    return tree->root == this;
+    return m_tree->m_root == this;
 }
 
 void Node::adjustTree(Node* N, Node* NN)
 {
     if (N->isRoot() && NN) {
         // build new root
-        Node* root = new Node(tree);
-        ALOGV("-> node %d created as new root", root->tid);
+        Node* root = new Node(m_tree);
+        ALOGV("-> node %d created as new root", root->m_tid);
         root->add(N);
         root->add(NN);
-        tree->root = root;
+        m_tree->m_root = root;
         return;
     }
     if (N->isRoot())
         return;
 
-    if (NN && N->parent)
-        N->parent->add(NN);
+    if (NN && N->m_parent)
+        N->m_parent->add(NN);
 }
 
 #ifdef DEBUG
@@ -401,16 +435,16 @@ void Node::drawTree(int level)
     }
 
     display(level);
-    for (unsigned int i = 0; i < nbChildren; i++)
+    for (unsigned int i = 0; i < m_nbChildren; i++)
     {
-        children[i]->drawTree(level+1);
+        m_children[i]->drawTree(level + 1);
     }
 
 #ifdef DEBUG
     if (gMaxLevel < level)
         gMaxLevel = level;
 
-    if (!nbChildren)
+    if (!m_nbChildren)
         gNbElements++;
     else
         gNbNodes++;
@@ -428,25 +462,25 @@ void Node::drawTree(int level)
 void Node::display(int level)
 {
     ALOGV("%*sNode %d - %d, %d, %d, %d (%d x %d)",
-      2*level, "", tid, minx, miny, maxx, maxy, maxx - minx, maxy - miny);
+      2*level, "", m_tid, m_minX, m_minY, m_maxX, m_maxY, m_maxX - m_minX, m_maxY - m_minY);
 }
 
 bool Node::overlap(int pminx, int pminy, int pmaxx, int pmaxy)
 {
-    return ! (pminx > maxx
-           || pmaxx < minx
-           || pmaxy < miny
-           || pminy > maxy);
+    return ! (pminx > m_maxX
+           || pmaxx < m_minX
+           || pmaxy < m_minY
+           || pminy > m_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)->payload);
+        list.append(((Element*)this)->m_payload);
 
-    for (unsigned int i = 0; i < nbChildren; i++) {
-        if (children[i]->overlap(minx, miny, maxx, maxy))
-            children[i]->search(minx, miny, maxx, maxy, list);
+    for (unsigned int i = 0; i < m_nbChildren; i++) {
+        if (m_children[i]->overlap(minx, miny, maxx, maxy))
+            m_children[i]->search(minx, miny, maxx, maxy, list);
     }
 }
 
@@ -455,25 +489,25 @@ void Node::search(int minx, int miny, int maxx, int maxy, Vector<WebCore::Record
 
 Element::Element(RTree* tree, int pminx, int pminy, int pmaxx, int pmaxy, WebCore::RecordingData* p)
     : Node(tree)
-    , payload(p)
+    , m_payload(p)
 {
-    minx = pminx;
-    miny = pminy;
-    maxx = pmaxx;
-    maxy = pmaxy;
+    m_minX = pminx;
+    m_minY = pminy;
+    m_maxX = pmaxx;
+    m_maxY = pmaxy;
     ALOGV("-> New element %d (%d, %d) - (%d x %d)",
-          tid, minx, miny, maxx-minx, maxy-miny);
+          m_tid, m_minX, m_minY, m_maxX - m_minX, m_maxY - m_minY);
 }
 
 Element::~Element()
 {
-    delete payload;
+    delete m_payload;
 }
 
 void Element::display(int level)
 {
     ALOGV("%*selement %d (%d, %d, %d, %d) - (%d x %d)", 2*level, "",
-          tid, minx, miny, maxx, maxy, maxx-minx, maxy-miny);
+          m_tid, m_minX, m_minY, m_maxX, m_maxY, m_maxX - m_minX, m_maxY - m_minY);
 }
 
 }
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.h b/Source/WebCore/platform/graphics/android/context/RTree.h
index 75704cb..5c2f021 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.h
+++ b/Source/WebCore/platform/graphics/android/context/RTree.h
@@ -66,10 +66,10 @@ public:
 
 private:
 
-    Node* root;
-    unsigned maxChildren;
-    ElementList* listA;
-    ElementList* listB;
+    Node* m_root;
+    unsigned m_maxChildren;
+    ElementList* m_listA;
+    ElementList* m_listB;
 
     friend class Node;
 };
@@ -85,16 +85,16 @@ public:
     void removeAll();
     void display();
 
-    Node** children;
-    unsigned nbChildren;
+    Node** m_children;
+    unsigned m_nbChildren;
 
 private:
 
-    int minx;
-    int maxx;
-    int miny;
-    int maxy;
-    int area;
+    int m_minX;
+    int m_maxX;
+    int m_minY;
+    int m_maxY;
+    int m_area;
 };
 
 class Node {
@@ -128,21 +128,21 @@ private:
 
 private:
 
-    RTree* tree;
-    Node* parent;
+    RTree* m_tree;
+    Node* m_parent;
 
-    Node** children;
-    unsigned nbChildren;
+    Node** m_children;
+    unsigned m_nbChildren;
 
 public:
 
-    int minx;
-    int miny;
-    int maxx;
-    int maxy;
+    int m_minX;
+    int m_minY;
+    int m_maxX;
+    int m_maxY;
 
 #ifdef DEBUG
-    unsigned tid;
+    unsigned m_tid;
 #endif
 };
 
@@ -155,7 +155,7 @@ public:
 
     virtual void display(int level = 0);
 
-    WebCore::RecordingData* payload;
+    WebCore::RecordingData* m_payload;
 };
 
 }