blob: 4e34b1ecb1002669a92f4e977662728db1f63728 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* 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 jit_BitSet_h
#define jit_BitSet_h
#include "mozilla/Assertions.h"
#include "mozilla/MathAlgorithms.h"
#include <stddef.h>
#include <stdint.h>
namespace js {
namespace jit {
class TempAllocator;
// Provides constant time set insertion and removal, and fast linear
// set operations such as intersection, difference, and union.
// N.B. All set operations must be performed on sets with the same number
// of bits.
class BitSet {
public:
static const size_t BitsPerWord = 8 * sizeof(uint32_t);
static size_t RawLengthForBits(size_t bits) {
return (bits + BitsPerWord - 1) / BitsPerWord;
}
private:
uint32_t* bits_;
const unsigned int numBits_;
static inline uint32_t bitForValue(unsigned int value) {
return 1l << uint32_t(value % BitsPerWord);
}
static inline unsigned int wordForValue(unsigned int value) {
return value / BitsPerWord;
}
inline unsigned int numWords() const { return RawLengthForBits(numBits_); }
BitSet(const BitSet&) = delete;
void operator=(const BitSet&) = delete;
public:
class Iterator;
explicit BitSet(unsigned int numBits) : bits_(nullptr), numBits_(numBits) {}
[[nodiscard]] bool init(TempAllocator& alloc);
unsigned int getNumBits() const { return numBits_; }
// O(1): Check if this set contains the given value.
bool contains(unsigned int value) const {
MOZ_ASSERT(bits_);
MOZ_ASSERT(value < numBits_);
return !!(bits_[wordForValue(value)] & bitForValue(value));
}
// O(numBits): Check if this set contains any value.
bool empty() const;
// O(1): Insert the given value into this set.
void insert(unsigned int value) {
MOZ_ASSERT(bits_);
MOZ_ASSERT(value < numBits_);
bits_[wordForValue(value)] |= bitForValue(value);
}
// O(numBits): Insert every element of the given set into this set.
void insertAll(const BitSet& other);
// O(1): Remove the given value from this set.
void remove(unsigned int value) {
MOZ_ASSERT(bits_);
MOZ_ASSERT(value < numBits_);
bits_[wordForValue(value)] &= ~bitForValue(value);
}
// O(numBits): Remove the every element of the given set from this set.
void removeAll(const BitSet& other);
// O(numBits): Intersect this set with the given set.
void intersect(const BitSet& other);
// O(numBits): Intersect this set with the given set; return whether the
// intersection caused the set to change.
bool fixedPointIntersect(const BitSet& other);
// O(numBits): Does inplace complement of the set.
void complement();
// O(numBits): Clear this set.
void clear();
uint32_t* raw() const { return bits_; }
size_t rawLength() const { return numWords(); }
};
class BitSet::Iterator {
private:
BitSet& set_;
unsigned index_;
unsigned word_;
uint32_t value_;
void skipEmpty() {
// Skip words containing only zeros.
unsigned numWords = set_.numWords();
const uint32_t* bits = set_.bits_;
while (value_ == 0) {
word_++;
if (word_ == numWords) {
return;
}
index_ = word_ * BitSet::BitsPerWord;
value_ = bits[word_];
}
// Be careful: the result of CountTrailingZeroes32 is undefined if the
// input is 0.
int numZeros = mozilla::CountTrailingZeroes32(value_);
index_ += numZeros;
value_ >>= numZeros;
MOZ_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_));
}
public:
explicit Iterator(BitSet& set)
: set_(set), index_(0), word_(0), value_(set.bits_[0]) {
skipEmpty();
}
inline bool more() const { return word_ < set_.numWords(); }
explicit operator bool() const { return more(); }
inline void operator++() {
MOZ_ASSERT(more());
MOZ_ASSERT(index_ < set_.numBits_);
index_++;
value_ >>= 1;
skipEmpty();
}
unsigned int operator*() {
MOZ_ASSERT(index_ < set_.numBits_);
return index_;
}
};
} // namespace jit
} // namespace js
#endif /* jit_BitSet_h */
|
