sparseVectorizedOutputTraverser.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_VECTORIZED_OUTPUT_TRAVERSER_H
#define PXR_EXEC_VDF_SPARSE_VECTORIZED_OUTPUT_TRAVERSER_H
 
 
#include "pxr/pxr.h"
 
#include "pxr/exec/vdf/api.h"
#include "pxr/exec/vdf/mask.h"
#include "pxr/exec/vdf/maskMemoizer.h"
#include "pxr/exec/vdf/maskedOutput.h"
#include "pxr/exec/vdf/maskedOutputVector.h"
#include "pxr/exec/vdf/poolChainIndex.h"
#include "pxr/base/tf/smallVector.h"
 
#include <tbb/concurrent_unordered_map.h>
 
#include <functional>
#include <map>
#include <vector>
 
PXR_NAMESPACE_OPEN_SCOPE
 
class VdfNode;
 
class VdfSparseVectorizedOutputTraverser
{
public:
 
    using NodeCallback = std::function<bool (const VdfNode &, size_t)>;
 
    VDF_API
    void Traverse(
        const VdfMaskedOutputVector &outputs,
        const NodeCallback &callback);
 
    VDF_API
    void Invalidate();
 
private:
 
    // A cached dependency on a pool output.
    struct _PoolDependency {
        VdfPoolChainIndex poolChainIndex;
        VdfMaskedOutput maskedOutput;
    };
 
    // An entry with cached dependencies.
    struct _Dependencies {
        TfSmallVector<VdfMaskedOutput, 1> outputs;
        TfSmallVector<_PoolDependency, 1> poolOutputs;
        TfSmallVector<const VdfNode *, 1> nodes;
    };
 
    // A pair of output pointer and mask pointer used for building the
    // traversal stack (and queue.) The pointer-to-mask is used in order to
    // avoid expensive traffic on the mask ref count.
    struct _OutputAndMask {
        VdfOutput *output;
        const VdfMask *mask;
    };
 
    // A map with entries of outputs that have been visited, and with which
    // mask these outputs have been visited with.
    using _VisitedOutputs =
        TfHashMap<const VdfOutput *, const VdfMask *, TfHash>;
 
    // The type of output stack used to guide the traversal.
    using _OutputStack = std::vector<_OutputAndMask>;
 
    // The type of queue used to guide the traversal along the pool.
    using _PoolQueue = std::map<const VdfPoolChainIndex, _OutputAndMask>;
 
    // Returns true if the output should be visited and false if it already has
    // been visited with the given mask.
    bool _Visit(
        const _OutputAndMask &outputAndMask,
        _VisitedOutputs *visitedOutputs);
 
    // Start a new traversal at the given output.
    void _Traverse(
        size_t index,
        const VdfMaskedOutput &maskedOutput,
        const NodeCallback &callback);
 
    // Visits a single output.
    void _TraverseOutput(
        size_t index,
        const _OutputAndMask &outputAndMask,
        const NodeCallback &callback,
        _OutputStack *stack,
        _PoolQueue *queue);
 
    // Queue a pool output.
    void _QueuePoolOutput(
        const VdfPoolChainIndex &poolChainIndex,
        const _OutputAndMask &outputAndMask,
        _PoolQueue *queue);
 
    // Take a shortcut through the pool, if possible.
    bool _TakePoolShortcut(
        const _OutputAndMask &outputAndMask,
        _PoolQueue *queue);
 
    // Retrieves the dependencies for a single output, if cached, or computes
    // dependencies of uncached.
    const _Dependencies &_GetDependencies(
        const _OutputAndMask &outputAndMask);
 
    // Computes the dependencies for a single output.
    void _ComputeDependencies(
        const _OutputAndMask &outputAndMask,
        _Dependencies *dependencies);
 
    // The cached dependencies.
    using _DependencyMap = tbb::concurrent_unordered_map<
        VdfMaskedOutput, _Dependencies, VdfMaskedOutput::Hash>;
    _DependencyMap _dependencyMap;
 
    // The memoized mask operations.
    VdfMaskMemoizer<tbb::concurrent_unordered_map> _maskMemoizer;
};
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif