1 // Copyright 2021 gRPC authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef GRPC_SRC_CORE_UTIL_BITSET_H 16 #define GRPC_SRC_CORE_UTIL_BITSET_H 17 18 #include <grpc/support/port_platform.h> 19 #include <stddef.h> 20 #include <stdint.h> 21 22 #include <type_traits> 23 24 #include "src/core/util/useful.h" 25 26 namespace grpc_core { 27 28 // Given a bit count as an integer, vend as member type `Type` a type with 29 // exactly that number of bits. Undefined if that bit count is not available. 30 template <size_t kBits> 31 struct UintSelector; 32 33 template <> 34 struct UintSelector<8> { 35 typedef uint8_t Type; 36 }; 37 template <> 38 struct UintSelector<16> { 39 typedef uint16_t Type; 40 }; 41 template <> 42 struct UintSelector<32> { 43 typedef uint32_t Type; 44 }; 45 template <> 46 struct UintSelector<64> { 47 typedef uint64_t Type; 48 }; 49 50 // An unsigned integer of some number of bits. 51 template <size_t kBits> 52 using Uint = typename UintSelector<kBits>::Type; 53 54 // Given the total number of bits that need to be stored, choose the size of 55 // 'unit' for a BitSet... We'll use an array of units to store the total set. 56 // For small bit counts we are selective in the type to try and balance byte 57 // size and performance 58 // - the details will likely be tweaked into the future. 59 // Once we get over 96 bits, we just use uint64_t for everything. 60 constexpr size_t ChooseUnitBitsForBitSet(size_t total_bits) { 61 return total_bits <= 8 ? 8 62 : total_bits <= 16 ? 16 63 : total_bits <= 24 ? 8 64 : total_bits <= 32 ? 32 65 : total_bits <= 48 ? 16 66 : total_bits <= 64 ? 64 67 : total_bits <= 96 ? 32 68 : 64; 69 } 70 71 // A BitSet that's configurable. 72 // Contains storage for kTotalBits, stored as an array of integers of size 73 // kUnitBits. e.g. to store 72 bits in 8 bit chunks, we'd say BitSet<72, 8>. 74 // Since most users shouldn't care about the size of unit used, we default 75 // kUnitBits to whatever is selected by ChooseUnitBitsForBitSet 76 template <size_t kTotalBits, 77 size_t kUnitBits = ChooseUnitBitsForBitSet(kTotalBits)> 78 class BitSet { 79 static constexpr size_t kUnits = (kTotalBits + kUnitBits - 1) / kUnitBits; 80 81 public: 82 // Initialize to all bits false 83 constexpr BitSet() : units_{} {} 84 85 // Set bit i to true 86 constexpr void set(int i) { units_[unit_for(i)] |= mask_for(i); } 87 88 // Set bit i to is_set 89 constexpr void set(int i, bool is_set) { 90 if (is_set) { 91 set(i); 92 } else { 93 clear(i); 94 } 95 } 96 97 // Set bit i to false 98 constexpr void clear(int i) { units_[unit_for(i)] &= ~mask_for(i); } 99 100 // Return true if bit i is set 101 constexpr bool is_set(int i) const { 102 return (units_[unit_for(i)] & mask_for(i)) != 0; 103 } 104 105 // Return true if all bits are set 106 bool all() const { 107 if (kTotalBits % kUnitBits == 0) { 108 // kTotalBits is a multiple of kUnitBits ==> we can just check for all 109 // ones in each unit. 110 for (size_t i = 0; i < kUnits; i++) { 111 if (units_[i] != all_ones()) return false; 112 } 113 return true; 114 } else { 115 // kTotalBits is not a multiple of kUnitBits ==> we need special handling 116 // for checking partial filling of the last unit (since not all of its 117 // bits are used!) 118 for (size_t i = 0; i < kUnits - 1; i++) { 119 if (units_[i] != all_ones()) return false; 120 } 121 return units_[kUnits - 1] == n_ones(kTotalBits % kUnitBits); 122 } 123 } 124 125 // Return true if *no* bits are set. 126 bool none() const { 127 for (size_t i = 0; i < kUnits; i++) { 128 if (units_[i] != 0) return false; 129 } 130 return true; 131 } 132 133 // Returns true if any bites are set. 134 bool any() const { return !none(); } 135 136 // Return a count of how many bits are set. 137 uint32_t count() const { 138 uint32_t count = 0; 139 for (size_t i = 0; i < kUnits; i++) { 140 count += absl::popcount(units_[i]); 141 } 142 return count; 143 } 144 145 bool operator==(const BitSet& other) const { 146 for (size_t i = 0; i < kUnits; i++) { 147 if (units_[i] != other.units_[i]) return false; 148 } 149 return true; 150 } 151 152 template <typename Int> 153 typename std::enable_if<std::is_unsigned<Int>::value && 154 (sizeof(Int) * 8 >= kTotalBits), 155 Int>::type 156 ToInt() const { 157 Int result = 0; 158 for (size_t i = 0; i < kTotalBits; i++) { 159 if (is_set(i)) result |= (Int(1) << i); 160 } 161 return result; 162 } 163 164 template <typename Int> 165 static BitSet<kTotalBits, kUnitBits> FromInt(Int value) { 166 BitSet<kTotalBits, kUnitBits> result; 167 for (size_t i = 0; i < kTotalBits; i++) { 168 result.set(i, (value & (Int(1) << i)) != 0); 169 } 170 return result; 171 } 172 173 BitSet& Set(int i, bool value) { 174 set(i, value); 175 return *this; 176 } 177 178 BitSet& SetAll(bool value) { 179 for (size_t i = 0; i < kTotalBits; i++) { 180 set(i, value); 181 } 182 return *this; 183 } 184 185 private: 186 // Given a bit index, return which unit it's stored in. 187 static constexpr size_t unit_for(size_t bit) { return bit / kUnitBits; } 188 189 // Given a bit index, return a mask to access that bit within it's unit. 190 static constexpr Uint<kUnitBits> mask_for(size_t bit) { 191 return Uint<kUnitBits>{1} << (bit % kUnitBits); 192 } 193 194 // Return a value that is all ones 195 static constexpr Uint<kUnitBits> all_ones() { 196 return Uint<kUnitBits>(~Uint<kUnitBits>(0)); 197 } 198 199 // Return a value with n bottom bits ones 200 static constexpr Uint<kUnitBits> n_ones(size_t n) { 201 return n == kUnitBits ? all_ones() : (Uint<kUnitBits>(1) << n) - 1; 202 } 203 204 // The set of units - kUnitBits sized integers that store kUnitBits bits! 205 Uint<kUnitBits> units_[kUnits]; 206 }; 207 208 // Zero-size specialization of BitSet. 209 // Useful for generic programming. 210 // Make a compile time error out of get/set type accesses, and hard-codes 211 // queries that do make sense. 212 template <> 213 class BitSet<0> { 214 public: 215 constexpr BitSet() {} 216 217 bool all() const { return true; } 218 bool none() const { return true; } 219 uint32_t count() const { return 0; } 220 }; 221 222 } // namespace grpc_core 223 224 #endif // GRPC_SRC_CORE_UTIL_BITSET_H 225