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
15namespace LIBC_NAMESPACE::cpp {
16
17template <size_t NumberOfBits> struct bitset {
18 static_assert(NumberOfBits != 0,
19 "Cannot create a LIBC_NAMESPACE::cpp::bitset of size 0.");
20
21 LIBC_INLINE constexpr void set(size_t Index) {
22 Data[Index / BITS_PER_UNIT] |= mask(Index);
23 }
24
25 LIBC_INLINE constexpr void reset() {
26 for (size_t i = 0; i < NUMBER_OF_UNITS; ++i)
27 Data[i] = 0;
28 }
29
30 LIBC_INLINE constexpr bool test(size_t Index) const {
31 return Data[Index / BITS_PER_UNIT] & mask(Index);
32 }
33
34 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.
41 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
77private:
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
83 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

source code of libc/src/__support/CPP/bitset.h