GrTTopoSort.h File Reference

#include "include/core/SkRefCnt.h"
#include "include/core/SkSpan.h"

Go to the source code of this file.

Functions
template<typename T , typename Traits = T>
bool	GrTTopoSort_Visit (T *node, uint32_t *counter)
template<typename T , typename Traits = T>
bool	GrTTopoSort (SkSpan< sk_sp< T > > graph, uint32_t offset=0)

Function Documentation

GrTTopoSort()

template<typename T , typename Traits = T>

bool GrTTopoSort	(	SkSpan< sk_sp< T > >	graph,
		uint32_t	offset = 0
	)

Definition at line 92 of file GrTTopoSort.h.

                                                              {
    uint32_t counter = offset;
 
#ifdef SK_DEBUG
    GrTTopoSort_CheckAllUnmarked<T, Traits>(graph);
#endif
 
    bool succeeded = true;
 
    for (size_t i = 0; i < graph.size(); ++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 (!GrTTopoSort_Visit<T, Traits>(graph[i].get(), &counter)) {
            succeeded = false;
        }
    }
 
    SkASSERT(counter - offset == (uint32_t) graph.size());
 
    // Reorder the array given the output order
    for (uint32_t i = 0; i < (uint32_t) graph.size(); ++i) {
        for (uint32_t correctIndex = Traits::GetIndex(graph[i].get()) - offset;
             correctIndex != i;
             correctIndex = Traits::GetIndex(graph[i].get()) - offset) {
             graph[i].swap(graph[correctIndex]);
        }
    }
 
#ifdef SK_DEBUG
    GrTTopoSort_CleanExit<T, Traits>(graph, offset);
#endif
    return succeeded;
}

GrTTopoSort_Visit()

template<typename T , typename Traits = T>

bool GrTTopoSort_Visit	(	T *	node,
		uint32_t *	counter
	)

Definition at line 36 of file GrTTopoSort.h.

                                                   {
    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)) {
        return true;
    }
 
    bool succeeded = true;
    // 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 (!GrTTopoSort_Visit<T, Traits>(Traits::Dependency(node, i), counter)) {
            succeeded = false;
        }
    }
 
    Traits::Output(node, *counter); // mark this node as output
    ++(*counter);
    Traits::ResetTempMark(node);
 
    return succeeded;
}