libc/src/__support/CPP/bitset.h

   1 //===-- A self contained equivalent of 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 #ifndef LLVM_LIBC_SRC_SUPPORT_CPP_BITSET_H
  10 #define LLVM_LIBC_SRC_SUPPORT_CPP_BITSET_H
  11
  12 #include <stddef.h> // For size_t.
  13
  14 namespace __llvm_libc::cpp {
  15
  16 template <size_t NumberOfBits> struct bitset {
  17   static_assert(NumberOfBits != 0,
  18                 "Cannot create a __llvm_libc::cpp::bitset of size 0.");
  19
  20   constexpr void set(size_t Index) {
  21     Data[Index / BITS_PER_UNIT] |= mask(Index);
  22   }
  23
  24   constexpr void reset() {
  25     for (size_t i = 0; i < NUMBER_OF_UNITS; ++i)
  26       Data[i] = 0;
  27   }
  28
  29   constexpr bool test(size_t Index) const {
  30     return Data[Index / BITS_PER_UNIT] & mask(Index);
  31   }
  32
  33   constexpr void flip() {
  34     for (size_t i = 0; i < NUMBER_OF_UNITS; ++i)
  35       Data[i] = ~Data[i];
  36   }
  37
  38   // This function sets all bits in the range from Start to End (inclusive) to
  39   // true. It assumes that Start <= End.
  40   constexpr void set_range(size_t Start, size_t End) {
  41     size_t start_index = Start / BITS_PER_UNIT;
  42     size_t end_index = End / BITS_PER_UNIT;
  43
  44     if (start_index == end_index) {
  45       // The reason the left shift is split into two parts (instead of just left
  46       // shifting by End - Start + 1) is because when a number is shifted left
  47       // by 64 then it wraps around to doing nothing, but shifting by 63 and the
  48       // shifting by 1 correctly shifts away all of the bits.
  49       size_t bit_mask = (((size_t(1) << (End - Start)) << 1) - 1)
  50                         << (Start - (start_index * BITS_PER_UNIT));
  51       Data[start_index] |= bit_mask;
  52     } else {
  53       size_t low_bit_mask =
  54           ~((size_t(1) << (Start - (start_index * BITS_PER_UNIT))) - 1);
  55       Data[start_index] |= low_bit_mask;
  56
  57       for (size_t i = start_index + 1; i < end_index; ++i)
  58         Data[i] = ~size_t(0);
  59
  60       // Same as above, by splitting the shift the behavior is more consistent.
  61       size_t high_bit_mask =
  62           ((size_t(1) << (End - (end_index * BITS_PER_UNIT))) << 1) - 1;
  63       Data[end_index] |= high_bit_mask;
  64     }
  65   }
  66
  67   constexpr bool operator==(const bitset<NumberOfBits> &other) {
  68     for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) {
  69       if (Data[i] != other.Data[i])
  70         return false;
  71     }
  72     return true;
  73   }
  74
  75 private:
  76   static constexpr size_t BITS_PER_BYTE = 8;
  77   static constexpr size_t BITS_PER_UNIT = BITS_PER_BYTE * sizeof(size_t);
  78   static constexpr size_t NUMBER_OF_UNITS =
  79       (NumberOfBits + BITS_PER_UNIT - 1) / BITS_PER_UNIT;
  80
  81   static constexpr size_t mask(size_t Index) {
  82     return size_t{1} << (Index % BITS_PER_UNIT);
  83   }
  84   size_t Data[NUMBER_OF_UNITS] = {0};
  85 };
  86
  87 } // namespace __llvm_libc::cpp
  88
  89 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_BITSET_H