sparseVectorizedInputTraverser.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_INPUT_TRAVERSER_H
#define PXR_EXEC_VDF_SPARSE_VECTORIZED_INPUT_TRAVERSER_H
 
 
#include "pxr/pxr.h"
 
#include "pxr/exec/vdf/api.h"
#include "pxr/exec/vdf/connection.h"
#include "pxr/exec/vdf/maskedOutputVector.h"
#include "pxr/exec/vdf/object.h"
#include "pxr/exec/vdf/poolChainIndex.h"
#include "pxr/exec/vdf/sparseOutputTraverser.h"
 
#include "pxr/base/tf/denseHashMap.h"
#include "pxr/base/tf/hashmap.h"
#include "pxr/base/tf/stl.h"
 
#include <functional>
#include <unordered_map>
#include <vector>
 
PXR_NAMESPACE_OPEN_SCOPE
 
class VdfNode;
 
class VdfSparseVectorizedInputTraverser
{
public:
 
    enum CallbackMode
    {
        CallbackModeAllNodes,
 
        CallbackModeTerminalNodes
    };
 
 
    using NodeCallback = std::function<
        bool (const VdfNode &, const TfBits &)>;
 
    VDF_API
    void Traverse(
        const VdfMaskedOutputVector &sharedMaskedOutputs,
        const NodeCallback          &nodeCallback,
        CallbackMode                callbackMode);
 
    using ConnectionCallback = std::function<
        bool (const VdfConnection &, const TfBits &)>;
 
    VDF_API
    void TraverseWithConnectionCallback(
        const VdfMaskedOutputVector &sharedMaskedOutputs,
        const ConnectionCallback    &connectionCallback);
 
 
private:
 
    // Helper class that holds a set of unique masks along with their request
    // bits.
    class _MasksToRequestsMap
    {
        // Map of unique masks to request indices using them.
        typedef
            TfDenseHashMap<VdfMask, TfBits, VdfMask::HashFunctor>
            _MaskToRequestBitsMap;
 
    public:
    
        // Ctor to initialize an empty object.
        _MasksToRequestsMap(size_t numRequests = 0)
        :   _numRequests(numRequests) {}
        
        // Ctor to initialize /w a single \p mask and \p requestBits.
        _MasksToRequestsMap(const VdfMask &mask, const TfBits &requestBits)
        :   _numRequests(requestBits.GetSize()) {
            _maskToRequestBitsMap[mask] = requestBits;
        }
        
        // Adds \p mask @ \p requestIndex.
        void AddMask(const VdfMask &mask, size_t requestIndex) {
 
            static TfBits empty;    
    
            std::pair<_MaskToRequestBitsMap::iterator, bool> res =
                _maskToRequestBitsMap.insert(std::make_pair(mask, empty));
                
            if (res.second) {
                res.first->second.Resize(_numRequests);
                res.first->second.ClearAll();
            }
            
            TF_VERIFY(!res.first->second.IsSet(requestIndex));
            res.first->second.Set(requestIndex);
        }
        
        // Adds \p mask with \p requestBits.
        void AddMask(const VdfMask &mask, const TfBits &requestBits) {
 
            std::pair<_MaskToRequestBitsMap::iterator, bool> res =
                _maskToRequestBitsMap.insert(std::make_pair(mask, requestBits));
                
            // If we didn't succeed to insert mask as a new entry, we must merge
            // in our new requestBits.
            
            if (!res.second)
                res.first->second |= requestBits;
        }
        
        // Iteration support.
        typedef _MaskToRequestBitsMap::const_iterator const_iterator;
        
        const_iterator begin() const {
            return _maskToRequestBitsMap.begin();
        }
        
        const_iterator end() const {
            return _maskToRequestBitsMap.end();
        }
        
        // Returns the request bits for \p mask.  Note that mask doesn't need
        // to be an exact match.
        const TfBits *GetRequestBits(const VdfMask &mask) const;
    
    private:
    
        size_t _numRequests;
    
        _MaskToRequestBitsMap _maskToRequestBitsMap;
    };
 
    // Helper to kick off the traversal.
    void _Traverse(const VdfMaskedOutputVector &sharedMaskedOutputs);
 
    // Helper to traverse an output.
    void _TraverseOutput(
        const VdfOutput           *output,
        const _MasksToRequestsMap &masks);
 
private:
 
    // The callback to use.
    NodeCallback _nodeCallback;
    ConnectionCallback _connectionCallback;
    
    // The current callback mode.
    CallbackMode _callbackMode;
    
    // Type used to identify the masks/request-bits that have already been
    // visited for traversed connections.  Note that we can't bunch together
    // all seen dependency bits along all seen request bits, because we could
    // have say two cycles through a single connection.  The first cycle would
    // manage to set all dependency bits there are and when the second cycle
    // for different request bits visits the connection the second time (since
    // there are two cycles) we would believe we would have seen that second
    // request with the second dependency mask already.
 
    typedef
        TfHashMap<const VdfConnection *, _MasksToRequestsMap, TfHash>
        _VisitedConnections;
 
    _VisitedConnections _visitedConnections;
    
    // The traversal stack frames, used as the stack. We are using an
    // unordered_map, because begin() will be called frequently and entries
    // will be erased from the front of the map.
    typedef
        std::unordered_map<const VdfOutput *, _MasksToRequestsMap, TfHash>
        _Stack;
 
    _Stack _stack;
    
    // A type used to represent an input in a priority queue.
    typedef std::pair<const VdfOutput *, _MasksToRequestsMap> _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 (the int key).
    //
    typedef std::map<VdfPoolChainIndex, _PrioritizedOutput,
                     std::greater<VdfPoolChainIndex> > _PrioritizedOutputMap;
 
    _PrioritizedOutputMap _prioritizedOutputs;
    
    // Initialized, empty _MasksToRequestsMap.
    _MasksToRequestsMap _emptyRequestToMaskMap;
};
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif