SkTTopoSort.h 3.7 KB

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