LLVM 20.0.0git
Bitset.h
Go to the documentation of this file.
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
24namespace 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.
29template <unsigned NumBits>
30class 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
41protected:
42 constexpr Bitset(const std::array<BitWord, NumWords> &B)
43 : Bits{B} {}
44
45public:
46 constexpr Bitset() = default;
47 constexpr Bitset(std::initializer_list<unsigned> Init) {
48 for (auto I : Init)
49 set(I);
50 }
51
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
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define I(x, y, z)
Definition: MD5.cpp:58
modulo schedule test
This file contains some templates that are useful if you are working with the STL at all.
Value * RHS
Value * LHS
This is a constexpr reimplementation of a subset of std::bitset.
Definition: Bitset.h:30
constexpr Bitset operator^(const Bitset &RHS) const
Definition: Bitset.h:98
constexpr Bitset & set(unsigned I)
Definition: Bitset.h:57
constexpr Bitset & flip(unsigned I)
Definition: Bitset.h:67
bool operator<(const Bitset &Other) const
Definition: Bitset.h:140
bool operator!=(const Bitset &RHS) const
Definition: Bitset.h:138
constexpr Bitset()=default
constexpr Bitset & operator^=(const Bitset &RHS)
Definition: Bitset.h:92
constexpr Bitset operator&(const Bitset &RHS) const
Definition: Bitset.h:109
constexpr bool operator[](unsigned I) const
Definition: Bitset.h:72
constexpr size_t size() const
Definition: Bitset.h:79
size_t count() const
Definition: Bitset.h:85
Bitset & set()
Definition: Bitset.h:52
bool any() const
Definition: Bitset.h:81
constexpr Bitset & operator|=(const Bitset &RHS)
Definition: Bitset.h:115
bool operator==(const Bitset &RHS) const
Definition: Bitset.h:134
constexpr Bitset(std::initializer_list< unsigned > Init)
Definition: Bitset.h:47
constexpr Bitset & operator&=(const Bitset &RHS)
Definition: Bitset.h:104
constexpr bool test(unsigned I) const
Definition: Bitset.h:77
constexpr Bitset operator|(const Bitset &RHS) const
Definition: Bitset.h:121
constexpr Bitset(const std::array< BitWord, NumWords > &B)
Definition: Bitset.h:42
constexpr Bitset & reset(unsigned I)
Definition: Bitset.h:62
bool none() const
Definition: Bitset.h:84
constexpr Bitset operator~() const
Definition: Bitset.h:127
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
int popcount(T Value) noexcept
Count the number of set bits in a value.
Definition: bit.h:385
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
@ Other
Any other memory.