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