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 <stddef.h> // For size_t. 14 15 namespace LIBC_NAMESPACE::cpp { 16 17 template <size_t NumberOfBits> struct bitset { 18 static_assert(NumberOfBits != 0, 19 "Cannot create a LIBC_NAMESPACE::cpp::bitset of size 0."); 20 setbitset21 LIBC_INLINE constexpr void set(size_t Index) { 22 Data[Index / BITS_PER_UNIT] |= mask(Index); 23 } 24 resetbitset25 LIBC_INLINE constexpr void reset() { 26 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) 27 Data[i] = 0; 28 } 29 testbitset30 LIBC_INLINE constexpr bool test(size_t Index) const { 31 return Data[Index / BITS_PER_UNIT] & mask(Index); 32 } 33 flipbitset34 LIBC_INLINE constexpr void flip() { 35 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) 36 Data[i] = ~Data[i]; 37 } 38 39 // This function sets all bits in the range from Start to End (inclusive) to 40 // true. It assumes that Start <= End. set_rangebitset41 LIBC_INLINE constexpr void set_range(size_t Start, size_t End) { 42 size_t start_index = Start / BITS_PER_UNIT; 43 size_t end_index = End / BITS_PER_UNIT; 44 45 if (start_index == end_index) { 46 // The reason the left shift is split into two parts (instead of just left 47 // shifting by End - Start + 1) is because when a number is shifted left 48 // by 64 then it wraps around to doing nothing, but shifting by 63 and the 49 // shifting by 1 correctly shifts away all of the bits. 50 size_t bit_mask = (((size_t(1) << (End - Start)) << 1) - 1) 51 << (Start - (start_index * BITS_PER_UNIT)); 52 Data[start_index] |= bit_mask; 53 } else { 54 size_t low_bit_mask = 55 ~((size_t(1) << (Start - (start_index * BITS_PER_UNIT))) - 1); 56 Data[start_index] |= low_bit_mask; 57 58 for (size_t i = start_index + 1; i < end_index; ++i) 59 Data[i] = ~size_t(0); 60 61 // Same as above, by splitting the shift the behavior is more consistent. 62 size_t high_bit_mask = 63 ((size_t(1) << (End - (end_index * BITS_PER_UNIT))) << 1) - 1; 64 Data[end_index] |= high_bit_mask; 65 } 66 } 67 68 LIBC_INLINE constexpr bool 69 operator==(const bitset<NumberOfBits> &other) const { 70 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) { 71 if (Data[i] != other.Data[i]) 72 return false; 73 } 74 return true; 75 } 76 77 private: 78 static constexpr size_t BITS_PER_BYTE = 8; 79 static constexpr size_t BITS_PER_UNIT = BITS_PER_BYTE * sizeof(size_t); 80 static constexpr size_t NUMBER_OF_UNITS = 81 (NumberOfBits + BITS_PER_UNIT - 1) / BITS_PER_UNIT; 82 maskbitset83 LIBC_INLINE static constexpr size_t mask(size_t Index) { 84 return size_t{1} << (Index % BITS_PER_UNIT); 85 } 86 size_t Data[NUMBER_OF_UNITS] = {0}; 87 }; 88 89 } // namespace LIBC_NAMESPACE::cpp 90 91 #endif // LLVM_LIBC_SRC___SUPPORT_CPP_BITSET_H 92