chromium/third_party/skia/src/gpu/ganesh/GrTTopoSort.h

/*
 * 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 GrTTopoSort_DEFINED
#define GrTTopoSort_DEFINED

#include "include/core/SkRefCnt.h"  // IWYU pragma: keep
#include "include/core/SkSpan.h"
#include "include/core/SkTypes.h"

#include <cstddef>
#include <cstdint>

#ifdef SK_DEBUG
template <typename T, typename Traits = T>
void GrTTopoSort_CheckAllUnmarked(SkSpan<const sk_sp<T>> graph) { … }

template <typename T, typename Traits = T>
void GrTTopoSort_CleanExit(SkSpan<const sk_sp<T>> graph, uint32_t offset) { … }
#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 GrTTopoSort_Visit(T* node, uint32_t* counter) { … }

// 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'. Note that all
// dependencies of a node in the Span must also be in the Span or already have WasOutput() = true.
//
// 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, uint32_t index) { ... }  // 'index' is 't's position in the result
//   static bool WasOutput(const T* t) { ... }
//   static uint32_t GetIndex() { ... }
//
//   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.
//
// The offset parameter is useful if you are sorting ranges of a larger graph and when Output()
// is called on a T it must know it's position in the full graph array.
//
// 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 GrRenderTask DAG.
template <typename T, typename Traits = T>
bool GrTTopoSort(SkSpan<sk_sp<T>> graph, uint32_t offset = 0) { … }

#endif