95 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_CPP_BITSET_H10#define LLVM_LIBC_SRC___SUPPORT_CPP_BITSET_H11 12#include "src/__support/macros/attributes.h"13#include "src/__support/macros/config.h"14#include <stddef.h> // For size_t.15 16namespace LIBC_NAMESPACE_DECL {17namespace cpp {18 19template <size_t NumberOfBits> struct bitset {20 static_assert(NumberOfBits != 0,21 "Cannot create a LIBC_NAMESPACE::cpp::bitset of size 0.");22 23 LIBC_INLINE constexpr void set(size_t Index) {24 Data[Index / BITS_PER_UNIT] |= mask(Index);25 }26 27 LIBC_INLINE constexpr void reset() {28 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i)29 Data[i] = 0;30 }31 32 LIBC_INLINE constexpr bool test(size_t Index) const {33 return Data[Index / BITS_PER_UNIT] & mask(Index);34 }35 36 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) to42 // true. It assumes that Start <= End.43 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 left49 // shifting by End - Start + 1) is because when a number is shifted left50 // by 64 then it wraps around to doing nothing, but shifting by 63 and the51 // 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 bool71 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 79private: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 85 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 cpp92} // namespace LIBC_NAMESPACE_DECL93 94#endif // LLVM_LIBC_SRC___SUPPORT_CPP_BITSET_H95