| /* |
| * 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 |