1/*
2 * Copyright 2015 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkTTopoSort_DEFINED
9#define SkTTopoSort_DEFINED
10
11#include "SkTDArray.h"
12
13#ifdef SK_DEBUG
14template <typename T, typename Traits = T>
15void SkTTopoSort_CheckAllUnmarked(const SkTDArray<T*>& graph) {
16    for (int i = 0; i < graph.count(); ++i) {
17        SkASSERT(!Traits::IsTempMarked(graph[i]));
18        SkASSERT(!Traits::WasOutput(graph[i]));
19    }
20}
21
22template <typename T, typename Traits = T>
23void SkTTopoSort_CleanExit(const SkTDArray<T*>& graph) {
24    for (int i = 0; i < graph.count(); ++i) {
25        SkASSERT(!Traits::IsTempMarked(graph[i]));
26        SkASSERT(Traits::WasOutput(graph[i]));
27    }
28}
29#endif
30
31// Recursively visit a node and all the other nodes it depends on.
32// Return false if there is a loop.
33template <typename T, typename Traits = T>
34bool SkTTopoSort_Visit(T* node, SkTDArray<T*>* result) {
35    if (Traits::IsTempMarked(node)) {
36        // There is a loop.
37        return false;
38    }
39
40    // If the node under consideration has been already been output it means it
41    // (and all the nodes it depends on) are already in 'result'.
42    if (!Traits::WasOutput(node)) {
43        // This node hasn't been output yet. Recursively assess all the
44        // nodes it depends on outputing them first.
45        Traits::SetTempMark(node);
46        for (int i = 0; i < Traits::NumDependencies(node); ++i) {
47            if (!SkTTopoSort_Visit<T, Traits>(Traits::Dependency(node, i), result)) {
48                return false;
49            }
50        }
51        Traits::Output(node, result->count()); // mark this node as output
52        Traits::ResetTempMark(node);
53
54        *result->append() = node;
55    }
56
57    return true;
58}
59
60// Topologically sort the nodes in 'graph'. For this sort, when node 'i' depends
61// on node 'j' it means node 'j' must appear in the result before node 'i'.
62// A false return value means there was a loop and the contents of 'graph' will
63// be in some arbitrary state.
64//
65// Traits requires:
66//   static void Output(T* t, int index) { ... }  // 'index' is 't's position in the result
67//   static bool WasOutput(const T* t) { ... }
68//
69//   static void SetTempMark(T* t) { ... }        // transiently used during toposort
70//   static void ResetTempMark(T* t) { ... }
71//   static bool IsTempMarked(const T* t) { ... }
72//
73//   static int NumDependencies(const T* t) { ... } // 't' will be output after all the other -
74//   static T* Dependency(T* t, int index) { ... }  // nodes on which it depends
75// We'll look on T for these by default, or you can pass a custom Traits type.
76//
77// TODO: potentially add a version that takes a seed node and just outputs that
78// node and all the nodes on which it depends. This could be used to partially
79// flush a GrOpList DAG.
80template <typename T, typename Traits = T>
81bool SkTTopoSort(SkTDArray<T*>* graph) {
82    SkTDArray<T*> result;
83
84#ifdef SK_DEBUG
85    SkTTopoSort_CheckAllUnmarked<T, Traits>(*graph);
86#endif
87
88    result.setReserve(graph->count());
89
90    for (int i = 0; i < graph->count(); ++i) {
91        if (Traits::WasOutput((*graph)[i])) {
92            // This node was depended on by some earlier node and has already
93            // been output
94            continue;
95        }
96
97        // Output this node after all the nodes it depends on have been output.
98        if (!SkTTopoSort_Visit<T, Traits>((*graph)[i], &result)) {
99            return false;
100        }
101    }
102
103    SkASSERT(graph->count() == result.count());
104    graph->swap(result);
105
106#ifdef SK_DEBUG
107    SkTTopoSort_CleanExit<T, Traits>(*graph);
108#endif
109    return true;
110}
111
112#endif
113