| 172 | |
| 173 | // A simple set of 64 bits that can be individually marked or cleared. |
| 174 | struct BitSet64 { |
| 175 | uint64_t value; |
| 176 | |
| 177 | inline BitSet64() : value(0ULL) { } |
| 178 | explicit inline BitSet64(uint64_t value) : value(value) { } |
| 179 | |
| 180 | // Gets the value associated with a particular bit index. |
| 181 | static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; } |
| 182 | |
| 183 | // Clears the bit set. |
| 184 | inline void clear() { clear(value); } |
| 185 | |
| 186 | static inline void clear(uint64_t& value) { value = 0ULL; } |
| 187 | |
| 188 | // Returns the number of marked bits in the set. |
| 189 | inline uint32_t count() const { return count(value); } |
| 190 | |
| 191 | static inline uint32_t count(uint64_t value) { return __builtin_popcountll(value); } |
| 192 | |
| 193 | // Returns true if the bit set does not contain any marked bits. |
| 194 | inline bool isEmpty() const { return isEmpty(value); } |
| 195 | |
| 196 | static inline bool isEmpty(uint64_t value) { return ! value; } |
| 197 | |
| 198 | // Returns true if the bit set does not contain any unmarked bits. |
| 199 | inline bool isFull() const { return isFull(value); } |
| 200 | |
| 201 | static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; } |
| 202 | |
| 203 | // Returns true if the specified bit is marked. |
| 204 | inline bool hasBit(uint32_t n) const { return hasBit(value, n); } |
| 205 | |
| 206 | static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); } |
| 207 | |
| 208 | // Marks the specified bit. |
| 209 | inline void markBit(uint32_t n) { markBit(value, n); } |
| 210 | |
| 211 | static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); } |
| 212 | |
| 213 | // Clears the specified bit. |
| 214 | inline void clearBit(uint32_t n) { clearBit(value, n); } |
| 215 | |
| 216 | static inline void clearBit(uint64_t& value, uint32_t n) { value &= ~ valueForBit(n); } |
| 217 | |
| 218 | // Finds the first marked bit in the set. |
| 219 | // Result is undefined if all bits are unmarked. |
| 220 | inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } |
| 221 | |
| 222 | static inline uint32_t firstMarkedBit(uint64_t value) { return __builtin_clzll(value); } |
| 223 | |
| 224 | // Finds the first unmarked bit in the set. |
| 225 | // Result is undefined if all bits are marked. |
| 226 | inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } |
| 227 | |
| 228 | static inline uint32_t firstUnmarkedBit(uint64_t value) { return __builtin_clzll(~ value); } |
| 229 | |
| 230 | // Finds the last marked bit in the set. |
| 231 | // Result is undefined if all bits are unmarked. |