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
26namespace WebCore {
27
28AreaAllocator::AreaAllocator(const IntSize& size)
29    : m_size(size)
30    , m_minAlloc(1, 1)
31    , m_margin(0, 0)
32{
33}
34
35AreaAllocator::~AreaAllocator()
36{
37}
38
39void AreaAllocator::expand(const IntSize& size)
40{
41    m_size = m_size.expandedTo(size);
42}
43
44void AreaAllocator::expandBy(const IntSize& size)
45{
46    m_size += size;
47}
48
49void AreaAllocator::release(const IntRect&)
50{
51}
52
53int AreaAllocator::overhead() const
54{
55    return 0;
56}
57
58IntSize AreaAllocator::roundAllocation(const 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 IntSize(width, height);
70}
71
72GeneralAreaAllocator::GeneralAreaAllocator(const IntSize& size)
73    : AreaAllocator(nextPowerOfTwo(size))
74{
75    m_root = new Node();
76    m_root->rect = 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(IntSize(8, 8));
83}
84
85GeneralAreaAllocator::~GeneralAreaAllocator()
86{
87    freeNode(m_root);
88}
89
90void GeneralAreaAllocator::freeNode(Node* node)
91{
92    if (node) {
93        freeNode(node->left);
94        freeNode(node->right);
95    }
96    delete node;
97}
98
99void GeneralAreaAllocator::expand(const IntSize& size)
100{
101    AreaAllocator::expand(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 = 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 = IntRect(m_root->rect.x(), m_root->rect.y(),
140                m_root->rect.width() * 2, m_root->rect.height());
141            right->rect = 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 = IntRect(m_root->rect.x(), m_root->rect.y(),
145                m_root->rect.width(), m_root->rect.height() * 2);
146            right->rect = 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
155static inline bool fitsWithin(const IntSize& size1, const IntSize& size2)
156{
157    return size1.width() <= size2.width() && size1.height() <= size2.height();
158}
159
160IntRect GeneralAreaAllocator::allocate(const IntSize& size)
161{
162    IntSize rounded = roundAllocation(size);
163    rounded = nextPowerOfTwo(rounded);
164    if (rounded.width() <= 0 || rounded.width() > m_size.width()
165        || rounded.height() <= 0 || rounded.height() > m_size.height())
166        return IntRect();
167
168    IntPoint point = allocateFromNode(rounded, m_root);
169    if (point.x() >= 0)
170        return IntRect(point, size);
171    return IntRect();
172}
173
174IntPoint GeneralAreaAllocator::allocateFromNode(const 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                    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 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(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(IntSize(size.width() * 2, size.height()), node->largestFree)) {
220                // Split along the X direction.
221                split = SplitOnX;
222            } else if (fitsWithin(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 = 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 IntPoint(-1, -1);
240}
241
242GeneralAreaAllocator::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 = IntRect(node->rect.x(), node->rect.y(),
259            node->rect.width() / 2, node->rect.height());
260        right->rect = IntRect(left->rect.maxX(), node->rect.y(),
261            node->rect.width() / 2, node->rect.height());
262    } else {
263        left->rect = IntRect(node->rect.x(), node->rect.y(),
264            node->rect.width(), node->rect.height() / 2);
265        right->rect = 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
275void GeneralAreaAllocator::updateLargestFree(Node* node)
276{
277    while ((node = node->parent)) {
278        node->largestFree = 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
285void GeneralAreaAllocator::release(const IntRect& rect)
286{
287    // Locate the node that contains the allocated region.
288    Node* node = m_root;
289    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
328int GeneralAreaAllocator::overhead() const
329{
330    return m_nodeCount * sizeof(Node);
331}
332
333} // namespace WebCore
334
335#endif // USE(COORDINATED_GRAPHICS)
336