sparseInputTraverser.h

Go to the documentation of this file.

//
// Copyright 2025 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/license.
//
#ifndef PXR_EXEC_VDF_SPARSE_INPUT_TRAVERSER_H
#define PXR_EXEC_VDF_SPARSE_INPUT_TRAVERSER_H
 
 
#include "pxr/pxr.h"
 
#include "pxr/exec/vdf/api.h"
#include "pxr/exec/vdf/object.h"
#include "pxr/exec/vdf/mask.h"
#include "pxr/exec/vdf/maskedOutputVector.h"
#include "pxr/exec/vdf/poolChainIndex.h"
 
#include "pxr/base/tf/hashmap.h"
 
#include <functional>
 
PXR_NAMESPACE_OPEN_SCOPE
 
class VdfConnection;
class VdfNode;
 
class VdfSparseInputTraverser
{
public:
 
    enum CallbackMode
    {
        CallbackModeAllNodes,
 
        CallbackModeTerminalNodes
    };
 
 
 
    using NodeCallback = std::function<bool (const VdfNode &)>;
 
    VDF_API
    static void Traverse(
        const VdfMaskedOutputVector &outputs,
        const NodeCallback          &nodeCallback,
        CallbackMode                callbackMode=CallbackModeAllNodes);
 
    using ConnectionCallback = std::function<
        bool (const VdfConnection &, const VdfMask &)> ;
 
    VDF_API
    static void TraverseWithConnectionCallback(
        const VdfMaskedOutputVector &outputs,
        const ConnectionCallback &connectionCallback);
 
 
 
 
    using NodePathCallback = std::function<
        bool (const VdfNode &node, const VdfObjectPtrVector &path)>;
 
    using ConnectionPathCallback = std::function<
        bool (const VdfConnection &, const VdfMask &,
            const VdfObjectPtrVector &)>;
 
    VDF_API
    static void TraverseWithPath(
        const VdfMaskedOutputVector  &outputs,
        const NodePathCallback       &nodePathCallback,
        const ConnectionPathCallback &connectionPathCallback,
        CallbackMode                 callbackMode=CallbackModeAllNodes);
 
 
private:
 
    // A type used to represent an input in a priority queue.
    class _PrioritizedOutput;
 
    // A map from pool chain index to prioritized output, used to ensure that we
    // process outputs in their order in the pool chain.
    //
    // Note that using a std::map<> gives us the _PrioritizedOutputs sorted by
    // the pool chain index.
    //
    typedef std::map<VdfPoolChainIndex, _PrioritizedOutput,
                     std::greater<VdfPoolChainIndex> > _PrioritizedOutputMap;
 
    // An individual stack frame in the traversal state.
    class _StackFrame;
 
    // Type used to identify the masks that have already been visited for
    // traversed connections.
    typedef TfHashMap<const VdfConnection *, VdfMask::Bits, TfHash>
        _VisitedConnections;
    
    // This struct embodies the total state of a sparse traversal.
    struct _TraversalState;
 
    // Helper to initialize a traversal.
    static void _InitTraversal(
        const VdfMaskedOutputVector &outputs,
        _TraversalState             *state,
        const CallbackMode          callbackMode=CallbackModeAllNodes);
 
    // Helper to traverse an output.
    static void _TraverseOutput(
        _TraversalState     *state,
        const _StackFrame    &frame,
        const CallbackMode  callbackMode);
 
    // Adapter that takes a NodeCallback and acts like a NodePathCallback by
    // ignoring the path.
    //
    // XXX:optimization
    // Using this means we do 2 std function calls for each call to the client
    // provided callback.  That's avoidable if we factor the code differently.
    //
    static bool _NodePathCallbackAdapter(
        const NodeCallback       &nodeCallback,
        const VdfNode            &node,
        const VdfObjectPtrVector &)
    {
        return nodeCallback(node);
    }
 
    // Adapter that takes a ConnectionCallback and acts like a ConnectionPathCallback
    // by ignoring the path.
    //
    static bool _ConnectionPathCallbackAdapter(
        const ConnectionCallback &connectionCallback,
        const VdfConnection      &connection,
        const VdfMask            &dependencyMask,
        const VdfObjectPtrVector &)
    {
        return connectionCallback(connection, dependencyMask);
    }
 
};
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif