1 //===-- A self contained equivalent of std::bitset --------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIBC_SRC___SUPPORT_CPP_BITSET_H 10 #define LLVM_LIBC_SRC___SUPPORT_CPP_BITSET_H 11 12 #include "src/__support/macros/attributes.h" 13 #include "src/__support/macros/config.h" 14 #include <stddef.h> // For size_t. 15 16 namespace LIBC_NAMESPACE_DECL { 17 namespace cpp { 18 19 template <size_t NumberOfBits> struct bitset { 20 static_assert(NumberOfBits != 0, 21 "Cannot create a LIBC_NAMESPACE::cpp::bitset of size 0."); 22 setbitset23 LIBC_INLINE constexpr void set(size_t Index) { 24 Data[Index / BITS_PER_UNIT] |= mask(Index); 25 } 26 resetbitset27 LIBC_INLINE constexpr void reset() { 28 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) 29 Data[i] = 0; 30 } 31 testbitset32 LIBC_INLINE constexpr bool test(size_t Index) const { 33 return Data[Index / BITS_PER_UNIT] & mask(Index); 34 } 35 flipbitset36 LIBC_INLINE constexpr void flip() { 37 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) 38 Data[i] = ~Data[i]; 39 } 40 41 // This function sets all bits in the range from Start to End (inclusive) to 42 // true. It assumes that Start <= End. set_rangebitset43 LIBC_INLINE constexpr void set_range(size_t Start, size_t End) { 44 size_t start_index = Start / BITS_PER_UNIT; 45 size_t end_index = End / BITS_PER_UNIT; 46 47 if (start_index == end_index) { 48 // The reason the left shift is split into two parts (instead of just left 49 // shifting by End - Start + 1) is because when a number is shifted left 50 // by 64 then it wraps around to doing nothing, but shifting by 63 and the 51 // shifting by 1 correctly shifts away all of the bits. 52 size_t bit_mask = (((size_t(1) << (End - Start)) << 1) - 1) 53 << (Start - (start_index * BITS_PER_UNIT)); 54 Data[start_index] |= bit_mask; 55 } else { 56 size_t low_bit_mask = 57 ~((size_t(1) << (Start - (start_index * BITS_PER_UNIT))) - 1); 58 Data[start_index] |= low_bit_mask; 59 60 for (size_t i = start_index + 1; i < end_index; ++i) 61 Data[i] = ~size_t(0); 62 63 // Same as above, by splitting the shift the behavior is more consistent. 64 size_t high_bit_mask = 65 ((size_t(1) << (End - (end_index * BITS_PER_UNIT))) << 1) - 1; 66 Data[end_index] |= high_bit_mask; 67 } 68 } 69 70 LIBC_INLINE constexpr bool 71 operator==(const bitset<NumberOfBits> &other) const { 72 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) { 73 if (Data[i] != other.Data[i]) 74 return false; 75 } 76 return true; 77 } 78 79 private: 80 static constexpr size_t BITS_PER_BYTE = 8; 81 static constexpr size_t BITS_PER_UNIT = BITS_PER_BYTE * sizeof(size_t); 82 static constexpr size_t NUMBER_OF_UNITS = 83 (NumberOfBits + BITS_PER_UNIT - 1) / BITS_PER_UNIT; 84 maskbitset85 LIBC_INLINE static constexpr size_t mask(size_t Index) { 86 return size_t{1} << (Index % BITS_PER_UNIT); 87 } 88 size_t Data[NUMBER_OF_UNITS] = {0}; 89 }; 90 91 } // namespace cpp 92 } // namespace LIBC_NAMESPACE_DECL 93 94 #endif // LLVM_LIBC_SRC___SUPPORT_CPP_BITSET_H 95