1 /* 2 * Copyright 2012, The Android Open Source Project 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * * Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * * Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #define LOG_TAG "RTree" 27 #define LOG_NDEBUG 1 28 29 #include "config.h" 30 31 #include "RTree.h" 32 33 #include "AndroidLog.h" 34 #include <utils/LinearAllocator.h> 35 36 namespace WebCore { 37 38 void* RecordingData::operator new(size_t size, android::LinearAllocator* allocator) 39 { 40 return allocator->alloc(size); 41 } 42 43 } 44 45 namespace RTree { 46 47 #ifdef DEBUG 48 static unsigned gID = 0; 49 #endif 50 51 class Element; 52 53 ////////////////////////////////////////////////////////////////////// 54 // utility functions used by ElementList and Node 55 56 static void recomputeBounds(int& minx, int& miny, 57 int& maxx, int& maxy, 58 unsigned& nbChildren, 59 Node**& children, int* area) 60 { 61 // compute the bounds 62 63 if (nbChildren) { 64 minx = children[0]->m_minX; 65 miny = children[0]->m_minY; 66 maxx = children[0]->m_maxX; 67 maxy = children[0]->m_maxY; 68 } 69 70 for (unsigned int i = 1; i < nbChildren; i++) 71 { 72 minx = std::min(minx, children[i]->m_minX); 73 miny = std::min(miny, children[i]->m_minY); 74 maxx = std::max(maxx, children[i]->m_maxX); 75 maxy = std::max(maxy, children[i]->m_maxY); 76 } 77 78 if (area) { 79 int w = maxx - minx; 80 int h = maxy - miny; 81 *area = w * h; 82 } 83 } 84 85 int computeDeltaArea(Node* node, int& minx, int& miny, 86 int& maxx, int& maxy) 87 { 88 int newMinX = std::min(minx, node->m_minX); 89 int newMinY = std::min(miny, node->m_minY); 90 int newMaxX = std::max(maxx, node->m_maxX); 91 int newMaxY = std::max(maxy, node->m_maxY); 92 int w = newMaxX - newMinX; 93 int h = newMaxY - newMinY; 94 return w * h; 95 } 96 97 ////////////////////////////////////////////////////////////////////// 98 // RTree 99 ////////////////////////////////////////////////////////////////////// 100 // 101 // This is an implementation of the R-Tree data structure 102 // "R-Trees - a dynamic index structure for spatial searching", Guttman(84) 103 // 104 // The structure works as follow -- elements have bounds, intermediate 105 // nodes will also maintain bounds (the union of their children' bounds). 106 // 107 // Searching is simple -- we just traverse the tree comparing the bounds 108 // until we find the elements we are interested in. 109 // 110 // Each node can have at most M children -- the performances / memory usage 111 // is strongly impacted by a choice of a good M value (RTree::m_maxChildren). 112 // 113 // Inserting an element 114 // -------------------- 115 // 116 // To find the leaf node N where we can insert a new element (RTree::insert(), 117 // Node::insert()), we need to traverse the tree, picking the branch where 118 // adding the new element will result in the least growth of its bounds, 119 // until we reach a leaf node (Node::findNode()). 120 // 121 // If the number of children of that leaf node is under M, we simply 122 // insert it. Otherwise, if we reached maximum capacity for that leaf, 123 // we split the list of children (Node::split()), creating two lists, 124 // where each list' elements is as far as each other as possible 125 // (to decrease the likelyhood of future splits). 126 // 127 // We can then assign one of the list to the original leaf node N, and 128 // we then create a new node NN that we try to attach to N's parent. 129 // 130 // If N's parent is also full, we go up in the hierachy and repeat 131 // (Node::adjustTree()). 132 // 133 ////////////////////////////////////////////////////////////////////// 134 135 RTree::RTree(android::LinearAllocator* allocator, int M) 136 : m_allocator(allocator) 137 { 138 m_maxChildren = M; 139 m_listA = new ElementList(M); 140 m_listB = new ElementList(M); 141 m_root = Node::create(this); 142 } 143 144 RTree::~RTree() 145 { 146 delete m_listA; 147 delete m_listB; 148 deleteNode(m_root); 149 } 150 151 void RTree::insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload) 152 { 153 Node* e = Node::create(this, bounds.x(), bounds.y(), 154 bounds.maxX(), bounds.maxY(), payload); 155 m_root->insert(e); 156 } 157 158 void RTree::search(WebCore::IntRect& clip, Vector<WebCore::RecordingData*>&list) 159 { 160 m_root->search(clip.x(), clip.y(), clip.maxX(), clip.maxY(), list); 161 } 162 163 void RTree::remove(WebCore::IntRect& clip) 164 { 165 m_root->remove(clip.x(), clip.y(), clip.maxX(), clip.maxY()); 166 } 167 168 void RTree::display() 169 { 170 #ifdef DEBUG 171 m_root->drawTree(); 172 #endif 173 } 174 175 void* RTree::allocateNode() 176 { 177 return m_allocator->alloc(sizeof(Node)); 178 } 179 180 void RTree::deleteNode(Node* n) 181 { 182 if (n) 183 n->~Node(); 184 } 185 186 ////////////////////////////////////////////////////////////////////// 187 // ElementList 188 189 ElementList::ElementList(int size) 190 : m_nbChildren(0) 191 , m_minX(0) 192 , m_maxX(0) 193 , m_minY(0) 194 , m_maxY(0) 195 , m_area(0) 196 , m_didTighten(false) 197 { 198 m_children = new Node*[size]; 199 } 200 201 ElementList::~ElementList() 202 { 203 delete[] m_children; 204 } 205 206 void ElementList::add(Node* node) 207 { 208 m_children[m_nbChildren] = node; 209 m_nbChildren++; 210 m_didTighten = false; 211 } 212 213 void ElementList::tighten() 214 { 215 if (m_didTighten) 216 return; 217 recomputeBounds(m_minX, m_minY, m_maxX, m_maxY, 218 m_nbChildren, m_children, &m_area); 219 m_didTighten = true; 220 } 221 222 int ElementList::delta(Node* node) 223 { 224 if (!m_didTighten) 225 tighten(); 226 return computeDeltaArea(node, m_minX, m_minY, m_maxX, m_maxY); 227 } 228 229 void ElementList::removeAll() 230 { 231 m_nbChildren = 0; 232 m_minX = 0; 233 m_maxX = 0; 234 m_minY = 0; 235 m_maxY = 0; 236 m_area = 0; 237 m_didTighten = false; 238 } 239 240 void ElementList::display() { 241 #ifdef DEBUG 242 for (unsigned int i = 0; i < m_nbChildren; i++) 243 m_children[i]->display(0); 244 #endif 245 } 246 247 ////////////////////////////////////////////////////////////////////// 248 // Node 249 250 Node::Node(RTree* t, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload) 251 : m_tree(t) 252 , m_parent(0) 253 , m_children(0) 254 , m_nbChildren(0) 255 , m_payload(payload) 256 , m_minX(minx) 257 , m_minY(miny) 258 , m_maxX(maxx) 259 , m_maxY(maxy) 260 #ifdef DEBUG 261 , m_tid(gID++) 262 #endif 263 { 264 #ifdef DEBUG 265 ALOGV("-> New Node %d", m_tid); 266 #endif 267 } 268 269 Node::~Node() 270 { 271 for (unsigned i = 0; i < m_nbChildren; i++) 272 m_tree->deleteNode(m_children[i]); 273 delete[] m_children; 274 if (m_payload) 275 m_payload->~RecordingData(); 276 } 277 278 void Node::setParent(Node* node) 279 { 280 m_parent = node; 281 } 282 283 void Node::insert(Node* node) 284 { 285 Node* N = findNode(node); 286 #ifdef DEBUG 287 ALOGV("-> Insert Node %d (%d, %d) in node %d", 288 node->m_tid, node->m_minX, node->m_minY, N->m_tid); 289 #endif 290 N->add(node); 291 } 292 293 Node* Node::findNode(Node* node) 294 { 295 if (m_nbChildren == 0) 296 return m_parent ? m_parent : this; 297 298 // pick the child whose bounds will be extended least 299 300 Node* pick = m_children[0]; 301 int minIncrease = pick->delta(node); 302 for (unsigned int i = 1; i < m_nbChildren; i++) { 303 int increase = m_children[i]->delta(node); 304 if (increase < minIncrease) { 305 minIncrease = increase; 306 pick = m_children[i]; 307 } 308 } 309 310 return pick->findNode(node); 311 } 312 313 void Node::tighten() 314 { 315 recomputeBounds(m_minX, m_minY, m_maxX, m_maxY, 316 m_nbChildren, m_children, 0); 317 } 318 319 int Node::delta(Node* node) 320 { 321 return computeDeltaArea(node, m_minX, m_minY, m_maxX, m_maxY); 322 } 323 324 void Node::simpleAdd(Node* node) 325 { 326 node->setParent(this); 327 if (!m_children) 328 m_children = new Node*[m_tree->m_maxChildren + 1]; 329 m_children[m_nbChildren] = node; 330 m_nbChildren++; 331 } 332 333 void Node::add(Node* node) 334 { 335 simpleAdd(node); 336 Node* NN = 0; 337 if (m_nbChildren > m_tree->m_maxChildren) 338 NN = split(); 339 340 adjustTree(this, NN); 341 } 342 343 void Node::remove(Node* node) 344 { 345 int nodeIndex = -1; 346 for (unsigned int i = 0; i < m_nbChildren; i++) { 347 if (m_children[i] == node) { 348 nodeIndex = i; 349 break; 350 } 351 } 352 if (nodeIndex == -1) 353 return; 354 355 // compact 356 for (unsigned int i = nodeIndex; i < m_nbChildren - 1; i++) 357 m_children[i] = m_children[i + 1]; 358 m_nbChildren--; 359 } 360 361 void Node::destroy(int index) 362 { 363 delete m_children[index]; 364 // compact 365 for (unsigned int i = index; i < m_nbChildren - 1; i++) 366 m_children[i] = m_children[i + 1]; 367 m_nbChildren--; 368 } 369 370 void Node::removeAll() 371 { 372 m_nbChildren = 0; 373 m_minX = 0; 374 m_maxX = 0; 375 m_minY = 0; 376 m_maxY = 0; 377 } 378 379 Node* Node::split() 380 { 381 // First, let's get the seeds 382 // The idea is to get elements as distant as possible 383 // as we can, so that the resulting splitted lists 384 // will be more likely to not overlap. 385 Node* minElementX = m_children[0]; 386 Node* maxElementX = m_children[0]; 387 Node* minElementY = m_children[0]; 388 Node* maxElementY = m_children[0]; 389 for (unsigned int i = 1; i < m_nbChildren; i++) { 390 if (m_children[i]->m_minX < minElementX->m_minX) 391 minElementX = m_children[i]; 392 if (m_children[i]->m_minY < minElementY->m_minY) 393 minElementY = m_children[i]; 394 if (m_children[i]->m_maxX >= maxElementX->m_maxX) 395 maxElementX = m_children[i]; 396 if (m_children[i]->m_maxY >= maxElementY->m_maxY) 397 maxElementY = m_children[i]; 398 } 399 400 int dx = maxElementX->m_maxX - minElementX->m_minX; 401 int dy = maxElementY->m_maxY - minElementY->m_minY; 402 403 // assign the two seeds... 404 Node* elementA = minElementX; 405 Node* elementB = maxElementX; 406 407 if (dx < dy) { 408 elementA = minElementY; 409 elementB = maxElementY; 410 } 411 412 // If we get the same element, just get the first and 413 // last element inserted... 414 if (elementA == elementB) { 415 elementA = m_children[0]; 416 elementB = m_children[m_nbChildren - 1]; 417 } 418 419 #ifdef DEBUG 420 ALOGV("split Node %d, dx: %d dy: %d elem A is %d, elem B is %d", 421 m_tid, dx, dy, elementA->m_tid, elementB->m_tid); 422 #endif 423 424 // Let's use some temporary lists to do the split 425 ElementList* listA = m_tree->m_listA; 426 ElementList* listB = m_tree->m_listB; 427 listA->removeAll(); 428 listB->removeAll(); 429 430 listA->add(elementA); 431 listB->add(elementB); 432 433 remove(elementA); 434 remove(elementB); 435 436 // For any remaining elements, insert it into the list 437 // resulting in the smallest growth 438 for (unsigned int i = 0; i < m_nbChildren; i++) { 439 Node* node = m_children[i]; 440 int dA = listA->delta(node); 441 int dB = listB->delta(node); 442 443 if (dA < dB && listA->m_nbChildren < m_tree->m_maxChildren) 444 listA->add(node); 445 else if (dB < dA && listB->m_nbChildren < m_tree->m_maxChildren) 446 listB->add(node); 447 else { 448 ElementList* smallestList = 449 listA->m_nbChildren > listB->m_nbChildren ? listB : listA; 450 smallestList->add(node); 451 } 452 } 453 454 // Use the list to rebuild the nodes 455 removeAll(); 456 for (unsigned int i = 0; i < listA->m_nbChildren; i++) 457 simpleAdd(listA->m_children[i]); 458 459 Node* NN = Node::create(m_tree); 460 for (unsigned int i = 0; i < listB->m_nbChildren; i++) 461 NN->simpleAdd(listB->m_children[i]); 462 NN->tighten(); 463 464 return NN; 465 } 466 467 bool Node::isRoot() 468 { 469 return m_tree->m_root == this; 470 } 471 472 void Node::adjustTree(Node* N, Node* NN) 473 { 474 bool callParent = N->updateBounds(); 475 476 if (N->isRoot() && NN) { 477 // build new root 478 Node* root = Node::create(m_tree); 479 #ifdef DEBUG 480 ALOGV("-> node %d created as new root", root->m_tid); 481 #endif 482 root->simpleAdd(N); 483 root->simpleAdd(NN); 484 root->tighten(); 485 m_tree->m_root = root; 486 return; 487 } 488 489 if (N->isRoot()) 490 return; 491 492 if (N->m_parent) { 493 if (NN) 494 N->m_parent->add(NN); 495 else if (callParent) 496 adjustTree(N->m_parent, 0); 497 } 498 } 499 500 bool Node::updateBounds() 501 { 502 int ominx = m_minX; 503 int ominy = m_minY; 504 int omaxx = m_maxX; 505 int omaxy = m_maxY; 506 tighten(); 507 if ((ominx != m_minX) 508 || (ominy != m_minY) 509 || (omaxx != m_maxX) 510 || (omaxy != m_maxY)) 511 return true; 512 return false; 513 } 514 515 #ifdef DEBUG 516 static int gMaxLevel = 0; 517 static int gNbNodes = 0; 518 static int gNbElements = 0; 519 520 void Node::drawTree(int level) 521 { 522 if (level == 0) { 523 ALOGV("\n*** show tree ***\n"); 524 gMaxLevel = 0; 525 gNbNodes = 0; 526 gNbElements = 0; 527 } 528 529 display(level); 530 for (unsigned int i = 0; i < m_nbChildren; i++) 531 { 532 m_children[i]->drawTree(level + 1); 533 } 534 535 if (gMaxLevel < level) 536 gMaxLevel = level; 537 538 if (!m_nbChildren) 539 gNbElements++; 540 else 541 gNbNodes++; 542 543 if (level == 0) { 544 ALOGV("********************\n"); 545 ALOGV("Depth level %d, total bytes: %d, %d nodes, %d bytes (%d bytes/node), %d elements, %d bytes (%d bytes/node)", 546 gMaxLevel, gNbNodes * sizeof(Node) + gNbElements * sizeof(Element), 547 gNbNodes, gNbNodes * sizeof(Node), sizeof(Node), 548 gNbElements, gNbElements * sizeof(Element), sizeof(Element)); 549 } 550 } 551 #endif 552 553 #ifdef DEBUG 554 void Node::display(int level) 555 { 556 ALOGV("%*sNode %d - %d, %d, %d, %d (%d x %d)", 557 2*level, "", m_tid, m_minX, m_minY, m_maxX, m_maxY, m_maxX - m_minX, m_maxY - m_minY); 558 } 559 #endif 560 561 bool Node::overlap(int minx, int miny, int maxx, int maxy) 562 { 563 return ! (minx > m_maxX 564 || maxx < m_minX 565 || maxy < m_minY 566 || miny > m_maxY); 567 } 568 569 void Node::search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list) 570 { 571 if (isElement() && overlap(minx, miny, maxx, maxy)) 572 list.append(this->m_payload); 573 574 for (unsigned int i = 0; i < m_nbChildren; i++) { 575 if (m_children[i]->overlap(minx, miny, maxx, maxy)) 576 m_children[i]->search(minx, miny, maxx, maxy, list); 577 } 578 } 579 580 bool Node::inside(int minx, int miny, int maxx, int maxy) 581 { 582 return (minx <= m_minX 583 && maxx >= m_maxX 584 && miny <= m_minY 585 && maxy >= m_maxY); 586 } 587 588 void Node::remove(int minx, int miny, int maxx, int maxy) 589 { 590 for (unsigned int i = 0; i < m_nbChildren; i++) { 591 if (m_children[i]->inside(minx, miny, maxx, maxy)) 592 destroy(i); 593 else if (m_children[i]->overlap(minx, miny, maxx, maxy)) 594 m_children[i]->remove(minx, miny, maxx, maxy); 595 } 596 } 597 598 } // Namespace RTree 599