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