| 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 |