1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef mozilla_BitSet_h 8 #define mozilla_BitSet_h 9 10 #include "mozilla/Array.h" 11 #include "mozilla/ArrayUtils.h" 12 #include "mozilla/MathAlgorithms.h" 13 #include "mozilla/PodOperations.h" 14 #include "mozilla/Span.h" 15 16 namespace mozilla { 17 18 /** 19 * An object like std::bitset but which provides access to the underlying 20 * storage. 21 * 22 * The limited API is due to expedience only; feel free to flesh out any 23 * std::bitset-like members. 24 */ 25 template <size_t N, typename Word = size_t> 26 class BitSet { 27 static_assert(std::is_unsigned_v<Word>, 28 "The Word type must be an unsigned integral type"); 29 30 private: 31 static constexpr size_t kBitsPerWord = 8 * sizeof(Word); 32 static constexpr size_t kNumWords = (N + kBitsPerWord - 1) / kBitsPerWord; 33 static constexpr size_t kPaddingBits = (kNumWords * kBitsPerWord) - N; 34 static constexpr Word kPaddingMask = Word(-1) >> kPaddingBits; 35 36 // The zeroth bit in the bitset is the least significant bit of mStorage[0]. 37 Array<Word, kNumWords> mStorage; 38 ResetPaddingBits()39 constexpr void ResetPaddingBits() { 40 if constexpr (kPaddingBits != 0) { 41 mStorage[kNumWords - 1] &= kPaddingMask; 42 } 43 } 44 45 public: 46 class Reference { 47 public: Reference(BitSet<N,Word> & aBitSet,size_t aPos)48 Reference(BitSet<N, Word>& aBitSet, size_t aPos) 49 : mBitSet(aBitSet), mPos(aPos) {} 50 51 Reference& operator=(bool aValue) { 52 auto bit = Word(1) << (mPos % kBitsPerWord); 53 auto& word = mBitSet.mStorage[mPos / kBitsPerWord]; 54 word = (word & ~bit) | (aValue ? bit : 0); 55 return *this; 56 } 57 58 MOZ_IMPLICIT operator bool() const { return mBitSet.Test(mPos); } 59 60 private: 61 BitSet<N, Word>& mBitSet; 62 size_t mPos; 63 }; 64 BitSet()65 constexpr BitSet() : mStorage() {} 66 BitSet(const BitSet & aOther)67 BitSet(const BitSet& aOther) { *this = aOther; } 68 69 BitSet& operator=(const BitSet& aOther) { 70 PodCopy(mStorage.begin(), aOther.mStorage.begin(), kNumWords); 71 return *this; 72 } 73 BitSet(Span<Word,kNumWords> aStorage)74 explicit BitSet(Span<Word, kNumWords> aStorage) { 75 PodCopy(mStorage.begin(), aStorage.Elements(), kNumWords); 76 } 77 Size()78 constexpr size_t Size() const { return N; } 79 Test(size_t aPos)80 constexpr bool Test(size_t aPos) const { 81 MOZ_ASSERT(aPos < N); 82 return mStorage[aPos / kBitsPerWord] & (Word(1) << (aPos % kBitsPerWord)); 83 } 84 IsEmpty()85 constexpr bool IsEmpty() const { 86 for (const Word& word : mStorage) { 87 if (word) { 88 return false; 89 } 90 } 91 return true; 92 } 93 94 explicit constexpr operator bool() { return !IsEmpty(); } 95 96 constexpr bool operator[](size_t aPos) const { return Test(aPos); } 97 98 Reference operator[](size_t aPos) { 99 MOZ_ASSERT(aPos < N); 100 return {*this, aPos}; 101 } 102 103 BitSet operator|(const BitSet<N, Word>& aOther) { 104 BitSet result = *this; 105 result |= aOther; 106 return result; 107 } 108 109 BitSet& operator|=(const BitSet<N, Word>& aOther) { 110 for (size_t i = 0; i < ArrayLength(mStorage); i++) { 111 mStorage[i] |= aOther.mStorage[i]; 112 } 113 return *this; 114 } 115 116 BitSet operator~() const { 117 BitSet result = *this; 118 result.Flip(); 119 return result; 120 } 121 122 BitSet& operator&=(const BitSet<N, Word>& aOther) { 123 for (size_t i = 0; i < ArrayLength(mStorage); i++) { 124 mStorage[i] &= aOther.mStorage[i]; 125 } 126 return *this; 127 } 128 129 BitSet operator&(const BitSet<N, Word>& aOther) const { 130 BitSet result = *this; 131 result &= aOther; 132 return result; 133 } 134 135 bool operator==(const BitSet<N, Word>& aOther) const { 136 return mStorage == aOther.mStorage; 137 } 138 Count()139 size_t Count() const { 140 size_t count = 0; 141 142 for (const Word& word : mStorage) { 143 if constexpr (kBitsPerWord > 32) { 144 count += CountPopulation64(word); 145 } else { 146 count += CountPopulation32(word); 147 } 148 } 149 150 return count; 151 } 152 153 // Set all bits to false. ResetAll()154 void ResetAll() { PodArrayZero(mStorage); } 155 156 // Set all bits to true. SetAll()157 void SetAll() { 158 memset(mStorage.begin(), 0xff, kNumWords * sizeof(Word)); 159 ResetPaddingBits(); 160 } 161 Flip()162 void Flip() { 163 for (Word& word : mStorage) { 164 word = ~word; 165 } 166 167 ResetPaddingBits(); 168 } 169 Storage()170 Span<Word> Storage() { return mStorage; } 171 Storage()172 Span<const Word> Storage() const { return mStorage; } 173 }; 174 175 } // namespace mozilla 176 177 #endif // mozilla_BitSet_h 178