123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113 |
- /*
- * 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 <typename T, typename Traits = T>
- void SkTTopoSort_CheckAllUnmarked(const SkTArray<sk_sp<T>>& graph) {
- for (int i = 0; i < graph.count(); ++i) {
- SkASSERT(!Traits::IsTempMarked(graph[i].get()));
- SkASSERT(!Traits::WasOutput(graph[i].get()));
- }
- }
- template <typename T, typename Traits = T>
- void SkTTopoSort_CleanExit(const SkTArray<sk_sp<T>>& 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 <typename T, typename Traits = T>
- bool SkTTopoSort_Visit(T* node, SkTArray<sk_sp<T>>* 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<T, Traits>(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 <typename T, typename Traits = T>
- bool SkTTopoSort(SkTArray<sk_sp<T>>* graph) {
- SkTArray<sk_sp<T>> result;
- #ifdef SK_DEBUG
- SkTTopoSort_CheckAllUnmarked<T, Traits>(*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<T, Traits>((*graph)[i].get(), &result)) {
- return false;
- }
- }
- SkASSERT(graph->count() == result.count());
- graph->swap(result);
- #ifdef SK_DEBUG
- SkTTopoSort_CleanExit<T, Traits>(*graph);
- #endif
- return true;
- }
- #endif
|