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:
Bitset(const std::array<BitWord,NumWords> & B)42   constexpr Bitset(const std::array<BitWord, NumWords> &B)
43       : Bits{B} {}
44 
45 public:
46   constexpr Bitset() = default;
Bitset(std::initializer_list<unsigned> Init)47   constexpr Bitset(std::initializer_list<unsigned> Init) {
48     for (auto I : Init)
49       set(I);
50   }
51 
set()52   Bitset &set() {
53     std::fill(std::begin(Bits), std::end(Bits), -BitWord(0));
54     return *this;
55   }
56 
set(unsigned I)57   constexpr Bitset &set(unsigned I) {
58     Bits[I / BITWORD_SIZE] |= BitWord(1) << (I % BITWORD_SIZE);
59     return *this;
60   }
61 
reset(unsigned I)62   constexpr Bitset &reset(unsigned I) {
63     Bits[I / BITWORD_SIZE] &= ~(BitWord(1) << (I % BITWORD_SIZE));
64     return *this;
65   }
66 
flip(unsigned I)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 
test(unsigned I)77   constexpr bool test(unsigned I) const { return (*this)[I]; }
78 
size()79   constexpr size_t size() const { return NumBits; }
80 
any()81   bool any() const {
82     return llvm::any_of(Bits, [](BitWord I) { return I != 0; });
83   }
none()84   bool none() const { return !any(); }
count()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