OLD | NEW |
1 // Copyright 2011 The Chromium Authors. All rights reserved. | 1 // Copyright 2011 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "config.h" | 5 #include "config.h" |
6 | 6 |
7 #include "CCLayerSorter.h" | 7 #include "CCLayerSorter.h" |
8 | 8 |
9 #include "CCMathUtil.h" | 9 #include "CCMathUtil.h" |
10 #include "CCRenderSurface.h" | 10 #include "CCRenderSurface.h" |
(...skipping 278 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
289 edge.to->incoming.push_back(&edge); | 289 edge.to->incoming.push_back(&edge); |
290 edge.to->incomingEdgeWeight += edge.weight; | 290 edge.to->incomingEdgeWeight += edge.weight; |
291 } | 291 } |
292 } | 292 } |
293 | 293 |
294 // Finds and removes an edge from the list by doing a swap with the | 294 // Finds and removes an edge from the list by doing a swap with the |
295 // last element of the list. | 295 // last element of the list. |
296 void CCLayerSorter::removeEdgeFromList(GraphEdge* edge, std::vector<GraphEdge*>&
list) | 296 void CCLayerSorter::removeEdgeFromList(GraphEdge* edge, std::vector<GraphEdge*>&
list) |
297 { | 297 { |
298 std::vector<GraphEdge*>::iterator iter = std::find(list.begin(), list.end(),
edge); | 298 std::vector<GraphEdge*>::iterator iter = std::find(list.begin(), list.end(),
edge); |
299 ASSERT(iter != list.end()); | 299 DCHECK(iter != list.end()); |
300 list.erase(iter); | 300 list.erase(iter); |
301 } | 301 } |
302 | 302 |
303 // Sorts the given list of layers such that they can be painted in a back-to-fro
nt | 303 // Sorts the given list of layers such that they can be painted in a back-to-fro
nt |
304 // order. Sorting produces correct results for non-intersecting layers that don'
t have | 304 // order. Sorting produces correct results for non-intersecting layers that don'
t have |
305 // cyclical order dependencies. Cycles and intersections are broken (somewhat) a
ribtrarily. | 305 // cyclical order dependencies. Cycles and intersections are broken (somewhat) a
ribtrarily. |
306 // Sorting of layers is done via a topological sort of a directed graph whose no
des are | 306 // Sorting of layers is done via a topological sort of a directed graph whose no
des are |
307 // the layers themselves. An edge from node A to node B signifies that layer A n
eeds to | 307 // the layers themselves. An edge from node A to node B signifies that layer A n
eeds to |
308 // be drawn before layer B. If A and B have no dependency between each other, th
en we | 308 // be drawn before layer B. If A and B have no dependency between each other, th
en we |
309 // preserve the ordering of those layers as they were in the original list. | 309 // preserve the ordering of those layers as they were in the original list. |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
374 // nodes that have zero-weight incoming edges i.e. layers that are being | 374 // nodes that have zero-weight incoming edges i.e. layers that are being |
375 // occluded by a layer that intersects them. | 375 // occluded by a layer that intersects them. |
376 float minIncomingEdgeWeight = FLT_MAX; | 376 float minIncomingEdgeWeight = FLT_MAX; |
377 GraphNode* nextNode = 0; | 377 GraphNode* nextNode = 0; |
378 for (unsigned i = 0; i < m_nodes.size(); i++) { | 378 for (unsigned i = 0; i < m_nodes.size(); i++) { |
379 if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < mi
nIncomingEdgeWeight) { | 379 if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < mi
nIncomingEdgeWeight) { |
380 minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight; | 380 minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight; |
381 nextNode = &m_nodes[i]; | 381 nextNode = &m_nodes[i]; |
382 } | 382 } |
383 } | 383 } |
384 ASSERT(nextNode); | 384 DCHECK(nextNode); |
385 // Remove all its incoming edges. | 385 // Remove all its incoming edges. |
386 for (unsigned e = 0; e < nextNode->incoming.size(); e++) { | 386 for (unsigned e = 0; e < nextNode->incoming.size(); e++) { |
387 GraphEdge* incomingEdge = nextNode->incoming[e]; | 387 GraphEdge* incomingEdge = nextNode->incoming[e]; |
388 | 388 |
389 m_activeEdges.erase(incomingEdge); | 389 m_activeEdges.erase(incomingEdge); |
390 removeEdgeFromList(incomingEdge, incomingEdge->from->outgoing); | 390 removeEdgeFromList(incomingEdge, incomingEdge->from->outgoing); |
391 } | 391 } |
392 nextNode->incoming.clear(); | 392 nextNode->incoming.clear(); |
393 nextNode->incomingEdgeWeight = 0; | 393 nextNode->incomingEdgeWeight = 0; |
394 noIncomingEdgeNodeList.push_back(nextNode); | 394 noIncomingEdgeNodeList.push_back(nextNode); |
395 DVLOG(2) << "Breaking cycle by cleaning up incoming edges from " << next
Node->layer->id() << " (weight = " << minIncomingEdgeWeight << ")"; | 395 DVLOG(2) << "Breaking cycle by cleaning up incoming edges from " << next
Node->layer->id() << " (weight = " << minIncomingEdgeWeight << ")"; |
396 } | 396 } |
397 | 397 |
398 // Note: The original elements of the list are in no danger of having their
ref count go to zero | 398 // Note: The original elements of the list are in no danger of having their
ref count go to zero |
399 // here as they are all nodes of the layer hierarchy and are kept alive by t
heir parent nodes. | 399 // here as they are all nodes of the layer hierarchy and are kept alive by t
heir parent nodes. |
400 int count = 0; | 400 int count = 0; |
401 for (LayerList::iterator it = first; it < last; it++) | 401 for (LayerList::iterator it = first; it < last; it++) |
402 *it = sortedList[count++]->layer; | 402 *it = sortedList[count++]->layer; |
403 | 403 |
404 DVLOG(2) << "Sorting end ----"; | 404 DVLOG(2) << "Sorting end ----"; |
405 | 405 |
406 m_nodes.clear(); | 406 m_nodes.clear(); |
407 m_edges.clear(); | 407 m_edges.clear(); |
408 m_activeEdges.clear(); | 408 m_activeEdges.clear(); |
409 } | 409 } |
410 | 410 |
411 } | 411 } |
OLD | NEW |