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 #ifndef RTree_h 27 #define RTree_h 28 29 #include <Vector.h> 30 #include "IntRect.h" 31 #include "GraphicsOperation.h" 32 33 namespace android { 34 class LinearAllocator; 35 } 36 37 namespace WebCore { 38 39 class RecordingData { 40 public: 41 RecordingData(GraphicsOperation::Operation* ops, size_t orderBy) 42 : m_orderBy(orderBy) 43 , m_operation(ops) 44 {} 45 ~RecordingData() { 46 m_operation->~Operation(); 47 } 48 49 size_t m_orderBy; 50 GraphicsOperation::Operation* m_operation; 51 52 void* operator new(size_t size, android::LinearAllocator* allocator); 53 54 // Purposely not implemented - use a LinearAllocator please 55 void* operator new(size_t size); 56 void operator delete(void* ptr); 57 }; 58 59 } // namespace WebCore 60 61 namespace RTree { 62 63 class ElementList; 64 class Node; 65 66 class RTree { 67 public: 68 // M -- max number of children per node 69 RTree(android::LinearAllocator* allocator, int M = 10); 70 ~RTree(); 71 72 void insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload); 73 // Does an overlap search 74 void search(WebCore::IntRect& clip, Vector<WebCore::RecordingData*>& list); 75 // Does an inclusive remove -- all elements fully inside the clip will 76 // be removed from the tree 77 void remove(WebCore::IntRect& clip); 78 void display(); 79 80 void* allocateNode(); 81 void deleteNode(Node* n); 82 83 private: 84 85 Node* m_root; 86 unsigned m_maxChildren; 87 ElementList* m_listA; 88 ElementList* m_listB; 89 android::LinearAllocator* m_allocator; 90 91 friend class Node; 92 }; 93 94 class ElementList { 95 public: 96 97 ElementList(int size); 98 ~ElementList(); 99 void add(Node* n); 100 void tighten(); 101 int delta(Node* n); 102 void removeAll(); 103 void display(); 104 105 Node** m_children; 106 unsigned m_nbChildren; 107 108 private: 109 110 int m_minX; 111 int m_maxX; 112 int m_minY; 113 int m_maxY; 114 int m_area; 115 bool m_didTighten; 116 }; 117 118 class Node { 119 public: 120 static Node* gRoot; 121 122 static Node* create(RTree* tree) { 123 return create(tree, 0, 0, 0, 0, 0); 124 } 125 126 static Node* create(RTree* tree, int minx, int miny, int maxx, int maxy, 127 WebCore::RecordingData* payload) { 128 return new (tree->allocateNode()) Node(tree, minx, miny, maxx, maxy, payload); 129 } 130 131 ~Node(); 132 133 void insert(Node* n); 134 void search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list); 135 void remove(int minx, int miny, int maxx, int maxy); 136 137 // Intentionally not implemented as Node* is custom allocated, we don't want to use this 138 void operator delete(void*); 139 140 private: 141 Node(RTree* tree, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload); 142 143 void setParent(Node* n); 144 Node* findNode(Node* n); 145 void simpleAdd(Node* n); 146 void add(Node* n); 147 void remove(Node* n); 148 void destroy(int index); 149 void removeAll(); 150 Node* split(); 151 void adjustTree(Node* N, Node* NN); 152 void tighten(); 153 bool updateBounds(); 154 int delta(Node* n); 155 156 bool overlap(int minx, int miny, int maxx, int maxy); 157 bool inside(int minx, int miny, int maxx, int maxy); 158 159 bool isElement() { return m_payload; } 160 bool isRoot(); 161 162 private: 163 164 RTree* m_tree; 165 Node* m_parent; 166 167 Node** m_children; 168 unsigned m_nbChildren; 169 170 WebCore::RecordingData* m_payload; 171 172 public: 173 174 int m_minX; 175 int m_minY; 176 int m_maxX; 177 int m_maxY; 178 179 #ifdef DEBUG 180 void drawTree(int level = 0); 181 void display(int level = 0); 182 unsigned m_tid; 183 #endif 184 }; 185 186 } // namespace RTree 187 188 #endif // RTree_h 189
