Line data    Source code

       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
      14             : template <typename T, typename Traits = T>
      15           0 : void SkTTopoSort_CheckAllUnmarked(const SkTDArray<T*>& graph) {
      16           0 :     for (int i = 0; i < graph.count(); ++i) {
      17           0 :         SkASSERT(!Traits::IsTempMarked(graph[i]));
      18           0 :         SkASSERT(!Traits::WasOutput(graph[i]));
      19             :     }
      20           0 : }
      21             : 
      22             : template <typename T, typename Traits = T>
      23           0 : void SkTTopoSort_CleanExit(const SkTDArray<T*>& graph) {
      24           0 :     for (int i = 0; i < graph.count(); ++i) {
      25           0 :         SkASSERT(!Traits::IsTempMarked(graph[i]));
      26           0 :         SkASSERT(Traits::WasOutput(graph[i]));
      27             :     }
      28           0 : }
      29             : #endif
      30             : 
      31             : // Recursively visit a node and all the other nodes it depends on.
      32             : // Return false if there is a loop.
      33             : template <typename T, typename Traits = T>
      34           0 : bool SkTTopoSort_Visit(T* node, SkTDArray<T*>* result) {
      35           0 :     if (Traits::IsTempMarked(node)) {
      36             :         // There is a loop.
      37           0 :         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           0 :     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           0 :         Traits::SetTempMark(node);
      46           0 :         for (int i = 0; i < Traits::NumDependencies(node); ++i) {
      47           0 :             if (!SkTTopoSort_Visit<T, Traits>(Traits::Dependency(node, i), result)) {
      48           0 :                 return false;
      49             :             }
      50             :         }
      51           0 :         Traits::Output(node, result->count()); // mark this node as output
      52           0 :         Traits::ResetTempMark(node);
      53             : 
      54           0 :         *result->append() = node;
      55             :     }
      56             : 
      57           0 :     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.
      80             : template <typename T, typename Traits = T>
      81           0 : bool SkTTopoSort(SkTDArray<T*>* graph) {
      82           0 :     SkTDArray<T*> result;
      83             : 
      84             : #ifdef SK_DEBUG
      85           0 :     SkTTopoSort_CheckAllUnmarked<T, Traits>(*graph);
      86             : #endif
      87             : 
      88           0 :     result.setReserve(graph->count());
      89             : 
      90           0 :     for (int i = 0; i < graph->count(); ++i) {
      91           0 :         if (Traits::WasOutput((*graph)[i])) {
      92             :             // This node was depended on by some earlier node and has already
      93             :             // been output
      94           0 :             continue;
      95             :         }
      96             : 
      97             :         // Output this node after all the nodes it depends on have been output.
      98           0 :         if (!SkTTopoSort_Visit<T, Traits>((*graph)[i], &result)) {
      99           0 :             return false;
     100             :         }
     101             :     }
     102             : 
     103           0 :     SkASSERT(graph->count() == result.count());
     104           0 :     graph->swap(result);
     105             : 
     106             : #ifdef SK_DEBUG
     107           0 :     SkTTopoSort_CleanExit<T, Traits>(*graph);
     108             : #endif
     109           0 :     return true;
     110             : }
     111             : 
     112             : #endif