llvm/ADT/Bitset.h

0001 //=== llvm/ADT/Bitset.h - constexpr std::bitset -----------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Defines a std::bitset like container that can be used in constexprs.
0010 // That constructor and many of the methods are constexpr. std::bitset doesn't
0011 // get constexpr methods until C++23. This class also provides a constexpr
0012 // constructor that accepts an initializer_list of bits to set.
0013 //
0014 //===----------------------------------------------------------------------===//
0015
0016 #ifndef LLVM_ADT_BITSET_H
0017 #define LLVM_ADT_BITSET_H
0018
0019 #include <llvm/ADT/STLExtras.h>
0020 #include <array>
0021 #include <climits>
0022 #include <cstdint>
0023
0024 namespace llvm {
0025
0026 /// This is a constexpr reimplementation of a subset of std::bitset. It would be
0027 /// nice to use std::bitset directly, but it doesn't support constant
0028 /// initialization.
0029 template <unsigned NumBits>
0030 class Bitset {
0031   typedef uintptr_t BitWord;
0032
0033   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
0034
0035   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
0036                 "Unsupported word size");
0037
0038   static constexpr unsigned NumWords = (NumBits + BITWORD_SIZE-1) / BITWORD_SIZE;
0039   std::array<BitWord, NumWords> Bits{};
0040
0041 protected:
0042   constexpr Bitset(const std::array<BitWord, NumWords> &B)
0043       : Bits{B} {}
0044
0045 public:
0046   constexpr Bitset() = default;
0047   constexpr Bitset(std::initializer_list<unsigned> Init) {
0048     for (auto I : Init)
0049       set(I);
0050   }
0051
0052   Bitset &set() {
0053     std::fill(std::begin(Bits), std::end(Bits), -BitWord(0));
0054     return *this;
0055   }
0056
0057   constexpr Bitset &set(unsigned I) {
0058     Bits[I / BITWORD_SIZE] |= BitWord(1) << (I % BITWORD_SIZE);
0059     return *this;
0060   }
0061
0062   constexpr Bitset &reset(unsigned I) {
0063     Bits[I / BITWORD_SIZE] &= ~(BitWord(1) << (I % BITWORD_SIZE));
0064     return *this;
0065   }
0066
0067   constexpr Bitset &flip(unsigned I) {
0068     Bits[I / BITWORD_SIZE] ^= BitWord(1) << (I % BITWORD_SIZE);
0069     return *this;
0070   }
0071
0072   constexpr bool operator[](unsigned I) const {
0073     BitWord Mask = BitWord(1) << (I % BITWORD_SIZE);
0074     return (Bits[I / BITWORD_SIZE] & Mask) != 0;
0075   }
0076
0077   constexpr bool test(unsigned I) const { return (*this)[I]; }
0078
0079   constexpr size_t size() const { return NumBits; }
0080
0081   bool any() const {
0082     return llvm::any_of(Bits, [](BitWord I) { return I != 0; });
0083   }
0084   bool none() const { return !any(); }
0085   size_t count() const {
0086     size_t Count = 0;
0087     for (auto B : Bits)
0088       Count += llvm::popcount(B);
0089     return Count;
0090   }
0091
0092   constexpr Bitset &operator^=(const Bitset &RHS) {
0093     for (unsigned I = 0, E = Bits.size(); I != E; ++I) {
0094       Bits[I] ^= RHS.Bits[I];
0095     }
0096     return *this;
0097   }
0098   constexpr Bitset operator^(const Bitset &RHS) const {
0099     Bitset Result = *this;
0100     Result ^= RHS;
0101     return Result;
0102   }
0103
0104   constexpr Bitset &operator&=(const Bitset &RHS) {
0105     for (unsigned I = 0, E = Bits.size(); I != E; ++I)
0106       Bits[I] &= RHS.Bits[I];
0107     return *this;
0108   }
0109   constexpr Bitset operator&(const Bitset &RHS) const {
0110     Bitset Result = *this;
0111     Result &= RHS;
0112     return Result;
0113   }
0114
0115   constexpr Bitset &operator|=(const Bitset &RHS) {
0116     for (unsigned I = 0, E = Bits.size(); I != E; ++I) {
0117       Bits[I] |= RHS.Bits[I];
0118     }
0119     return *this;
0120   }
0121   constexpr Bitset operator|(const Bitset &RHS) const {
0122     Bitset Result = *this;
0123     Result |= RHS;
0124     return Result;
0125   }
0126
0127   constexpr Bitset operator~() const {
0128     Bitset Result = *this;
0129     for (auto &B : Result.Bits)
0130       B = ~B;
0131     return Result;
0132   }
0133
0134   bool operator==(const Bitset &RHS) const {
0135     return std::equal(std::begin(Bits), std::end(Bits), std::begin(RHS.Bits));
0136   }
0137
0138   bool operator!=(const Bitset &RHS) const { return !(*this == RHS); }
0139
0140   bool operator < (const Bitset &Other) const {
0141     for (unsigned I = 0, E = size(); I != E; ++I) {
0142       bool LHS = test(I), RHS = Other.test(I);
0143       if (LHS != RHS)
0144         return LHS < RHS;
0145     }
0146     return false;
0147   }
0148 };
0149
0150 } // end namespace llvm
0151
0152 #endif