diff options
Diffstat (limited to 'Source/WebCore/platform/graphics/android/context/RTree.cpp')
| -rw-r--r-- | Source/WebCore/platform/graphics/android/context/RTree.cpp | 598 |
1 files changed, 598 insertions, 0 deletions
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.cpp b/Source/WebCore/platform/graphics/android/context/RTree.cpp new file mode 100644 index 0000000..2e24c34 --- /dev/null +++ b/Source/WebCore/platform/graphics/android/context/RTree.cpp @@ -0,0 +1,598 @@ +/* + * Copyright 2012, The Android Open Source Project + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#define LOG_TAG "RTree" +#define LOG_NDEBUG 1 + +#include "config.h" + +#include "RTree.h" + +#include "AndroidLog.h" +#include "LinearAllocator.h" + +namespace WebCore { + +void* RecordingData::operator new(size_t size, LinearAllocator* allocator) +{ + return allocator->alloc(size); +} + +} + +namespace RTree { + +#ifdef DEBUG +static unsigned gID = 0; +#endif + +class Element; + +////////////////////////////////////////////////////////////////////// +// utility functions used by ElementList and Node + +static void recomputeBounds(int& minx, int& miny, + int& maxx, int& maxy, + unsigned& nbChildren, + Node**& children, int* area) +{ + // compute the bounds + + if (nbChildren) { + 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]->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) { + int w = maxx - minx; + int h = maxy - miny; + *area = w * h; + } +} + +int computeDeltaArea(Node* node, int& minx, int& miny, + int& maxx, int& 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; +} + +////////////////////////////////////////////////////////////////////// +// 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(WebCore::LinearAllocator* allocator, int M) + : m_allocator(allocator) +{ + m_maxChildren = M; + m_listA = new ElementList(M); + m_listB = new ElementList(M); + m_root = Node::create(this); +} + +RTree::~RTree() +{ + delete m_listA; + delete m_listB; + deleteNode(m_root); +} + +void RTree::insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload) +{ + Node* e = Node::create(this, bounds.x(), bounds.y(), + bounds.maxX(), bounds.maxY(), payload); + m_root->insert(e); +} + +void RTree::search(WebCore::IntRect& clip, Vector<WebCore::RecordingData*>&list) +{ + m_root->search(clip.x(), clip.y(), clip.maxX(), clip.maxY(), list); +} + +void RTree::remove(WebCore::IntRect& clip) +{ + m_root->remove(clip.x(), clip.y(), clip.maxX(), clip.maxY()); +} + +void RTree::display() +{ +#ifdef DEBUG + m_root->drawTree(); +#endif +} + +void* RTree::allocateNode() +{ + return m_allocator->alloc(sizeof(Node)); +} + +void RTree::deleteNode(Node* n) +{ + if (n) + n->~Node(); +} + +////////////////////////////////////////////////////////////////////// +// ElementList + +ElementList::ElementList(int size) + : m_nbChildren(0) + , m_minX(0) + , m_maxX(0) + , m_minY(0) + , m_maxY(0) + , m_area(0) + , m_didTighten(false) +{ + m_children = new Node*[size]; +} + +ElementList::~ElementList() +{ + delete[] m_children; +} + +void ElementList::add(Node* node) +{ + m_children[m_nbChildren] = node; + m_nbChildren++; + m_didTighten = false; +} + +void ElementList::tighten() +{ + if (m_didTighten) + return; + recomputeBounds(m_minX, m_minY, m_maxX, m_maxY, + m_nbChildren, m_children, &m_area); + m_didTighten = true; +} + +int ElementList::delta(Node* node) +{ + if (!m_didTighten) + tighten(); + return computeDeltaArea(node, m_minX, m_minY, m_maxX, m_maxY); +} + +void ElementList::removeAll() +{ + m_nbChildren = 0; + m_minX = 0; + m_maxX = 0; + m_minY = 0; + m_maxY = 0; + m_area = 0; + m_didTighten = false; +} + +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, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload) + : m_tree(t) + , m_parent(0) + , m_children(0) + , m_nbChildren(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; + if (m_payload) + m_payload->~RecordingData(); +} + +void Node::setParent(Node* node) +{ + m_parent = 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); +} + +Node* Node::findNode(Node* node) +{ + if (m_nbChildren == 0) + return m_parent ? m_parent : this; + + // pick the child whose bounds will be extended least + + Node* pick = m_children[0]; + int minIncrease = pick->delta(node); + for (unsigned int i = 1; i < m_nbChildren; i++) { + int increase = m_children[i]->delta(node); + if (increase < minIncrease) { + minIncrease = increase; + pick = m_children[i]; + } + } + + return pick->findNode(node); +} + +void Node::tighten() +{ + recomputeBounds(m_minX, m_minY, m_maxX, m_maxY, + m_nbChildren, m_children, 0); +} + +int Node::delta(Node* node) +{ + return computeDeltaArea(node, m_minX, m_minY, m_maxX, m_maxY); +} + +void Node::simpleAdd(Node* node) +{ + node->setParent(this); + if (!m_children) + m_children = new Node*[m_tree->m_maxChildren + 1]; + m_children[m_nbChildren] = node; + m_nbChildren++; +} + +void Node::add(Node* node) +{ + simpleAdd(node); + Node* NN = 0; + if (m_nbChildren > m_tree->m_maxChildren) + NN = split(); + + adjustTree(this, NN); +} + +void Node::remove(Node* node) +{ + int nodeIndex = -1; + for (unsigned int i = 0; i < m_nbChildren; i++) { + if (m_children[i] == node) { + nodeIndex = i; + break; + } + } + if (nodeIndex == -1) + return; + + // compact + for (unsigned int i = nodeIndex; i < m_nbChildren - 1; i++) + m_children[i] = m_children[i + 1]; + m_nbChildren--; +} + +void Node::destroy(int index) +{ + delete m_children[index]; + // compact + for (unsigned int i = index; i < m_nbChildren - 1; i++) + m_children[i] = m_children[i + 1]; + m_nbChildren--; +} + +void Node::removeAll() +{ + m_nbChildren = 0; + m_minX = 0; + m_maxX = 0; + m_minY = 0; + m_maxY = 0; +} + +Node* Node::split() +{ + // First, let's get the seeds + // 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 = 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->m_maxX - minElementX->m_minX; + int dy = maxElementY->m_maxY - minElementY->m_minY; + + // assign the two seeds... + Node* elementA = minElementX; + Node* elementB = maxElementX; + + if (dx < dy) { + elementA = minElementY; + elementB = maxElementY; + } + + // If we get the same element, just get the first and + // last element inserted... + if (elementA == elementB) { + elementA = m_children[0]; + 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; + ElementList* listB = m_tree->m_listB; + listA->removeAll(); + listB->removeAll(); + + listA->add(elementA); + listB->add(elementB); + + remove(elementA); + remove(elementB); + + // For any remaining elements, insert it into the list + // resulting in the smallest growth + 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->m_nbChildren < m_tree->m_maxChildren) + listA->add(node); + else if (dB < dA && listB->m_nbChildren < m_tree->m_maxChildren) + listB->add(node); + else { + ElementList* smallestList = + 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->m_nbChildren; i++) + simpleAdd(listA->m_children[i]); + + Node* NN = Node::create(m_tree); + for (unsigned int i = 0; i < listB->m_nbChildren; i++) + NN->simpleAdd(listB->m_children[i]); + NN->tighten(); + + return NN; +} + +bool Node::isRoot() +{ + return m_tree->m_root == this; +} + +void Node::adjustTree(Node* N, Node* NN) +{ + bool callParent = N->updateBounds(); + + if (N->isRoot() && NN) { + // build new root + Node* root = Node::create(m_tree); +#ifdef DEBUG + ALOGV("-> node %d created as new root", root->m_tid); +#endif + root->simpleAdd(N); + root->simpleAdd(NN); + root->tighten(); + m_tree->m_root = root; + return; + } + + if (N->isRoot()) + return; + + if (N->m_parent) { + if (NN) + N->m_parent->add(NN); + else if (callParent) + adjustTree(N->m_parent, 0); + } +} + +bool Node::updateBounds() +{ + int ominx = m_minX; + int ominy = m_minY; + int omaxx = m_maxX; + int omaxy = m_maxY; + tighten(); + if ((ominx != m_minX) + || (ominy != m_minY) + || (omaxx != m_maxX) + || (omaxy != m_maxY)) + return true; + return false; +} + +#ifdef DEBUG +static int gMaxLevel = 0; +static int gNbNodes = 0; +static int gNbElements = 0; + +void Node::drawTree(int level) +{ + if (level == 0) { + ALOGV("\n*** show tree ***\n"); + gMaxLevel = 0; + gNbNodes = 0; + gNbElements = 0; + } + + display(level); + for (unsigned int i = 0; i < m_nbChildren; i++) + { + m_children[i]->drawTree(level + 1); + } + + if (gMaxLevel < level) + gMaxLevel = level; + + if (!m_nbChildren) + gNbElements++; + else + gNbNodes++; + + if (level == 0) { + ALOGV("********************\n"); + ALOGV("Depth level %d, total bytes: %d, %d nodes, %d bytes (%d bytes/node), %d elements, %d bytes (%d bytes/node)", + gMaxLevel, gNbNodes * sizeof(Node) + gNbElements * sizeof(Element), + gNbNodes, gNbNodes * sizeof(Node), sizeof(Node), + gNbElements, gNbElements * sizeof(Element), sizeof(Element)); + } +} +#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) +{ + return ! (minx > m_maxX + || maxx < m_minX + || maxy < m_minY + || miny > 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(this->m_payload); + + 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); + } +} + +bool Node::inside(int minx, int miny, int maxx, int maxy) +{ + return (minx <= m_minX + && maxx >= m_maxX + && miny <= m_minY + && maxy >= m_maxY); +} + +void Node::remove(int minx, int miny, int maxx, int maxy) +{ + for (unsigned int i = 0; i < m_nbChildren; i++) { + if (m_children[i]->inside(minx, miny, maxx, maxy)) + destroy(i); + else if (m_children[i]->overlap(minx, miny, maxx, maxy)) + m_children[i]->remove(minx, miny, maxx, maxy); + } +} + +} // Namespace RTree |