Source code

Revision control

Other Tools

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
static void getIndexAndMask(size_t offset, size_t* indexp, WordT* maskp) {
103
MOZ_ASSERT(offset < nbits);
104
static_assert(bitsPerElement == 32, "unexpected bitsPerElement value");
105
*indexp = offset / bitsPerElement;
106
*maskp = WordT(1) << (offset % bitsPerElement);
107
}
108
109
static size_t offsetOfMap() { return offsetof(BitArray<nbits>, map); }
110
};
111
112
} /* namespace js */
113
114
#endif /* ds_BitArray_h */