js/src/ds/BitArray.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef ds_BitArray_h
   8 #define ds_BitArray_h
   9
  10 #include "mozilla/MathAlgorithms.h"
  11 #include "mozilla/TemplateLib.h"
  12
  13 #include <limits.h>
  14 #include <string.h>
  15
  16 #include "jstypes.h"
  17
  18 namespace js {
  19
  20 namespace detail {
  21
  22 template <typename WordT>
  23 inline uint_fast8_t CountTrailingZeroes(WordT word);
  24
  25 template <>
  26 inline uint_fast8_t CountTrailingZeroes(uint32_t word) {
  27   return mozilla::CountTrailingZeroes32(word);
  28 }
  29
  30 template <>
  31 inline uint_fast8_t CountTrailingZeroes(uint64_t word) {
  32   return mozilla::CountTrailingZeroes64(word);
  33 }
  34
  35 }  // namespace detail
  36
  37 template <size_t nbits>
  38 class BitArray {
  39  public:
  40   // Use a 32 bit word to make it easier to access a BitArray from JIT code.
  41   using WordT = uint32_t;
  42
  43   static const size_t bitsPerElement = sizeof(WordT) * CHAR_BIT;
  44   static const size_t numSlots =
  45       nbits / bitsPerElement + (nbits % bitsPerElement == 0 ? 0 : 1);
  46
  47  private:
  48   static const size_t paddingBits = (numSlots * bitsPerElement) - nbits;
  49   static_assert(paddingBits < bitsPerElement,
  50                 "More padding bits than expected.");
  51   static const WordT paddingMask = WordT(-1) >> paddingBits;
  52
  53   WordT map[numSlots];
  54
  55  public:
  56   constexpr BitArray() : map() {};
  57
  58   void clear(bool value) {
  59     memset(map, value ? 0xFF : 0, sizeof(map));
  60     if (value) {
  61       map[numSlots - 1] &= paddingMask;
  62     }
  63   }
  64
  65   inline bool get(size_t offset) const {
  66     size_t index;
  67     WordT mask;
  68     getIndexAndMask(offset, &index, &mask);
  69     MOZ_ASSERT(index < nbits);
  70     return map[index] & mask;
  71   }
  72
  73   void set(size_t offset) {
  74     size_t index;
  75     WordT mask;
  76     getIndexAndMask(offset, &index, &mask);
  77     map[index] |= mask;
  78   }
  79
  80   void unset(size_t offset) {
  81     size_t index;
  82     WordT mask;
  83     getIndexAndMask(offset, &index, &mask);
  84     map[index] &= ~mask;
  85   }
  86
  87   bool isAllClear() const {
  88     for (size_t i = 0; i < numSlots; i++) {
  89       if (map[i]) {
  90         return false;
  91       }
  92     }
  93     return true;
  94   }
  95
  96   // For iterating over the set bits in the bit array, get a word at a time.
  97   WordT getWord(size_t elementIndex) const {
  98     MOZ_ASSERT(elementIndex < nbits);
  99     return map[elementIndex];
 100   }
 101
 102   // Update a word at a time.
 103   void setWord(size_t elementIndex, WordT value) {
 104     MOZ_ASSERT(elementIndex < nbits);
 105     map[elementIndex] = value;
 106   }
 107
 108   static void getIndexAndMask(size_t offset, size_t* indexp, WordT* maskp) {
 109     MOZ_ASSERT(offset < nbits);
 110     static_assert(bitsPerElement == 32, "unexpected bitsPerElement value");
 111     *indexp = offset / bitsPerElement;
 112     *maskp = WordT(1) << (offset % bitsPerElement);
 113   }
 114
 115   static size_t offsetOfMap() { return offsetof(BitArray<nbits>, map); }
 116 };
 117
 118 } /* namespace js */
 119
 120 #endif /* ds_BitArray_h */