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