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