1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
/*
* Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies)
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
*/
#ifndef AreaAllocator_h
#define AreaAllocator_h
#include <IntPoint.h>
#include <IntRect.h>
#include <IntSize.h>
namespace WebCore {
inline int nextPowerOfTwo(int number)
{
// This is a fast trick to get nextPowerOfTwo for an integer.
--number;
number |= number >> 1;
number |= number >> 2;
number |= number >> 4;
number |= number >> 8;
number |= number >> 16;
number++;
return number;
}
inline IntSize nextPowerOfTwo(const IntSize& size)
{
return IntSize(nextPowerOfTwo(size.width()), nextPowerOfTwo(size.height()));
}
} // namespace WebCore
namespace WebKit {
class AreaAllocator {
public:
AreaAllocator(const WebCore::IntSize&);
virtual ~AreaAllocator();
WebCore::IntSize size() const { return m_size; }
WebCore::IntSize minimumAllocation() const { return m_minAlloc; }
void setMinimumAllocation(const WebCore::IntSize& size) { m_minAlloc = size; }
WebCore::IntSize margin() const { return m_margin; }
void setMargin(const WebCore::IntSize &margin) { m_margin = margin; }
virtual void expand(const WebCore::IntSize&);
void expandBy(const WebCore::IntSize&);
virtual WebCore::IntRect allocate(const WebCore::IntSize&) = 0;
virtual void release(const WebCore::IntRect&);
virtual int overhead() const;
protected:
WebCore::IntSize m_size;
WebCore::IntSize m_minAlloc;
WebCore::IntSize m_margin;
WebCore::IntSize roundAllocation(const WebCore::IntSize&) const;
};
class GeneralAreaAllocator : public AreaAllocator {
public:
GeneralAreaAllocator(const WebCore::IntSize&);
virtual ~GeneralAreaAllocator();
void expand(const WebCore::IntSize&);
WebCore::IntRect allocate(const WebCore::IntSize&);
void release(const WebCore::IntRect&);
int overhead() const;
private:
enum Split { SplitOnX, SplitOnY };
struct Node {
WebCore::IntRect rect;
WebCore::IntSize largestFree;
Node* parent;
Node* left;
Node* right;
};
Node* m_root;
int m_nodeCount;
static void freeNode(Node*);
WebCore::IntPoint allocateFromNode(const WebCore::IntSize&, Node*);
Node* splitNode(Node*, Split);
static void updateLargestFree(Node*);
};
} // namespace WebKit
#endif
|
