Coordinated Graphics: Move AreaAllocator and UpdateAtlas to CoordinatedGraphics
[WebKit-https.git] / Source / WebKit2 / WebProcess / WebPage / CoordinatedGraphics / AreaAllocator.cpp
1 /*
2  * Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies)
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
17  *
18  */
19
20 #include "config.h"
21
22 #if USE(COORDINATED_GRAPHICS)
23
24 #include "AreaAllocator.h"
25
26 namespace WebKit {
27
28 AreaAllocator::AreaAllocator(const WebCore::IntSize& size)
29     : m_size(size)
30     , m_minAlloc(1, 1)
31     , m_margin(0, 0)
32 {
33 }
34
35 AreaAllocator::~AreaAllocator()
36 {
37 }
38
39 void AreaAllocator::expand(const WebCore::IntSize& size)
40 {
41     m_size = m_size.expandedTo(size);
42 }
43
44 void AreaAllocator::expandBy(const WebCore::IntSize& size)
45 {
46     m_size += size;
47 }
48
49 void AreaAllocator::release(const WebCore::IntRect&)
50 {
51 }
52
53 int AreaAllocator::overhead() const
54 {
55     return 0;
56 }
57
58 WebCore::IntSize AreaAllocator::roundAllocation(const WebCore::IntSize& size) const
59 {
60     int width = size.width() + m_margin.width();
61     int height = size.height() + m_margin.height();
62     int extra = width % m_minAlloc.width();
63     if (extra)
64         width += m_minAlloc.width() - extra;
65     extra = height % m_minAlloc.height();
66     if (extra)
67         height += m_minAlloc.height() - extra;
68
69     return WebCore::IntSize(width, height);
70 }
71
72 GeneralAreaAllocator::GeneralAreaAllocator(const WebCore::IntSize& size)
73     : AreaAllocator(WebCore::nextPowerOfTwo(size))
74 {
75     m_root = new Node();
76     m_root->rect = WebCore::IntRect(0, 0, m_size.width(), m_size.height());
77     m_root->largestFree = m_size;
78     m_root->parent = 0;
79     m_root->left = 0;
80     m_root->right = 0;
81     m_nodeCount = 1;
82     setMinimumAllocation(WebCore::IntSize(8, 8));
83 }
84
85 GeneralAreaAllocator::~GeneralAreaAllocator()
86 {
87     freeNode(m_root);
88 }
89
90 void GeneralAreaAllocator::freeNode(Node* node)
91 {
92     if (node) {
93         freeNode(node->left);
94         freeNode(node->right);
95     }
96     delete node;
97 }
98
99 void GeneralAreaAllocator::expand(const WebCore::IntSize& size)
100 {
101     AreaAllocator::expand(WebCore::nextPowerOfTwo(size));
102
103     if (m_root->rect.size() == m_size)
104         return; // No change.
105
106     if (!m_root->left && m_root->largestFree.width() > 0) {
107         // No allocations have occurred, so just adjust the root size.
108         m_root->rect = WebCore::IntRect(0, 0, m_size.width(), m_size.height());
109         m_root->largestFree = m_size;
110         return;
111     }
112
113     // Add extra nodes above the current root to expand the tree.
114     Node* oldRoot = m_root;
115     Split split;
116     if (m_size.width() >= m_size.height())
117         split = SplitOnX;
118     else
119         split = SplitOnY;
120
121     while (m_root->rect.size() != m_size) {
122         if (m_root->rect.width() == m_size.width())
123             split = SplitOnY;
124         else if (m_root->rect.height() == m_size.height())
125             split = SplitOnX;
126         Node* parent = new Node();
127         Node* right = new Node();
128         m_nodeCount += 2;
129         m_root->parent = parent;
130         parent->parent = 0;
131         parent->left = m_root;
132         parent->right = right;
133         parent->largestFree = m_root->rect.size();
134         right->parent = parent;
135         right->left = 0;
136         right->right = 0;
137         right->largestFree = m_root->rect.size();
138         if (split == SplitOnX) {
139             parent->rect = WebCore::IntRect(m_root->rect.x(), m_root->rect.y(),
140                 m_root->rect.width() * 2, m_root->rect.height());
141             right->rect = WebCore::IntRect(m_root->rect.x() + m_root->rect.width(), m_root->rect.y(),
142                 m_root->rect.width(), m_root->rect.height());
143         } else {
144             parent->rect = WebCore::IntRect(m_root->rect.x(), m_root->rect.y(),
145                 m_root->rect.width(), m_root->rect.height() * 2);
146             right->rect = WebCore::IntRect(m_root->rect.x(), m_root->rect.y() + m_root->rect.width(),
147                 m_root->rect.width(), m_root->rect.height());
148         }
149         split = (split == SplitOnX ? SplitOnY : SplitOnX);
150         m_root = parent;
151     }
152     updateLargestFree(oldRoot);
153 }
154
155 static inline bool fitsWithin(const WebCore::IntSize& size1, const WebCore::IntSize& size2)
156 {
157     return size1.width() <= size2.width() && size1.height() <= size2.height();
158 }
159
160 WebCore::IntRect GeneralAreaAllocator::allocate(const WebCore::IntSize& size)
161 {
162     WebCore::IntSize rounded = roundAllocation(size);
163     rounded = WebCore::nextPowerOfTwo(rounded);
164     if (rounded.width() <= 0 || rounded.width() > m_size.width()
165         || rounded.height() <= 0 || rounded.height() > m_size.height())
166         return WebCore::IntRect();
167
168     WebCore::IntPoint point = allocateFromNode(rounded, m_root);
169     if (point.x() >= 0)
170         return WebCore::IntRect(point, size);
171     return WebCore::IntRect();
172 }
173
174 WebCore::IntPoint GeneralAreaAllocator::allocateFromNode(const WebCore::IntSize& size, Node* node)
175 {
176     // Find the best node to insert into, which should be
177     // a node with the least amount of unused space that is
178     // big enough to contain the requested size.
179     while (node) {
180         // Go down a level and determine if the left or right
181         // sub-tree contains the best chance of allocation.
182         Node* left = node->left;
183         Node* right = node->right;
184         if (left && fitsWithin(size, left->largestFree)) {
185             if (right && fitsWithin(size, right->largestFree)) {
186                 if (left->largestFree.width() < right->largestFree.width()
187                     || left->largestFree.height() < right->largestFree.height()) {
188                     // The largestFree values may be a little oversized,
189                     // so try the left sub-tree and then the right sub-tree.
190                     WebCore::IntPoint point = allocateFromNode(size, left);
191                     if (point.x() >= 0)
192                         return point;
193                     return allocateFromNode(size, right);
194                 }
195                 node = right;
196             } else
197                 node = left;
198         } else if (right && fitsWithin(size, right->largestFree))
199             node = right;
200         else if (left || right) {
201             // Neither sub-node has enough space to allocate from.
202             return WebCore::IntPoint(-1, -1);
203         } else if (fitsWithin(size, node->largestFree)) {
204             // Do we need to split this node into smaller pieces?
205             Split split;
206             if (fitsWithin(WebCore::IntSize(size.width() * 2, size.height() * 2), node->largestFree)) {
207                 // Split in either direction: choose the inverse of
208                 // the parent node's split direction to try to balance
209                 // out the wasted space as further subdivisions happen.
210                 if (node->parent
211                     && node->parent->left->rect.x() == node->parent->right->rect.x())
212                     split = SplitOnX;
213                 else if (node->parent)
214                     split = SplitOnY;
215                 else if (node->rect.width() >= node->rect.height())
216                     split = SplitOnX;
217                 else
218                     split = SplitOnY;
219             } else if (fitsWithin(WebCore::IntSize(size.width() * 2, size.height()), node->largestFree)) {
220                 // Split along the X direction.
221                 split = SplitOnX;
222             } else if (fitsWithin(WebCore::IntSize(size.width(), size.height() * 2), node->largestFree)) {
223                 // Split along the Y direction.
224                 split = SplitOnY;
225             } else {
226                 // Cannot split further - allocate this node.
227                 node->largestFree = WebCore::IntSize(0, 0);
228                 updateLargestFree(node);
229                 return node->rect.location();
230             }
231
232             // Split the node, then go around again using the left sub-tree.
233             node = splitNode(node, split);
234         } else {
235             // Cannot possibly fit into this node.
236             break;
237         }
238     }
239     return WebCore::IntPoint(-1, -1);
240 }
241
242 GeneralAreaAllocator::Node* GeneralAreaAllocator::splitNode
243     (Node* node, Split split)
244 {
245     Node* left = new Node();
246     Node* right = new Node();
247     m_nodeCount += 2;
248     left->parent = node;
249     left->left = 0;
250     left->right = 0;
251     right->parent = node;
252     right->left = 0;
253     right->right = 0;
254     node->left = left;
255     node->right = right;
256
257     if (split == SplitOnX) {
258         left->rect = WebCore::IntRect(node->rect.x(), node->rect.y(),
259             node->rect.width() / 2, node->rect.height());
260         right->rect = WebCore::IntRect(left->rect.maxX(), node->rect.y(),
261             node->rect.width() / 2, node->rect.height());
262     } else {
263         left->rect = WebCore::IntRect(node->rect.x(), node->rect.y(),
264             node->rect.width(), node->rect.height() / 2);
265         right->rect = WebCore::IntRect(node->rect.x(), left->rect.maxY(),
266             node->rect.width(), node->rect.height() / 2);
267     }
268
269     left->largestFree = left->rect.size();
270     right->largestFree = right->rect.size();
271     node->largestFree = right->largestFree;
272     return left;
273 }
274
275 void GeneralAreaAllocator::updateLargestFree(Node* node)
276 {
277     while ((node = node->parent)) {
278         node->largestFree = WebCore::IntSize(
279             std::max(node->left->largestFree.width(), node->right->largestFree.width()),
280             std::max(node->left->largestFree.height(), node->right->largestFree.height())
281             );
282     }
283 }
284
285 void GeneralAreaAllocator::release(const WebCore::IntRect& rect)
286 {
287     // Locate the node that contains the allocated region.
288     Node* node = m_root;
289     WebCore::IntPoint point = rect.location();
290     while (node) {
291         if (node->left && node->left->rect.contains(point))
292             node = node->left;
293         else if (node->right && node->right->rect.contains(point))
294             node = node->right;
295         else if (node->rect.contains(point))
296             break;
297         else
298             return; // Point is completely outside the tree.
299     }
300     if (!node)
301         return;
302
303     // Mark the node as free and then work upwards through the tree
304     // recombining and deleting nodes until we reach a sibling
305     // that is still allocated.
306     node->largestFree = node->rect.size();
307     while (node->parent) {
308         if (node->parent->left == node) {
309             if (node->parent->right->largestFree != node->parent->right->rect.size())
310                 break;
311         } else {
312             if (node->parent->left->largestFree != node->parent->left->rect.size())
313                 break;
314         }
315         node = node->parent;
316         freeNode(node->left);
317         freeNode(node->right);
318         m_nodeCount -= 2;
319         node->left = 0;
320         node->right = 0;
321         node->largestFree = node->rect.size();
322     }
323
324     // Make the rest of our ancestors have the correct "largest free size".
325     updateLargestFree(node);
326 }
327
328 int GeneralAreaAllocator::overhead() const
329 {
330     return m_nodeCount * sizeof(Node);
331 }
332
333 } // namespace
334
335 #endif // USE(COORDINATED_GRAPHICS)