Coordinated Graphics: Move AreaAllocator and UpdateAtlas to CoordinatedGraphics
[WebKit-https.git] / Source / WebKit2 / WebProcess / WebPage / CoordinatedGraphics / AreaAllocator.h
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 #ifndef AreaAllocator_h
21 #define AreaAllocator_h
22
23 #include <IntPoint.h>
24 #include <IntRect.h>
25 #include <IntSize.h>
26
27 #if USE(COORDINATED_GRAPHICS)
28
29 namespace WebCore {
30 inline int nextPowerOfTwo(int number)
31 {
32     // This is a fast trick to get nextPowerOfTwo for an integer.
33     --number;
34     number |= number >> 1;
35     number |= number >> 2;
36     number |= number >> 4;
37     number |= number >> 8;
38     number |= number >> 16;
39     number++;
40     return number;
41 }
42
43 inline IntSize nextPowerOfTwo(const IntSize& size)
44 {
45     return IntSize(nextPowerOfTwo(size.width()), nextPowerOfTwo(size.height()));
46 }
47 } // namespace WebCore
48
49 namespace WebKit {
50
51 class AreaAllocator {
52 public:
53     AreaAllocator(const WebCore::IntSize&);
54     virtual ~AreaAllocator();
55
56     WebCore::IntSize size() const { return m_size; }
57
58     WebCore::IntSize minimumAllocation() const { return m_minAlloc; }
59     void setMinimumAllocation(const WebCore::IntSize& size) { m_minAlloc = size; }
60
61     WebCore::IntSize margin() const { return m_margin; }
62     void setMargin(const WebCore::IntSize &margin) { m_margin = margin; }
63
64     virtual void expand(const WebCore::IntSize&);
65     void expandBy(const WebCore::IntSize&);
66
67     virtual WebCore::IntRect allocate(const WebCore::IntSize&) = 0;
68     virtual void release(const WebCore::IntRect&);
69
70     virtual int overhead() const;
71
72 protected:
73     WebCore::IntSize m_size;
74     WebCore::IntSize m_minAlloc;
75     WebCore::IntSize m_margin;
76
77     WebCore::IntSize roundAllocation(const WebCore::IntSize&) const;
78 };
79
80 class GeneralAreaAllocator : public AreaAllocator {
81 public:
82     GeneralAreaAllocator(const WebCore::IntSize&);
83     virtual ~GeneralAreaAllocator();
84
85     void expand(const WebCore::IntSize&);
86     WebCore::IntRect allocate(const WebCore::IntSize&);
87     void release(const WebCore::IntRect&);
88     int overhead() const;
89
90 private:
91     enum Split { SplitOnX, SplitOnY };
92
93     struct Node {
94         WebCore::IntRect rect;
95         WebCore::IntSize largestFree;
96         Node* parent;
97         Node* left;
98         Node* right;
99     };
100
101     Node* m_root;
102     int m_nodeCount;
103
104     static void freeNode(Node*);
105     WebCore::IntPoint allocateFromNode(const WebCore::IntSize&, Node*);
106     Node* splitNode(Node*, Split);
107     static void updateLargestFree(Node*);
108 };
109
110 } // namespace WebKit
111
112 #endif // USE(COORDINATED_GRAPHICS)
113
114 #endif // AreaAllocator_h