11cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard/* 21cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * Copyright 2012, The Android Open Source Project 31cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * 41cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * Redistribution and use in source and binary forms, with or without 51cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * modification, are permitted provided that the following conditions 61cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * are met: 71cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * * Redistributions of source code must retain the above copyright 81cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * notice, this list of conditions and the following disclaimer. 91cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * * Redistributions in binary form must reproduce the above copyright 101cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * notice, this list of conditions and the following disclaimer in the 111cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * documentation and/or other materials provided with the distribution. 121cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * 131cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY 141cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 151cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 161cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 171cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 181cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 191cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 201cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 211cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 221cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 231cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 241cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard */ 251cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 261cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#ifndef RTree_h 271cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#define RTree_h 281cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 291cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#include <Vector.h> 301cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#include "IntRect.h" 311cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#include "GraphicsOperation.h" 321cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 331cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardnamespace WebCore { 341cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 35e76b13ff11039a3640550fc332dee125b62b4c58John Reckclass LinearAllocator; 36e76b13ff11039a3640550fc332dee125b62b4c58John Reck 371cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardclass RecordingData { 381cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardpublic: 3977d974918eff4b56050e9f1c3a78becab1244a04John Reck RecordingData(GraphicsOperation::Operation* ops, size_t orderBy) 401cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard : m_orderBy(orderBy) 411cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard , m_operation(ops) 421cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard {} 431cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard ~RecordingData() { 44d9779adc025ab665fde1c9983e7793e96ab56d4eJohn Reck m_operation->~Operation(); 451cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard } 461cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 4777d974918eff4b56050e9f1c3a78becab1244a04John Reck size_t m_orderBy; 481cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard GraphicsOperation::Operation* m_operation; 49c0df80bf70ee26fc3ebcdb52f6800cedf75db768John Reck 50c0df80bf70ee26fc3ebcdb52f6800cedf75db768John Reck void* operator new(size_t size, LinearAllocator* allocator); 51c0df80bf70ee26fc3ebcdb52f6800cedf75db768John Reck 52c0df80bf70ee26fc3ebcdb52f6800cedf75db768John Reck // Purposely not implemented - use a LinearAllocator please 53c0df80bf70ee26fc3ebcdb52f6800cedf75db768John Reck void* operator new(size_t size); 54c0df80bf70ee26fc3ebcdb52f6800cedf75db768John Reck void operator delete(void* ptr); 551cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard}; 561cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 57e76b13ff11039a3640550fc332dee125b62b4c58John Reck} // namespace WebCore 581cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 591cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardnamespace RTree { 601cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 611cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardclass ElementList; 621cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardclass Node; 631cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 641cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardclass RTree { 651cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardpublic: 661cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard // M -- max number of children per node 67c0df80bf70ee26fc3ebcdb52f6800cedf75db768John Reck RTree(WebCore::LinearAllocator* allocator, int M = 10); 681cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard ~RTree(); 691cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 701cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload); 711cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard // Does an overlap search 721cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void search(WebCore::IntRect& clip, Vector<WebCore::RecordingData*>& list); 73f87a68b1847dffdc65542deaed6d924878c99db4Nicolas Roard // Does an inclusive remove -- all elements fully inside the clip will 74f87a68b1847dffdc65542deaed6d924878c99db4Nicolas Roard // be removed from the tree 75f87a68b1847dffdc65542deaed6d924878c99db4Nicolas Roard void remove(WebCore::IntRect& clip); 761cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void display(); 771cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 78e76b13ff11039a3640550fc332dee125b62b4c58John Reck void* allocateNode(); 79e76b13ff11039a3640550fc332dee125b62b4c58John Reck void deleteNode(Node* n); 80e76b13ff11039a3640550fc332dee125b62b4c58John Reck 811cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardprivate: 821cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 839ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard Node* m_root; 849ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard unsigned m_maxChildren; 859ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard ElementList* m_listA; 869ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard ElementList* m_listB; 87e76b13ff11039a3640550fc332dee125b62b4c58John Reck WebCore::LinearAllocator* m_allocator; 881cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 891cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard friend class Node; 901cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard}; 911cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 921cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardclass ElementList { 931cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardpublic: 941cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 951cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard ElementList(int size); 961cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard ~ElementList(); 9795e32410ffa4f84bc6b140640731bd44c50cee88Nicolas Roard void add(Node* n); 981cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void tighten(); 991cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard int delta(Node* n); 1001cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void removeAll(); 1011cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void display(); 1021cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1039ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard Node** m_children; 1049ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard unsigned m_nbChildren; 1051cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1061cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardprivate: 1071cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1089ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_minX; 1099ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_maxX; 1109ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_minY; 1119ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_maxY; 1129ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_area; 11395e32410ffa4f84bc6b140640731bd44c50cee88Nicolas Roard bool m_didTighten; 1141cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard}; 1151cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1161cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardclass Node { 1171cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardpublic: 1181cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard static Node* gRoot; 1191cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 120e76b13ff11039a3640550fc332dee125b62b4c58John Reck static Node* create(RTree* tree) { 121e76b13ff11039a3640550fc332dee125b62b4c58John Reck return create(tree, 0, 0, 0, 0, 0); 122e76b13ff11039a3640550fc332dee125b62b4c58John Reck } 123e76b13ff11039a3640550fc332dee125b62b4c58John Reck 124e76b13ff11039a3640550fc332dee125b62b4c58John Reck static Node* create(RTree* tree, int minx, int miny, int maxx, int maxy, 125e76b13ff11039a3640550fc332dee125b62b4c58John Reck WebCore::RecordingData* payload) { 126e76b13ff11039a3640550fc332dee125b62b4c58John Reck return new (tree->allocateNode()) Node(tree, minx, miny, maxx, maxy, payload); 127e76b13ff11039a3640550fc332dee125b62b4c58John Reck } 128e76b13ff11039a3640550fc332dee125b62b4c58John Reck 129e76b13ff11039a3640550fc332dee125b62b4c58John Reck ~Node(); 1301cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1311cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void insert(Node* n); 1321cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list); 133f87a68b1847dffdc65542deaed6d924878c99db4Nicolas Roard void remove(int minx, int miny, int maxx, int maxy); 134e76b13ff11039a3640550fc332dee125b62b4c58John Reck 135e76b13ff11039a3640550fc332dee125b62b4c58John Reck // Intentionally not implemented as Node* is custom allocated, we don't want to use this 136e76b13ff11039a3640550fc332dee125b62b4c58John Reck void operator delete(void*); 1371cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1381cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardprivate: 139e76b13ff11039a3640550fc332dee125b62b4c58John Reck Node(RTree* tree, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload); 1401cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1411cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void setParent(Node* n); 1421cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard Node* findNode(Node* n); 14395e32410ffa4f84bc6b140640731bd44c50cee88Nicolas Roard void simpleAdd(Node* n); 1441cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void add(Node* n); 1451cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void remove(Node* n); 146f87a68b1847dffdc65542deaed6d924878c99db4Nicolas Roard void destroy(int index); 1471cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void removeAll(); 1481cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard Node* split(); 1491cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void adjustTree(Node* N, Node* NN); 1501cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard void tighten(); 15195e32410ffa4f84bc6b140640731bd44c50cee88Nicolas Roard bool updateBounds(); 1521cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard int delta(Node* n); 1531cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1541cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard bool overlap(int minx, int miny, int maxx, int maxy); 155f87a68b1847dffdc65542deaed6d924878c99db4Nicolas Roard bool inside(int minx, int miny, int maxx, int maxy); 1561cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 157e76b13ff11039a3640550fc332dee125b62b4c58John Reck bool isElement() { return m_payload; } 1581cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard bool isRoot(); 1591cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1601cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardprivate: 1611cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1629ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard RTree* m_tree; 1639ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard Node* m_parent; 1641cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1659ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard Node** m_children; 1669ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard unsigned m_nbChildren; 1671cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 168e76b13ff11039a3640550fc332dee125b62b4c58John Reck WebCore::RecordingData* m_payload; 169e76b13ff11039a3640550fc332dee125b62b4c58John Reck 1701cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roardpublic: 1711cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1729ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_minX; 1739ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_minY; 1749ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_maxX; 1759ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard int m_maxY; 1761cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1771cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#ifdef DEBUG 178e76b13ff11039a3640550fc332dee125b62b4c58John Reck void drawTree(int level = 0); 179e76b13ff11039a3640550fc332dee125b62b4c58John Reck void display(int level = 0); 1809ff239af6ed7d2c7fbfefb2e55c81db81e0462e7Nicolas Roard unsigned m_tid; 1811cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#endif 1821cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard}; 1831cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 184e76b13ff11039a3640550fc332dee125b62b4c58John Reck} // namespace RTree 1851cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard 1861cb75f6f5e7b8dbed4119b3a72fc8668bf24531fNicolas Roard#endif // RTree_h 187