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