/* * Copyright 2015 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #ifndef SkTTopoSort_DEFINED #define SkTTopoSort_DEFINED #include "include/core/SkRefCnt.h" #include "include/private/SkTArray.h" #ifdef SK_DEBUG template void SkTTopoSort_CheckAllUnmarked(const SkTArray>& graph) { for (int i = 0; i < graph.count(); ++i) { SkASSERT(!Traits::IsTempMarked(graph[i].get())); SkASSERT(!Traits::WasOutput(graph[i].get())); } } template void SkTTopoSort_CleanExit(const SkTArray>& graph) { for (int i = 0; i < graph.count(); ++i) { SkASSERT(!Traits::IsTempMarked(graph[i].get())); SkASSERT(Traits::WasOutput(graph[i].get())); } } #endif // Recursively visit a node and all the other nodes it depends on. // Return false if there is a loop. template bool SkTTopoSort_Visit(T* node, SkTArray>* result) { if (Traits::IsTempMarked(node)) { // There is a loop. return false; } // If the node under consideration has been already been output it means it // (and all the nodes it depends on) are already in 'result'. if (!Traits::WasOutput(node)) { // This node hasn't been output yet. Recursively assess all the // nodes it depends on outputing them first. Traits::SetTempMark(node); for (int i = 0; i < Traits::NumDependencies(node); ++i) { if (!SkTTopoSort_Visit(Traits::Dependency(node, i), result)) { return false; } } Traits::Output(node, result->count()); // mark this node as output Traits::ResetTempMark(node); result->push_back(sk_ref_sp(node)); } return true; } // Topologically sort the nodes in 'graph'. For this sort, when node 'i' depends // on node 'j' it means node 'j' must appear in the result before node 'i'. // A false return value means there was a loop and the contents of 'graph' will // be in some arbitrary state. // // Traits requires: // static void Output(T* t, int index) { ... } // 'index' is 't's position in the result // static bool WasOutput(const T* t) { ... } // // static void SetTempMark(T* t) { ... } // transiently used during toposort // static void ResetTempMark(T* t) { ... } // static bool IsTempMarked(const T* t) { ... } // // static int NumDependencies(const T* t) { ... } // 't' will be output after all the other - // static T* Dependency(T* t, int index) { ... } // nodes on which it depends // We'll look on T for these by default, or you can pass a custom Traits type. // // TODO: potentially add a version that takes a seed node and just outputs that // node and all the nodes on which it depends. This could be used to partially // flush a GrOpList DAG. template bool SkTTopoSort(SkTArray>* graph) { SkTArray> result; #ifdef SK_DEBUG SkTTopoSort_CheckAllUnmarked(*graph); #endif result.reserve(graph->count()); for (int i = 0; i < graph->count(); ++i) { if (Traits::WasOutput((*graph)[i].get())) { // This node was depended on by some earlier node and has already // been output continue; } // Output this node after all the nodes it depends on have been output. if (!SkTTopoSort_Visit((*graph)[i].get(), &result)) { return false; } } SkASSERT(graph->count() == result.count()); graph->swap(result); #ifdef SK_DEBUG SkTTopoSort_CleanExit(*graph); #endif return true; } #endif