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