EIC code displayed by LXR master/​include/​opencascade/​NCollection_PackedMap.hxx	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-09-21 09:17:57

 // Copyright (c) 2005-2026 OPEN CASCADE SAS
 //
 // This file is part of Open CASCADE Technology software library.
 //
 // This library is free software; you can redistribute it and/or modify it under
 // the terms of the GNU Lesser General Public License version 2.1 as published
 // by the Free Software Foundation, with special exception defined in the file
 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
 // distribution for complete text of the license and disclaimer of any warranty.
 //
 // Alternatively, this file may be used under the terms of Open CASCADE
 // commercial license or contractual agreement.
 
 #ifndef NCollection_PackedMap_HeaderFile
 #define NCollection_PackedMap_HeaderFile
 
 #include <Standard.hxx>
 #include <Standard_DefineAlloc.hxx>
 #include <Standard_NoSuchObject.hxx>
 #include <Standard_OStream.hxx>
 #include <NCollection_Array1.hxx>
 #include <NCollection_Primes.hxx>
 
 #include <cstdint>
 #include <cstring>
 #include <type_traits>
 
 //! @brief Optimized Map for integer values of various integral types.
 //!
 //! This template class provides a memory-efficient storage for sets of integers.
 //! Each block of BitsPerBlock (32 or 64) consecutive integers is stored compactly
 //! using bit manipulation. The block size is automatically selected based on
 //! the integer type: 32 bits for int/unsigned, 64 bits for int64_t/size_t.
 //!
 //! @tparam IntType The integral type to store (int, unsigned int, int64_t, size_t, etc.)
 template <typename IntType>
 class NCollection_PackedMap
 {
   static_assert(std::is_integral<IntType>::value,
                 "NCollection_PackedMap requires an integral type");
 
 public:
   DEFINE_STANDARD_ALLOC
 
   //! True if the integer type is larger than 32 bits
   static constexpr bool Is64Bit = sizeof(IntType) > 4;
 
   //! The block type for storing packed bits
   using BlockType = typename std::conditional<Is64Bit, uint64_t, uint32_t>::type;
 
   //! The index type for addressing blocks
   using IndexType = typename std::conditional<sizeof(IntType) <= 4, uint32_t, uint64_t>::type;
 
   //! Number of bits per block
   static constexpr int BitsPerBlock = Is64Bit ? 64 : 32;
 
 private:
   //! Number of low bits used for position within a block
   static constexpr int MaskLowBits = Is64Bit ? 6 : 5;
 
   //! Mask for low bits (position within block)
   static constexpr IndexType MASK_LOW = (IndexType(1) << MaskLowBits) - 1;
 
   //! Mask for high bits (block base address)
   static constexpr IndexType MASK_HIGH = ~MASK_LOW;
 
   //! @brief Class implementing a block of consecutive integer values as a node.
   //!
   //! For 32-bit types: stores 32 consecutive values
   //! For 64-bit types: stores 64 consecutive values
   //!
   //! The data are stored as:
   //! - myMask: contains the count-1 in low bits and block base address in high bits
   //! - myData: bit field where each bit indicates presence of corresponding integer
   class PackedMapNode
   {
   public:
     PackedMapNode(PackedMapNode* thePtr = nullptr)
         : myNext(thePtr),
           myMask(0),
           myData(0)
     {
     }
 
     PackedMapNode(IntType theValue, PackedMapNode*& thePtr)
         : myNext(thePtr),
           myMask(static_cast<IndexType>(theValue) & MASK_HIGH),
           myData(BlockType(1) << (static_cast<IndexType>(theValue) & MASK_LOW))
     {
     }
 
     PackedMapNode(IndexType theMask, BlockType theData, PackedMapNode* thePtr)
         : myNext(thePtr),
           myMask(theMask),
           myData(theData)
     {
     }
 
     IndexType Mask() const { return myMask; }
 
     BlockType Data() const { return myData; }
 
     IndexType& ChangeMask() { return myMask; }
 
     BlockType& ChangeData() { return myData; }
 
     //! Compute the sequential index of this packed node in the map.
     IntType Key() const { return static_cast<IntType>(myMask & MASK_HIGH); }
 
     //! Return the number of set integer keys.
     size_t NbValues() const { return size_t(myMask & MASK_LOW) + 1; }
 
     //! Return TRUE if this packed node is not empty.
     bool HasValues() const { return (myData != 0); }
 
     //! Return TRUE if the given integer key is set within this packed node.
     bool HasValue(IntType theValue) const
     {
       return (myData & (BlockType(1) << (static_cast<IndexType>(theValue) & MASK_LOW))) != 0;
     }
 
     //! Add integer key to this packed node.
     //! @return TRUE if key has been added
     bool AddValue(IntType theValue)
     {
       const BlockType aValBit = BlockType(1) << (static_cast<IndexType>(theValue) & MASK_LOW);
       if ((myData & aValBit) == 0)
       {
         myData ^= aValBit;
         ++myMask;
         return true;
       }
       return false;
     }
 
     //! Delete integer key from this packed node.
     //! @return TRUE if key has been deleted
     bool DelValue(IntType theValue)
     {
       const BlockType aValBit = BlockType(1) << (static_cast<IndexType>(theValue) & MASK_LOW);
       if ((myData & aValBit) != 0)
       {
         myData ^= aValBit;
         myMask--;
         return true;
       }
       return false;
     }
 
     //! Return the next node having the same hash code.
     PackedMapNode* Next() const { return myNext; }
 
     //! Set the next node having the same hash code.
     void SetNext(PackedMapNode* theNext) { myNext = theNext; }
 
   public:
     //! Support of Map interface.
     size_t HashCode(size_t theUpper) const
     {
       return static_cast<size_t>(myMask >> MaskLowBits) % theUpper + 1;
     }
 
     //! Support of Map interface.
     bool IsEqual(IndexType theOther) const
     {
       return (myMask >> MaskLowBits) == (static_cast<IndexType>(theOther));
     }
 
   private:
     PackedMapNode* myNext;
     IndexType      myMask;
     BlockType      myData;
   };
 
 public:
   //! Iterator of class NCollection_PackedMap.
   class Iterator
   {
   public:
     //! Empty Constructor.
     Iterator()
         : myBuckets(nullptr),
           myNode(nullptr),
           myNbBuckets(0),
           myBucket(0),
           myIntMask(~BlockType(0)),
           myKey(0)
     {
     }
 
     //! Constructor.
     Iterator(const NCollection_PackedMap& theMap)
         : myBuckets(theMap.myData1),
           myNode(nullptr),
           myNbBuckets(theMap.myData1 != nullptr ? theMap.myNbBuckets : 0),
           myBucket(0),
           myIntMask(~BlockType(0))
     {
       findFirst();
       myKey = myNode != nullptr ? NCollection_PackedMap::findNext(myNode, myIntMask) : 0;
     }
 
     //! Re-initialize with the same or another Map instance.
     void Initialize(const NCollection_PackedMap& theMap)
     {
       myBuckets   = theMap.myData1;
       myBucket    = 0;
       myNode      = nullptr;
       myNbBuckets = theMap.myData1 != nullptr ? theMap.myNbBuckets : 0;
       findFirst();
 
       myIntMask = ~BlockType(0);
       myKey     = myNode != nullptr ? findNext(myNode, myIntMask) : 0;
     }
 
     //! Restart the iteration
     void Reset()
     {
       myBucket = 0;
       myNode   = nullptr;
       findFirst();
 
       myIntMask = ~BlockType(0);
       myKey     = myNode != nullptr ? findNext(myNode, myIntMask) : 0;
     }
 
     //! Query the iterated key.
     IntType Key() const
     {
       Standard_NoSuchObject_Raise_if((myIntMask == ~BlockType(0)),
                                      "NCollection_PackedMap::Iterator::Key");
       return myKey;
     }
 
     //! Return TRUE if iterator points to the node.
     bool More() const { return myNode != nullptr; }
 
     //! Increment the iterator
     void Next()
     {
       for (; myNode != nullptr; next())
       {
         myKey = NCollection_PackedMap::findNext(myNode, myIntMask);
         if (myIntMask != ~BlockType(0))
         {
           break;
         }
       }
     }
 
   private:
     //! Find the first non-empty bucket starting from myBucket.
     void findFirst()
     {
       if (myBuckets == nullptr)
       {
         return;
       }
       for (; myBucket <= myNbBuckets; ++myBucket)
       {
         myNode = myBuckets[myBucket];
         if (myNode != nullptr)
         {
           return;
         }
       }
     }
 
     //! Advance to the next node (may cross bucket boundaries).
     void next()
     {
       if (myBuckets == nullptr)
       {
         return;
       }
       if (myNode != nullptr)
       {
         myNode = myNode->Next();
         if (myNode != nullptr)
         {
           return;
         }
       }
       ++myBucket;
       while (myBucket <= myNbBuckets)
       {
         myNode = myBuckets[myBucket];
         if (myNode != nullptr)
         {
           return;
         }
         ++myBucket;
       }
     }
 
   private:
     PackedMapNode** myBuckets;
     PackedMapNode*  myNode;
     size_t          myNbBuckets;
     size_t          myBucket;
 
     BlockType myIntMask; //!< all bits set above the iterated position
     IntType   myKey;     //!< Currently iterated key
   };
 
 public:
   //! Constructor
   NCollection_PackedMap(const size_t theNbBuckets = 1)
       : myData1(nullptr),
         myNbBuckets(theNbBuckets),
         myNbPackedMapNodes(0),
         myExtent(0)
   {
   }
 
   //! Constructor (legacy int-taking).
   NCollection_PackedMap(const int theNbBuckets)
       : myData1(nullptr),
         myNbBuckets(theNbBuckets < 1 ? 1 : static_cast<size_t>(theNbBuckets)),
         myNbPackedMapNodes(0),
         myExtent(0)
   {
   }
 
   //! Copy constructor
   NCollection_PackedMap(const NCollection_PackedMap& theOther)
       : myData1(nullptr),
         myNbBuckets(1),
         myNbPackedMapNodes(0),
         myExtent(0)
   {
     Assign(theOther);
   }
 
   NCollection_PackedMap& operator=(const NCollection_PackedMap& theOther)
   {
     return Assign(theOther);
   }
 
   //! Move constructor
   NCollection_PackedMap(NCollection_PackedMap&& theOther) noexcept
       : myData1(theOther.myData1),
         myNbBuckets(theOther.myNbBuckets),
         myNbPackedMapNodes(theOther.myNbPackedMapNodes),
         myExtent(theOther.myExtent)
   {
     theOther.myData1            = nullptr;
     theOther.myNbBuckets        = 1;
     theOther.myNbPackedMapNodes = 0;
     theOther.myExtent           = 0;
   }
 
   //! Move assignment operator
   NCollection_PackedMap& operator=(NCollection_PackedMap&& theOther) noexcept
   {
     if (this != &theOther)
     {
       Clear();
       myData1                     = theOther.myData1;
       myNbBuckets                 = theOther.myNbBuckets;
       myNbPackedMapNodes          = theOther.myNbPackedMapNodes;
       myExtent                    = theOther.myExtent;
       theOther.myData1            = nullptr;
       theOther.myNbBuckets        = 1;
       theOther.myNbPackedMapNodes = 0;
       theOther.myExtent           = 0;
     }
     return *this;
   }
 
   //! Assignment operator
   NCollection_PackedMap& Assign(const NCollection_PackedMap& theOther)
   {
     if (this != &theOther)
     {
       Clear();
       if (!theOther.IsEmpty())
       {
         ReSize(theOther.myNbPackedMapNodes);
         const size_t nBucketsSrc = theOther.myNbBuckets;
         const size_t nBuckets    = myNbBuckets;
         for (size_t i = 0; i <= nBucketsSrc; ++i)
         {
           for (const PackedMapNode* p = theOther.myData1[i]; p != nullptr;)
           {
             const size_t aHashCode = p->HashCode(nBuckets);
             myData1[aHashCode]     = new PackedMapNode(p->Mask(), p->Data(), myData1[aHashCode]);
             ++myNbPackedMapNodes;
             p = p->Next();
           }
         }
       }
       myExtent = theOther.myExtent;
     }
     return *this;
   }
 
   //! Resize the map
   void ReSize(const size_t theNbBuckets)
   {
     size_t aNewBuck = NCollection_Primes::NextPrimeForMap(theNbBuckets);
     if (aNewBuck <= myNbBuckets)
     {
       if (!IsEmpty())
       {
         return;
       }
       aNewBuck = myNbBuckets;
     }
 
     PackedMapNode** aNewData = reinterpret_cast<PackedMapNode**>(
       Standard::AllocateOptimal((aNewBuck + 1) * sizeof(PackedMapNode*)));
     memset(aNewData, 0, (aNewBuck + 1) * sizeof(PackedMapNode*));
     if (myData1 != nullptr)
     {
       PackedMapNode** anOldData = myData1;
       for (size_t i = 0; i <= myNbBuckets; ++i)
       {
         for (PackedMapNode* p = anOldData[i]; p != nullptr;)
         {
           size_t         k = p->HashCode(aNewBuck);
           PackedMapNode* q = p->Next();
           p->SetNext(aNewData[k]);
           aNewData[k] = p;
           p           = q;
         }
       }
     }
 
     Standard::Free(myData1);
     myNbBuckets = aNewBuck;
     myData1     = aNewData;
   }
 
   //! Resize the map (legacy int-taking).
   void ReSize(const int theNbBuckets)
   {
     ReSize(static_cast<size_t>(theNbBuckets < 0 ? 0 : theNbBuckets));
   }
 
   //! Clear the map
   void Clear()
   {
     if (!IsEmpty())
     {
       for (size_t aBucketIter = 0; aBucketIter <= myNbBuckets; ++aBucketIter)
       {
         if (myData1[aBucketIter])
         {
           for (PackedMapNode* aSubNodeIter = myData1[aBucketIter]; aSubNodeIter != nullptr;)
           {
             PackedMapNode* q = aSubNodeIter->Next();
             delete aSubNodeIter;
             aSubNodeIter = q;
           }
         }
       }
     }
 
     myNbPackedMapNodes = 0;
     Standard::Free(myData1);
     myData1  = nullptr;
     myExtent = 0;
   }
 
   ~NCollection_PackedMap() { Clear(); }
 
   //! Add a key to the map
   //! @param[in] theKey the key to add
   //! @return true if the key was added, false if it already existed
   bool Add(const IntType theKey)
   {
     if (Resizable())
     {
       ReSize(myNbPackedMapNodes);
     }
 
     const IndexType aKeyInt     = packedKeyIndex(theKey);
     const size_t    aHashCode   = hashCode(aKeyInt, myNbBuckets);
     PackedMapNode*  aBucketHead = myData1[aHashCode];
     for (PackedMapNode* p = aBucketHead; p != nullptr; p = p->Next())
     {
       if (p->IsEqual(aKeyInt))
       {
         if (p->AddValue(theKey))
         {
           ++myExtent;
           return true;
         }
         return false;
       }
     }
 
     myData1[aHashCode] = new PackedMapNode(theKey, aBucketHead);
     ++myNbPackedMapNodes;
     ++myExtent;
     return true;
   }
 
   //! Check if the map contains a key
   //! @param[in] theKey the key to check
   //! @return true if the key is in the map
   bool Contains(const IntType theKey) const
   {
     if (IsEmpty())
     {
       return false;
     }
 
     const IndexType aKeyInt = packedKeyIndex(theKey);
     for (PackedMapNode* p = myData1[hashCode(aKeyInt, myNbBuckets)]; p != nullptr;)
     {
       if (p->IsEqual(aKeyInt))
       {
         return p->HasValue(theKey);
       }
       p = p->Next();
     }
     return false;
   }
 
   //! Remove a key from the map
   //! @param[in] theKey the key to remove
   //! @return true if the key was removed, false if it was not present
   bool Remove(const IntType theKey)
   {
     if (IsEmpty())
     {
       return false;
     }
 
     const IndexType aKeyInt     = packedKeyIndex(theKey);
     PackedMapNode*& aBucketHead = myData1[hashCode(aKeyInt, myNbBuckets)];
     PackedMapNode*  p           = aBucketHead;
     PackedMapNode*  q           = nullptr;
     while (p)
     {
       if (p->IsEqual(aKeyInt))
       {
         bool aResult = p->DelValue(theKey);
         if (aResult)
         {
           --myExtent;
           if (!p->HasValues())
           {
             --myNbPackedMapNodes;
             if (q != nullptr)
             {
               q->SetNext(p->Next());
             }
             else
             {
               aBucketHead = p->Next();
             }
             delete p;
           }
         }
         return aResult;
       }
       q = p;
       p = p->Next();
     }
     return false;
   }
 
   //! Returns the number of map buckets.
   size_t NbBuckets() const { return myNbBuckets; }
 
   //! Returns map extent (legacy int-returning API).
   int Extent() const { return static_cast<int>(myExtent); }
 
   //! Returns map extent (legacy int-returning API, synonym of Extent()).
   int Length() const { return static_cast<int>(myExtent); }
 
   //! Returns map extent.
   size_t Size() const { return myExtent; }
 
   //! Returns TRUE if map is empty.
   bool IsEmpty() const { return myNbPackedMapNodes == 0; }
 
   //! Query the minimal contained key value.
   IntType GetMinimalMapped() const
   {
     if (IsEmpty())
     {
       return std::numeric_limits<IntType>::max();
     }
 
     IntType              aResult    = std::numeric_limits<IntType>::max();
     const PackedMapNode* pFoundNode = nullptr;
     for (size_t i = 0; i <= myNbBuckets; ++i)
     {
       for (const PackedMapNode* p = myData1[i]; p != nullptr; p = p->Next())
       {
         const IntType aKey = p->Key();
         if (aResult > aKey)
         {
           aResult    = aKey;
           pFoundNode = p;
         }
       }
     }
     if (pFoundNode)
     {
       BlockType aFullMask = ~BlockType(0);
       aResult             = findNext(pFoundNode, aFullMask);
     }
     return aResult;
   }
 
   //! Query the maximal contained key value.
   IntType GetMaximalMapped() const
   {
     if (IsEmpty())
     {
       return std::numeric_limits<IntType>::lowest();
     }
 
     IntType              aResult    = std::numeric_limits<IntType>::lowest();
     const PackedMapNode* pFoundNode = nullptr;
     for (size_t i = 0; i <= myNbBuckets; ++i)
     {
       for (const PackedMapNode* p = myData1[i]; p != nullptr; p = p->Next())
       {
         const IntType aKey = p->Key();
         if (aResult < aKey)
         {
           aResult    = aKey;
           pFoundNode = p;
         }
       }
     }
     if (pFoundNode)
     {
       BlockType aFullMask = ~BlockType(0);
       aResult             = findPrev(pFoundNode, aFullMask);
     }
     return aResult;
   }
 
 public:
   //! @name Deprecated boolean operations (use NCollection_PackedMapAlgo instead)
 
   //! @deprecated Use NCollection_PackedMapAlgo::Union() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   void Union(const NCollection_PackedMap& theLeft, const NCollection_PackedMap& theRight);
 
   //! @deprecated Use NCollection_PackedMapAlgo::Unite() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool Unite(const NCollection_PackedMap& theOther);
 
   //! @deprecated Use NCollection_PackedMapAlgo::Intersection() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   void Intersection(const NCollection_PackedMap& theLeft, const NCollection_PackedMap& theRight);
 
   //! @deprecated Use NCollection_PackedMapAlgo::Intersect() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool Intersect(const NCollection_PackedMap& theOther);
 
   //! @deprecated Use NCollection_PackedMapAlgo::Subtraction() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   void Subtraction(const NCollection_PackedMap& theLeft, const NCollection_PackedMap& theRight);
 
   //! @deprecated Use NCollection_PackedMapAlgo::Subtract() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool Subtract(const NCollection_PackedMap& theOther);
 
   //! @deprecated Use NCollection_PackedMapAlgo::Difference() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   void Difference(const NCollection_PackedMap& theLeft, const NCollection_PackedMap& theRight);
 
   //! @deprecated Use NCollection_PackedMapAlgo::Differ() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool Differ(const NCollection_PackedMap& theOther);
 
   //! @deprecated Use NCollection_PackedMapAlgo::IsEqual() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool IsEqual(const NCollection_PackedMap& theOther) const;
 
   //! @deprecated Use NCollection_PackedMapAlgo::IsSubset() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool IsSubset(const NCollection_PackedMap& theOther) const;
 
   //! @deprecated Use NCollection_PackedMapAlgo::HasIntersection() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool HasIntersection(const NCollection_PackedMap& theOther) const;
 
   //! @deprecated Use NCollection_PackedMapAlgo::Contains() instead
   Standard_DEPRECATED("This method will be removed after OCCT 7.9 release. Use methods from "
                       "NCollection_PackedMapAlgo.hxx instead.")
   bool Contains(const NCollection_PackedMap& theOther) const;
 
 protected:
   //! Returns TRUE if resizing the map should be considered.
   bool Resizable() const { return IsEmpty() || (myNbPackedMapNodes > myNbBuckets); }
 
   //! Return an integer index for specified key.
   static IndexType packedKeyIndex(IntType theKey)
   {
     return static_cast<IndexType>(theKey) >> MaskLowBits;
   }
 
   //! Compute hash code for a key index.
   static size_t hashCode(IndexType theKeyIndex, size_t theNbBuckets)
   {
     return static_cast<size_t>(theKeyIndex) % theNbBuckets + 1;
   }
 
   //! Compute the population (i.e., the number of non-zero bits) of the block.
   //! The population is stored decremented as it is defined in PackedMapNode.
   static size_t population(IndexType& theMask, BlockType theData)
   {
     if constexpr (Is64Bit)
     {
       // 64-bit population count
       uint64_t aRes = theData - ((theData >> 1) & 0x5555555555555555ULL);
       aRes          = (aRes & 0x3333333333333333ULL) + ((aRes >> 2) & 0x3333333333333333ULL);
       aRes          = (aRes + (aRes >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
       aRes          = aRes + (aRes >> 8);
       aRes          = aRes + (aRes >> 16);
       aRes          = aRes + (aRes >> 32);
       theMask       = (theMask & MASK_HIGH) | ((static_cast<IndexType>(aRes) - 1) & MASK_LOW);
       return size_t(aRes & 0x7f);
     }
     else
     {
       // 32-bit population count
       uint32_t aRes =
         static_cast<uint32_t>(theData) - ((static_cast<uint32_t>(theData) >> 1) & 0x55555555);
       aRes    = (aRes & 0x33333333) + ((aRes >> 2) & 0x33333333);
       aRes    = (aRes + (aRes >> 4)) & 0x0f0f0f0f;
       aRes    = aRes + (aRes >> 8);
       aRes    = aRes + (aRes >> 16);
       theMask = (theMask & MASK_HIGH) | ((aRes - 1) & MASK_LOW);
       return size_t(aRes & 0x3f);
     }
   }
 
   //! Find the smallest non-zero bit under the given mask.
   //! Outputs the new mask that does not contain the detected bit.
   static IntType findNext(const PackedMapNode* theNode, BlockType& theMask)
   {
     BlockType val    = theNode->Data() & theMask;
     int       nZeros = 0;
     if (val == 0)
     {
       theMask = ~BlockType(0); // void, nothing to do
     }
     else
     {
       BlockType aMask = ~BlockType(0);
       if constexpr (Is64Bit)
       {
         if ((val & 0x00000000ffffffffULL) == 0)
         {
           aMask  = 0xffffffff00000000ULL;
           nZeros = 32;
           val >>= 32;
         }
       }
       if ((val & 0x0000ffff) == 0)
       {
         aMask <<= 16;
         nZeros += 16;
         val >>= 16;
       }
       if ((val & 0x000000ff) == 0)
       {
         aMask <<= 8;
         nZeros += 8;
         val >>= 8;
       }
       if ((val & 0x0000000f) == 0)
       {
         aMask <<= 4;
         nZeros += 4;
         val >>= 4;
       }
       if ((val & 0x00000003) == 0)
       {
         aMask <<= 2;
         nZeros += 2;
         val >>= 2;
       }
       if ((val & 0x00000001) == 0)
       {
         aMask <<= 1;
         nZeros++;
       }
       theMask = (aMask << 1);
     }
     return static_cast<IntType>(nZeros) + theNode->Key();
   }
 
   //! Find the highest non-zero bit under the given mask.
   //! Outputs the new mask that does not contain the detected bit.
   static IntType findPrev(const PackedMapNode* theNode, BlockType& theMask)
   {
     BlockType val    = theNode->Data() & theMask;
     int       nZeros = 0;
     if (val == 0)
     {
       theMask = ~BlockType(0); // void, nothing to do
     }
     else
     {
       BlockType aMask = ~BlockType(0);
       if constexpr (Is64Bit)
       {
         if ((val & 0xffffffff00000000ULL) == 0)
         {
           aMask  = 0x00000000ffffffffULL;
           nZeros = 32;
           val <<= 32;
         }
       }
       if ((val & BlockType(0xffff0000) << (Is64Bit ? 32 : 0)) == 0)
       {
         aMask >>= 16;
         nZeros += 16;
         val <<= 16;
       }
       if ((val & BlockType(0xff000000) << (Is64Bit ? 32 : 0)) == 0)
       {
         aMask >>= 8;
         nZeros += 8;
         val <<= 8;
       }
       if ((val & BlockType(0xf0000000) << (Is64Bit ? 32 : 0)) == 0)
       {
         aMask >>= 4;
         nZeros += 4;
         val <<= 4;
       }
       if ((val & BlockType(0xc0000000) << (Is64Bit ? 32 : 0)) == 0)
       {
         aMask >>= 2;
         nZeros += 2;
         val <<= 2;
       }
       if ((val & BlockType(0x80000000) << (Is64Bit ? 32 : 0)) == 0)
       {
         aMask >>= 1;
         nZeros++;
       }
       theMask = (aMask >> 1);
     }
     return static_cast<IntType>((BitsPerBlock - 1) - nZeros) + theNode->Key();
   }
 
 private:
   PackedMapNode** myData1;            //!< data array
   size_t          myNbBuckets;        //!< number of buckets (size of data array)
   size_t          myNbPackedMapNodes; //!< amount of packed map nodes
   size_t          myExtent;           //!< extent of this map (number of unpacked integer keys)
 };
 
 // Include algorithm header after class definition to avoid circular dependency
 #include <NCollection_PackedMapAlgo.hxx>
 
 // Implementation of deprecated methods
 template <typename IntType>
 void NCollection_PackedMap<IntType>::Union(const NCollection_PackedMap& theLeft,
                                            const NCollection_PackedMap& theRight)
 {
   NCollection_PackedMapAlgo::Union(*this, theLeft, theRight);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::Unite(const NCollection_PackedMap& theOther)
 {
   return NCollection_PackedMapAlgo::Unite(*this, theOther);
 }
 
 template <typename IntType>
 void NCollection_PackedMap<IntType>::Intersection(const NCollection_PackedMap& theLeft,
                                                   const NCollection_PackedMap& theRight)
 {
   NCollection_PackedMapAlgo::Intersection(*this, theLeft, theRight);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::Intersect(const NCollection_PackedMap& theOther)
 {
   return NCollection_PackedMapAlgo::Intersect(*this, theOther);
 }
 
 template <typename IntType>
 void NCollection_PackedMap<IntType>::Subtraction(const NCollection_PackedMap& theLeft,
                                                  const NCollection_PackedMap& theRight)
 {
   NCollection_PackedMapAlgo::Subtraction(*this, theLeft, theRight);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::Subtract(const NCollection_PackedMap& theOther)
 {
   return NCollection_PackedMapAlgo::Subtract(*this, theOther);
 }
 
 template <typename IntType>
 void NCollection_PackedMap<IntType>::Difference(const NCollection_PackedMap& theLeft,
                                                 const NCollection_PackedMap& theRight)
 {
   NCollection_PackedMapAlgo::Difference(*this, theLeft, theRight);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::Differ(const NCollection_PackedMap& theOther)
 {
   return NCollection_PackedMapAlgo::Differ(*this, theOther);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::IsEqual(const NCollection_PackedMap& theOther) const
 {
   return NCollection_PackedMapAlgo::IsEqual(*this, theOther);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::IsSubset(const NCollection_PackedMap& theOther) const
 {
   return NCollection_PackedMapAlgo::IsSubset(*this, theOther);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::HasIntersection(const NCollection_PackedMap& theOther) const
 {
   return NCollection_PackedMapAlgo::HasIntersection(*this, theOther);
 }
 
 template <typename IntType>
 bool NCollection_PackedMap<IntType>::Contains(const NCollection_PackedMap& theOther) const
 {
   return NCollection_PackedMapAlgo::Contains(*this, theOther);
 }
 
 #endif // NCollection_PackedMap_HeaderFile

This page was automatically generated by the 2.3.7 LXR engine. The LXR team