mask.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_MASK_H
#define PXR_EXEC_VDF_MASK_H
 
 
#include "pxr/pxr.h"
 
#include "pxr/exec/vdf/api.h"
 
#include "pxr/base/tf/compressedBits.h"
#include "pxr/base/tf/delegatedCountPtr.h"
#include "pxr/base/tf/diagnostic.h"
#include "pxr/base/tf/staticData.h"
 
#include <atomic>
#include <functional>
#include <iosfwd>
#include <string>
#include <utility>
 
PXR_NAMESPACE_OPEN_SCOPE
 
class VdfMask
{
    class _BitsImpl;
 
public:
    typedef TfCompressedBits Bits;
    
    VdfMask() {}
    
    explicit VdfMask(size_t size) {
        // If size == 0, we want to leave the optional _bits uninitialized.
        // This is important, because we use the uninitialized optional as a
        // sentinal for a zero size mask, and we need to be consistent about
        // that.
        if (size != 0) {
            _bits = _FindOrInsert(VdfMask::Bits(size));
        }
    }
 
    explicit VdfMask(VdfMask::Bits const &bits) {
        // If the bits denote a 1x1 mask, use the static 1x1 mask for
        // initialization. This prevents a call to _FindOrInsert, which locks
        // on the mask registry.
        if (bits.GetSize() == 1 && bits.AreAllSet()) {
            *this = _GetAllOnes1();
        }
        
        // If size == 0, we want to leave the optional _bits uninitialized.
        // This is important, because we use the uninitialized optional as a
        // sentinal for a zero size mask, and we need to be consistent about
        // that.
        else if (bits.GetSize() != 0) {
            _bits = _FindOrInsert(bits);
        }
    }
 
    explicit VdfMask(VdfMask::Bits &&bits) {
        if (bits.GetSize() != 0) {
            _bits = _FindOrEmplace(std::move(bits));
        }
    }
 
    void Swap(VdfMask &rhs) noexcept {
        _bits.swap(rhs._bits);
    }
 
    friend void swap(VdfMask &lhs, VdfMask &rhs) noexcept {
        lhs.Swap(rhs);
    }
 
    void SetAll() {
        if (!_bits) {
            return;
        }
 
        VdfMask::Bits bits(_bits->Get().GetSize());
        bits.Complement();
        _bits = _FindOrInsert(bits);
    }
    
    void SetIndex(size_t index) {
        if (!TF_VERIFY(_bits)) {
            return;
        }
 
        VdfMask::Bits copy(_bits->Get());
        copy.Set(index);
        _bits = _FindOrEmplace(std::move(copy));
    }
 
    bool IsSet(size_t index) const {
        if (!TF_VERIFY(_bits)) {
            return false;
        }
 
        return _bits->Get().IsSet(index);
    }
 
    void ClearIndex(size_t index) {
        if (!TF_VERIFY(_bits)) {
            return;
        }
 
        VdfMask::Bits copy(_bits->Get());
        copy.Clear(index);
        _bits = _FindOrEmplace(std::move(copy));
    }
 
    size_t GetSize() const {
        if (!_bits) {
            return 0;
        }
 
        return _bits->Get().GetSize(); 
    }
 
    bool IsEmpty() const {
        return !_bits;
    }
 
    bool Overlaps(const VdfMask &mask) const {
        if (_bits == mask._bits) {
            return IsAnySet();
        }
 
        return GetBits().HasNonEmptyIntersection(mask.GetBits());
    }
 
    bool Contains(const VdfMask &mask) const {
        if (_bits == mask._bits) {
            return true;
        }
 
        return !mask.GetBits().HasNonEmptyDifference(GetBits());
    }
 
    bool IsAllOnes() const {
        if (!_bits) {
            return true;
        }
 
        return _bits->Get().AreAllSet();
    }
 
    bool IsAllZeros() const {
        if (!_bits) {
            return true;
        }
 
        return _bits->Get().AreAllUnset();
    }
 
    bool IsAnySet() const {
        if (!_bits) {
            return false;
        }
 
        return _bits->Get().IsAnySet();
    }
 
    size_t GetFirstSet() const {
        if (!_bits) {
            return 0;
        }
 
        return _bits->Get().GetFirstSet();
    }
 
    size_t GetLastSet() const {
        if (!_bits) {
            return 0;
        }
 
        return _bits->Get().GetLastSet();
    }
 
    size_t GetNumSet() const {
        if (!_bits) {
            return 0;
        }
 
        return _bits->Get().GetNumSet();
    }
 
    bool IsContiguous() const {
        if (!_bits) {
            return false;
        }
 
        return _bits->Get().AreContiguouslySet();
    }
 
 
    bool operator==(const VdfMask &rhs) const {
        return _bits == rhs._bits;
    }
 
    bool operator!=(const VdfMask &rhs) const {
        return !(*this == rhs);
    }
 
    struct ArbitraryLessThan
    {
        bool operator()(const VdfMask &lhs, const VdfMask &rhs) const
        {
            return lhs._bits < rhs._bits;
        }
    };
 
