1 | //=== llvm/ADT/Bitset.h - constexpr 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 | // Defines a std::bitset like container that can be used in constexprs. |
10 | // That constructor and many of the methods are constexpr. std::bitset doesn't |
11 | // get constexpr methods until C++23. This class also provides a constexpr |
12 | // constructor that accepts an initializer_list of bits to set. |
13 | // |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #ifndef LLVM_ADT_BITSET_H |
17 | #define LLVM_ADT_BITSET_H |
18 | |
19 | #include <llvm/ADT/STLExtras.h> |
20 | #include <array> |
21 | #include <climits> |
22 | #include <cstdint> |
23 | |
24 | namespace llvm { |
25 | |
26 | /// This is a constexpr reimplementation of a subset of std::bitset. It would be |
27 | /// nice to use std::bitset directly, but it doesn't support constant |
28 | /// initialization. |
29 | template <unsigned NumBits> |
30 | class Bitset { |
31 | typedef uintptr_t BitWord; |
32 | |
33 | enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; |
34 | |
35 | static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32, |
36 | "Unsupported word size" ); |
37 | |
38 | static constexpr unsigned NumWords = (NumBits + BITWORD_SIZE-1) / BITWORD_SIZE; |
39 | std::array<BitWord, NumWords> Bits{}; |
40 | |
41 | protected: |
42 | constexpr Bitset(const std::array<BitWord, NumWords> &B) |
43 | : Bits{B} {} |
44 | |
45 | public: |
46 | constexpr Bitset() = default; |
47 | constexpr Bitset(std::initializer_list<unsigned> Init) { |
48 | for (auto I : Init) |
49 | set(I); |
50 | } |
51 | |
52 | Bitset &set() { |
53 | std::fill(std::begin(Bits), std::end(Bits), -BitWord(0)); |
54 | return *this; |
55 | } |
56 | |
57 | constexpr Bitset &set(unsigned I) { |
58 | Bits[I / BITWORD_SIZE] |= BitWord(1) << (I % BITWORD_SIZE); |
59 | return *this; |
60 | } |
61 | |
62 | constexpr Bitset &reset(unsigned I) { |
63 | Bits[I / BITWORD_SIZE] &= ~(BitWord(1) << (I % BITWORD_SIZE)); |
64 | return *this; |
65 | } |
66 | |
67 | constexpr Bitset &flip(unsigned I) { |
68 | Bits[I / BITWORD_SIZE] ^= BitWord(1) << (I % BITWORD_SIZE); |
69 | return *this; |
70 | } |
71 | |
72 | constexpr bool operator[](unsigned I) const { |
73 | BitWord Mask = BitWord(1) << (I % BITWORD_SIZE); |
74 | return (Bits[I / BITWORD_SIZE] & Mask) != 0; |
75 | } |
76 | |
77 | constexpr bool test(unsigned I) const { return (*this)[I]; } |
78 | |
79 | constexpr size_t size() const { return NumBits; } |
80 | |
81 | bool any() const { |
82 | return llvm::any_of(Bits, [](BitWord I) { return I != 0; }); |
83 | } |
84 | bool none() const { return !any(); } |
85 | size_t count() const { |
86 | size_t Count = 0; |
87 | for (auto B : Bits) |
88 | Count += llvm::popcount(B); |
89 | return Count; |
90 | } |
91 | |
92 | constexpr Bitset &operator^=(const Bitset &RHS) { |
93 | for (unsigned I = 0, E = Bits.size(); I != E; ++I) { |
94 | Bits[I] ^= RHS.Bits[I]; |
95 | } |
96 | return *this; |
97 | } |
98 | constexpr Bitset operator^(const Bitset &RHS) const { |
99 | Bitset Result = *this; |
100 | Result ^= RHS; |
101 | return Result; |
102 | } |
103 | |
104 | constexpr Bitset &operator&=(const Bitset &RHS) { |
105 | for (unsigned I = 0, E = Bits.size(); I != E; ++I) |
106 | Bits[I] &= RHS.Bits[I]; |
107 | return *this; |
108 | } |
109 | constexpr Bitset operator&(const Bitset &RHS) const { |
110 | Bitset Result = *this; |
111 | Result &= RHS; |
112 | return Result; |
113 | } |
114 | |
115 | constexpr Bitset &operator|=(const Bitset &RHS) { |
116 | for (unsigned I = 0, E = Bits.size(); I != E; ++I) { |
117 | Bits[I] |= RHS.Bits[I]; |
118 | } |
119 | return *this; |
120 | } |
121 | constexpr Bitset operator|(const Bitset &RHS) const { |
122 | Bitset Result = *this; |
123 | Result |= RHS; |
124 | return Result; |
125 | } |
126 | |
127 | constexpr Bitset operator~() const { |
128 | Bitset Result = *this; |
129 | for (auto &B : Result.Bits) |
130 | B = ~B; |
131 | return Result; |
132 | } |
133 | |
134 | bool operator==(const Bitset &RHS) const { |
135 | return std::equal(std::begin(Bits), std::end(Bits), std::begin(RHS.Bits)); |
136 | } |
137 | |
138 | bool operator!=(const Bitset &RHS) const { return !(*this == RHS); } |
139 | |
140 | bool operator < (const Bitset &Other) const { |
141 | for (unsigned I = 0, E = size(); I != E; ++I) { |
142 | bool LHS = test(I), RHS = Other.test(I); |
143 | if (LHS != RHS) |
144 | return LHS < RHS; |
145 | } |
146 | return false; |
147 | } |
148 | }; |
149 | |
150 | } // end namespace llvm |
151 | |
152 | #endif |
153 | |