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