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