    VdfMask &operator&=(const VdfMask &rhs) {
        if (_bits == rhs._bits) {
            return *this;
        }
 
        _bits = _FindOrEmplace(GetBits() & rhs.GetBits());
        return *this;
    }
 
    VdfMask operator&(const VdfMask &rhs) const {
        VdfMask r(*this);
        r &= rhs;
        return r;
    }
 
    VdfMask &operator|=(const VdfMask &rhs) {
        if (_bits == rhs._bits) {
            return *this;
        }
 
        _bits = _FindOrEmplace(GetBits() | rhs.GetBits());
        return *this;
    }
 
    VdfMask operator|(const VdfMask &rhs) const {
        VdfMask r(*this);
        r |= rhs;
        return r;
    }
 
    VdfMask &operator^=(const VdfMask &rhs) {
        if (!_bits && TF_VERIFY(!rhs._bits)) {
            return *this;
        }
 
        _bits = _FindOrEmplace(GetBits() ^ rhs.GetBits());
        return *this;
    }
 
    VdfMask operator^(const VdfMask &rhs) const {
        VdfMask r(*this);
        r ^= rhs;
        return r;
    }
 
    VdfMask &operator-=(const VdfMask &rhs) {
        if (!_bits && TF_VERIFY(!rhs._bits)) {
            return *this;
        }
 
        VdfMask::Bits copy = GetBits();
        copy -= rhs.GetBits();
        _bits = _FindOrEmplace(std::move(copy));
        return *this;
    }
 
    VdfMask operator-(const VdfMask &rhs) const {
        VdfMask r(*this);
        r -= rhs;
        return r;
    }
 
    VdfMask &Complement() {
        if (!_bits) {
            return *this;
        }
 
        _bits = _FindOrEmplace(
            VdfMask::Bits(_bits->Get(), VdfMask::Bits::ComplementTag));
        return *this;
    }
 
    VdfMask &SetOrAppend(const VdfMask &rhs) {
        if (!_bits) {
            *this = rhs;
        } else {
            *this |= rhs;
        }
        return *this;
    }
 
 
 
    class iterator {
        using _BaseIterator = VdfMask::Bits::AllSetView::const_iterator;
 
    public:
        using value_type = _BaseIterator::value_type;
 
        iterator() {}
 
        bool operator==(const iterator &rhs) const {
            return _it == rhs._it;
        }
 
        bool operator!=(const iterator &rhs) const {
            return !operator==(rhs);
        }
 
        value_type operator*() const {
            return *_it;
        }
 
        iterator &operator++() {
            ++_it;
            return *this;
        }
 
        bool IsAtEnd() const {
            return _it.IsAtEnd();
        }
 
        void AdvanceToEnd() {
            _it = _BaseIterator();
        }
 
        int AdvanceTo(value_type index) {
            if (_it.IsAtEnd()) {
                return 0;
            }
 
            // The index must be ahead of the current iterator position.
            TF_DEV_AXIOM(index >= *_it);
 
            // We can simply increment the underlying VdfMask::Bits iterator
            // until we reach (past) index.
            while (!_it.IsAtEnd() && *_it < index) {
                ++_it;
            }
            return *_it;
        }
 
    private:
 
        // Only a mask is a allowed to create an iterator.
        iterator(const VdfMask::Bits *bits) :
            _it(bits->GetAllSetView().begin())
        {}
 
        friend class VdfMask;
 
        // The wrapped VdfMask::Bits iterator
        _BaseIterator _it;
    };
 
 
    iterator begin() const {
        if (!_bits) {
            return iterator(&VdfMask::Bits::GetEmpty());
        }
 
        return iterator(&_bits->Get());
    }
 
 
    static VdfMask AllOnes(size_t size) {
        // special-case all-ones of size 1 and 0
        if (size == 0) {
            return VdfMask();
        } else if (size == 1) {
            return _GetAllOnes1();
        }
 
        VdfMask::Bits bits(size);
        bits.SetAll();
        return VdfMask(bits);
    }
 
    static VdfMask AllZeros(size_t size) {
        // special-case all-zeros of size 0
        if (size == 0) {
            return VdfMask();
        }
 
        return VdfMask(size);
    }
 
 
    std::string GetRLEString() const {
        if (!_bits) {
            return std::string();
        }
 
        return _bits->Get().GetAsRLEString();
    }
 
    size_t GetMemoryUsage() const {
        if (!_bits) {
            return 0;
        }
 
        return _bits->Get().GetAllocatedSize();
    }
 
 
 
 
    VdfMask::Bits const &GetBits() const {
        if (!_bits) {
            return VdfMask::Bits::GetEmpty();
        }
 
        return _bits->Get();
    }
 
    size_t GetHash() const {
        return std::hash<_BitsImpl*>()(_bits.get());
    }
 
    struct HashFunctor {
        size_t operator()(const VdfMask &mask) const {
            return mask.GetHash();
        }
    };
    
    
private:
 
    struct _AllOnes1Factory
    {
        static VdfMask * New()
        {
            return new VdfMask(_AllOnes1Factory());
        }
    };
 
