/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef ds_BitArray_h
#define ds_BitArray_h
#include "mozilla/Assertions.h"
#include <limits.h>
#include <stddef.h>
#include <utility>
#include "jstypes.h"
namespace js {
/**
* A bit array is an array of bits represented by an array of words.
*/
/**
* Fixed size bit array using internal storage.
*/
template <size_t nbits, typename StorageType>
class BitArray {
public:
using WordT = StorageType;
static constexpr size_t bitsPerElement =
sizeof(WordT) * CHAR_BIT;
static constexpr size_t numWords = HowMany(nbits, bitsPerElement);
private:
WordT map[numWords];
public:
constexpr BitArray() : map() {};
inline bool get(size_t bitIndex)
const {
auto [index, mask] = getIndexAndMask(bitIndex);
return map[index] & mask;
}
void set(size_t bitIndex) {
auto [index, mask] = getIndexAndMask(bitIndex);
map[index] |= mask;
}
void unset(size_t bitIndex) {
auto [index, mask] = getIndexAndMask(bitIndex);
map[index] &= ~mask;
}
bool isAllClear()
const {
for (size_t i =
0; i < numWords; i++) {
if (map[i]) {
return false;
}
}
return true;
}
// For iterating over the set bits in the bit array, get a word at a time.
WordT getWord(size_t wordIndex)
const {
MOZ_ASSERT(wordIndex < numWords);
return map[wordIndex];
}
static auto getIndexAndMask(size_t bitIndex) {
MOZ_ASSERT(bitIndex < nbits);
size_t wordIndex = bitIndex / bitsPerElement;
MOZ_ASSERT(wordIndex < numWords);
WordT wordMask = WordT(
1) << (bitIndex % bitsPerElement);
return std::pair{wordIndex, wordMask};
}
static size_t offsetOfMap() {
return offsetof(BitArray, map); }
};
/**
* Variable size bit array using external storage.
*/
template <typename StorageType>
class ExternalBitArray {
public:
using WordT = StorageType;
static constexpr size_t bitsPerElement =
sizeof(WordT) * CHAR_BIT;
private:
WordT* array_;
#ifdef DEBUG
size_t length_;
#endif
auto getIndexAndMask(size_t bitIndex)
const {
MOZ_ASSERT(bitIndex < length_);
size_t wordIndex = bitIndex / bitsPerElement;
MOZ_ASSERT(wordIndex < NumWordsForLength(length_));
WordT wordMask = WordT(
1) << (bitIndex % bitsPerElement);
return std::pair{wordIndex, wordMask};
}
public:
ExternalBitArray(WordT* array, size_t length)
: array_(array)
#ifdef DEBUG
,
length_(length)
#endif
{
}
bool get(size_t bitIndex)
const {
auto [index, mask] = getIndexAndMask(bitIndex);
return array_[index] & mask;
}
void set(size_t bitIndex) {
auto [index, mask] = getIndexAndMask(bitIndex);
array_[index] |= mask;
}
void unset(size_t bitIndex) {
auto [index, mask] = getIndexAndMask(bitIndex);
array_[index] &= ~mask;
}
/**
* Return the number of words needed to represent `length` bits.
*/
static constexpr size_t NumWordsForLength(size_t length) {
return HowMany(length, bitsPerElement);
}
/**
* Return the bit length representable in `numWords` words.
*/
static constexpr size_t LengthForNumWords(size_t numWords) {
return numWords * bitsPerElement;
}
};
}
/* namespace js */
#endif /* ds_BitArray_h */
