#include "config.h"
#if USE(COORDINATED_GRAPHICS)
#include "AreaAllocator.h"
namespace WebCore {
AreaAllocator::AreaAllocator(const IntSize& size)
: m_size(size)
, m_minAlloc(1, 1)
, m_margin(0, 0)
{
}
AreaAllocator::~AreaAllocator()
{
}
void AreaAllocator::expand(const IntSize& size)
{
m_size = m_size.expandedTo(size);
}
void AreaAllocator::expandBy(const IntSize& size)
{
m_size += size;
}
void AreaAllocator::release(const IntRect&)
{
}
int AreaAllocator::overhead() const
{
return 0;
}
IntSize AreaAllocator::roundAllocation(const IntSize& size) const
{
int width = size.width() + m_margin.width();
int height = size.height() + m_margin.height();
int extra = width % m_minAlloc.width();
if (extra)
width += m_minAlloc.width() - extra;
extra = height % m_minAlloc.height();
if (extra)
height += m_minAlloc.height() - extra;
return IntSize(width, height);
}
GeneralAreaAllocator::GeneralAreaAllocator(const IntSize& size)
: AreaAllocator(nextPowerOfTwo(size))
{
m_root = new Node();
m_root->rect = IntRect(0, 0, m_size.width(), m_size.height());
m_root->largestFree = m_size;
m_root->parent = 0;
m_root->left = 0;
m_root->right = 0;
m_nodeCount = 1;
setMinimumAllocation(IntSize(8, 8));
}
GeneralAreaAllocator::~GeneralAreaAllocator()
{
freeNode(m_root);
}
void GeneralAreaAllocator::freeNode(Node* node)
{
if (node) {
freeNode(node->left);
freeNode(node->right);
}
delete node;
}
void GeneralAreaAllocator::expand(const IntSize& size)
{
AreaAllocator::expand(nextPowerOfTwo(size));
if (m_root->rect.size() == m_size)
return;
if (!m_root->left && m_root->largestFree.width() > 0) {
m_root->rect = IntRect(0, 0, m_size.width(), m_size.height());
m_root->largestFree = m_size;
return;
}
Node* oldRoot = m_root;
Split split;
if (m_size.width() >= m_size.height())
split = SplitOnX;
else
split = SplitOnY;
while (m_root->rect.size() != m_size) {
if (m_root->rect.width() == m_size.width())
split = SplitOnY;
else if (m_root->rect.height() == m_size.height())
split = SplitOnX;
Node* parent = new Node();
Node* right = new Node();
m_nodeCount += 2;
m_root->parent = parent;
parent->parent = 0;
parent->left = m_root;
parent->right = right;
parent->largestFree = m_root->rect.size();
right->parent = parent;
right->left = 0;
right->right = 0;
right->largestFree = m_root->rect.size();
if (split == SplitOnX) {
parent->rect = IntRect(m_root->rect.x(), m_root->rect.y(),
m_root->rect.width() * 2, m_root->rect.height());
right->rect = IntRect(m_root->rect.x() + m_root->rect.width(), m_root->rect.y(),
m_root->rect.width(), m_root->rect.height());
} else {
parent->rect = IntRect(m_root->rect.x(), m_root->rect.y(),
m_root->rect.width(), m_root->rect.height() * 2);
right->rect = IntRect(m_root->rect.x(), m_root->rect.y() + m_root->rect.width(),
m_root->rect.width(), m_root->rect.height());
}
split = (split == SplitOnX ? SplitOnY : SplitOnX);
m_root = parent;
}
updateLargestFree(oldRoot);
}
static inline bool fitsWithin(const IntSize& size1, const IntSize& size2)
{
return size1.width() <= size2.width() && size1.height() <= size2.height();
}
IntRect GeneralAreaAllocator::allocate(const IntSize& size)
{
IntSize rounded = roundAllocation(size);
rounded = nextPowerOfTwo(rounded);
if (rounded.width() <= 0 || rounded.width() > m_size.width()
|| rounded.height() <= 0 || rounded.height() > m_size.height())
return IntRect();
IntPoint point = allocateFromNode(rounded, m_root);
if (point.x() >= 0)
return IntRect(point, size);
return IntRect();
}
IntPoint GeneralAreaAllocator::allocateFromNode(const IntSize& size, Node* node)
{
while (node) {
Node* left = node->left;
Node* right = node->right;
if (left && fitsWithin(size, left->largestFree)) {
if (right && fitsWithin(size, right->largestFree)) {
if (left->largestFree.width() < right->largestFree.width()
|| left->largestFree.height() < right->largestFree.height()) {
IntPoint point = allocateFromNode(size, left);
if (point.x() >= 0)
return point;
return allocateFromNode(size, right);
}
node = right;
} else
node = left;
} else if (right && fitsWithin(size, right->largestFree))
node = right;
else if (left || right) {
return IntPoint(-1, -1);
} else if (fitsWithin(size, node->largestFree)) {
Split split;
if (fitsWithin(IntSize(size.width() * 2, size.height() * 2), node->largestFree)) {
if (node->parent
&& node->parent->left->rect.x() == node->parent->right->rect.x())
split = SplitOnX;
else if (node->parent)
split = SplitOnY;
else if (node->rect.width() >= node->rect.height())
split = SplitOnX;
else
split = SplitOnY;
} else if (fitsWithin(IntSize(size.width() * 2, size.height()), node->largestFree)) {
split = SplitOnX;
} else if (fitsWithin(IntSize(size.width(), size.height() * 2), node->largestFree)) {
split = SplitOnY;
} else {
node->largestFree = IntSize(0, 0);
updateLargestFree(node);
return node->rect.location();
}
node = splitNode(node, split);
} else {
break;
}
}
return IntPoint(-1, -1);
}
GeneralAreaAllocator::Node* GeneralAreaAllocator::splitNode
(Node* node, Split split)
{
Node* left = new Node();
Node* right = new Node();
m_nodeCount += 2;
left->parent = node;
left->left = 0;
left->right = 0;
right->parent = node;
right->left = 0;
right->right = 0;
node->left = left;
node->right = right;
if (split == SplitOnX) {
left->rect = IntRect(node->rect.x(), node->rect.y(),
node->rect.width() / 2, node->rect.height());
right->rect = IntRect(left->rect.maxX(), node->rect.y(),
node->rect.width() / 2, node->rect.height());
} else {
left->rect = IntRect(node->rect.x(), node->rect.y(),
node->rect.width(), node->rect.height() / 2);
right->rect = IntRect(node->rect.x(), left->rect.maxY(),
node->rect.width(), node->rect.height() / 2);
}
left->largestFree = left->rect.size();
right->largestFree = right->rect.size();
node->largestFree = right->largestFree;
return left;
}
void GeneralAreaAllocator::updateLargestFree(Node* node)
{
while ((node = node->parent)) {
node->largestFree = IntSize(
std::max(node->left->largestFree.width(), node->right->largestFree.width()),
std::max(node->left->largestFree.height(), node->right->largestFree.height())
);
}
}
void GeneralAreaAllocator::release(const IntRect& rect)
{
Node* node = m_root;
IntPoint point = rect.location();
while (node) {
if (node->left && node->left->rect.contains(point))
node = node->left;
else if (node->right && node->right->rect.contains(point))
node = node->right;
else if (node->rect.contains(point))
break;
else
return; }
if (!node)
return;
node->largestFree = node->rect.size();
while (node->parent) {
if (node->parent->left == node) {
if (node->parent->right->largestFree != node->parent->right->rect.size())
break;
} else {
if (node->parent->left->largestFree != node->parent->left->rect.size())
break;
}
node = node->parent;
freeNode(node->left);
freeNode(node->right);
m_nodeCount -= 2;
node->left = 0;
node->right = 0;
node->largestFree = node->rect.size();
}
updateLargestFree(node);
}
int GeneralAreaAllocator::overhead() const
{
return m_nodeCount * sizeof(Node);
}
}
#endif // USE(COORDINATED_GRAPHICS)