    explicit VdfMask(const _AllOnes1Factory &) {
        Bits allOnes1Bits(1);
        allOnes1Bits.SetAll();
        _bits = _FindOrInsert(allOnes1Bits);
    }
 
    static VdfMask _GetAllOnes1() {
        return *_allOnes1;
    }
 
    // Befriend the stream operator so that VdfMasks support output streaming.
    friend VDF_API std::ostream & operator<<(
        std::ostream &os, const VdfMask &mask);
 
    // Refcounted hash table nodes for VdfMask::Bits.
    //
    class _BitsImpl
    {
    public:
        // Non-copyable
        _BitsImpl(const _BitsImpl &) = delete;
        _BitsImpl& operator=(const _BitsImpl &) = delete;
 
        // Non-movable
        _BitsImpl(_BitsImpl &&) = delete;
        _BitsImpl& operator=(_BitsImpl &&) = delete;
 
        // Provide const access to the bits.  Flyweighting requires that
        // the value is never mutated.
        //
        const VdfMask::Bits &Get() const { return _bits; }
 
        // Return the pre-computed hash value for _bits.
        //
        // Implemented in MaskRegistry.h
        //
        size_t GetHash() const;
 
    private:
        // next points to the next entry in the hash bucket (if any) for
        // \p bits.
        //
        _BitsImpl(_BitsImpl *next, size_t hash, VdfMask::Bits &&bits);
 
        friend inline void TfDelegatedCountIncrement(_BitsImpl *p) noexcept;
        friend inline void TfDelegatedCountDecrement(_BitsImpl *p) noexcept;
 
        friend class Vdf_MaskRegistry;
 
        _BitsImpl *_next;
        size_t _hash;
        VdfMask::Bits _bits;
        std::atomic<int> _refCount;
        // Note that the resurrection count is bounded by the number of threads
        // concurrently accessing masks, thus a 16-bit integer is sufficient.
        std::atomic<uint16_t> _resurrectionCount;
        bool _isImmortal;
    };
 
    friend inline void TfDelegatedCountIncrement(_BitsImpl *p) noexcept;
    friend inline void TfDelegatedCountDecrement(_BitsImpl *p) noexcept;
 
    friend class Vdf_MaskRegistry;
 
    typedef TfDelegatedCountPtr<_BitsImpl> _BitsImplRefPtr;
 
    // Return a ref ptr to the \c _BitsImpl corresponding to \p *bits.  If an
    // existing _BitsImpl for \p *bits is not found, create a new one by
    // *moving* the contents out of \p *bits and into the new \c _BitsImpl.
    //
    // Do not use \p *bits after passing it to this function.
    //
    VDF_API
    static _BitsImplRefPtr _FindOrEmplace(VdfMask::Bits &&bits);
 
    // Return a ref ptr to the \c _BitsImpl corresponding to \p bits.  If an
    // existing _BitsImpl for \p bits is not found, create a new one by
    // copying \p bits.
    //
    VDF_API
    static _BitsImplRefPtr _FindOrInsert(const VdfMask::Bits &bits);
 
    // Erase the _BitsImpl pointed to by \p bits.
    //
    VDF_API
    static void _EraseBits(_BitsImpl *bits);
 
private:
    // Default constructed / empty masks are represented as null
    // _BitsImplRefPtr.
    _BitsImplRefPtr _bits;
 
    // AllOnes mask of size 1 optimization.
    VDF_API static TfStaticData<VdfMask, _AllOnes1Factory> _allOnes1;
};
 
// Specialize TfDelegatedCountPtr operations for VdfMask::_BitsImpl.
inline void TfDelegatedCountIncrement(VdfMask::_BitsImpl *p) noexcept
{
    // For immortal masks there is no need to maintain the reference count.
    if (p->_isImmortal) {
        return;
    }
 
    // There's no need for a stronger memory ordering here because we can only
    // increase the ref count by way of an existing reference and sharing an
    // existing VdfMask between threads requires external synchronization,
    // just like any other non-atomic type.
    //
    // Note that Vdf_MaskRegistry manages reference counting and serialization
    // for threads that are looking up the same bits concurrently rather than
    // simply making copies of an existing VdfMask.
    p->_refCount.fetch_add(1, std::memory_order_relaxed);
}
inline void TfDelegatedCountDecrement(VdfMask::_BitsImpl *p) noexcept
{
    // For immortal masks there is no need to maintain the reference count.
    if (p->_isImmortal) {
        return;
    }
 
    // Many threads may decrement the ref count but only one thread will be
    // responsible for deleting it.  However, we must ensure that all of the
    // memory operations in all of the threads happen before the final thread
    // performs the deletion.  To establish this happens-before relationship,
    // we need a release-acquire pair of atomic operations.
    const int prevRC = p->_refCount.fetch_sub(1, std::memory_order_release);
    if (prevRC == 1) {
        // Use an acquire fence here because we only need to synchronize with
        // the decrement accesses when we're about to perform the deletion.
        std::atomic_thread_fence(std::memory_order_acquire);
        VdfMask::_EraseBits(p);
    }
}
 
// Output stream operator
VDF_API
std::ostream &
operator<<(std::ostream &os, const VdfMask &mask);
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif