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