/home/arjun/llvm-project/llvm/include/llvm/ADT/BitVector.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file implements the BitVector class. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_ADT_BITVECTOR_H |
14 | | #define LLVM_ADT_BITVECTOR_H |
15 | | |
16 | | #include "llvm/ADT/ArrayRef.h" |
17 | | #include "llvm/ADT/DenseMapInfo.h" |
18 | | #include "llvm/ADT/iterator_range.h" |
19 | | #include "llvm/Support/MathExtras.h" |
20 | | #include <algorithm> |
21 | | #include <cassert> |
22 | | #include <climits> |
23 | | #include <cstdint> |
24 | | #include <cstdlib> |
25 | | #include <cstring> |
26 | | #include <utility> |
27 | | |
28 | | namespace llvm { |
29 | | |
30 | | /// ForwardIterator for the bits that are set. |
31 | | /// Iterators get invalidated when resize / reserve is called. |
32 | | template <typename BitVectorT> class const_set_bits_iterator_impl { |
33 | | const BitVectorT &Parent; |
34 | | int Current = 0; |
35 | | |
36 | | void advance() { |
37 | | assert(Current != -1 && "Trying to advance past end."); |
38 | | Current = Parent.find_next(Current); |
39 | | } |
40 | | |
41 | | public: |
42 | | const_set_bits_iterator_impl(const BitVectorT &Parent, int Current) |
43 | | : Parent(Parent), Current(Current) {} |
44 | | explicit const_set_bits_iterator_impl(const BitVectorT &Parent) |
45 | | : const_set_bits_iterator_impl(Parent, Parent.find_first()) {} |
46 | | const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default; |
47 | | |
48 | | const_set_bits_iterator_impl operator++(int) { |
49 | | auto Prev = *this; |
50 | | advance(); |
51 | | return Prev; |
52 | | } |
53 | | |
54 | | const_set_bits_iterator_impl &operator++() { |
55 | | advance(); |
56 | | return *this; |
57 | | } |
58 | | |
59 | | unsigned operator*() const { return Current; } |
60 | | |
61 | | bool operator==(const const_set_bits_iterator_impl &Other) const { |
62 | | assert(&Parent == &Other.Parent && |
63 | | "Comparing iterators from different BitVectors"); |
64 | | return Current == Other.Current; |
65 | | } |
66 | | |
67 | | bool operator!=(const const_set_bits_iterator_impl &Other) const { |
68 | | assert(&Parent == &Other.Parent && |
69 | | "Comparing iterators from different BitVectors"); |
70 | | return Current != Other.Current; |
71 | | } |
72 | | }; |
73 | | |
74 | | class BitVector { |
75 | | typedef uintptr_t BitWord; |
76 | | |
77 | | enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; |
78 | | |
79 | | static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32, |
80 | | "Unsupported word size"); |
81 | | |
82 | | MutableArrayRef<BitWord> Bits; // Actual bits. |
83 | | unsigned Size; // Size of bitvector in bits. |
84 | | |
85 | | public: |
86 | | typedef unsigned size_type; |
87 | | // Encapsulation of a single bit. |
88 | | class reference { |
89 | | friend class BitVector; |
90 | | |
91 | | BitWord *WordRef; |
92 | | unsigned BitPos; |
93 | | |
94 | | public: |
95 | 0 | reference(BitVector &b, unsigned Idx) { |
96 | 0 | WordRef = &b.Bits[Idx / BITWORD_SIZE]; |
97 | 0 | BitPos = Idx % BITWORD_SIZE; |
98 | 0 | } |
99 | | |
100 | | reference() = delete; |
101 | | reference(const reference&) = default; |
102 | | |
103 | 0 | reference &operator=(reference t) { |
104 | 0 | *this = bool(t); |
105 | 0 | return *this; |
106 | 0 | } |
107 | | |
108 | 0 | reference& operator=(bool t) { |
109 | 0 | if (t) |
110 | 0 | *WordRef |= BitWord(1) << BitPos; |
111 | 0 | else |
112 | 0 | *WordRef &= ~(BitWord(1) << BitPos); |
113 | 0 | return *this; |
114 | 0 | } |
115 | | |
116 | 0 | operator bool() const { |
117 | 0 | return ((*WordRef) & (BitWord(1) << BitPos)) != 0; |
118 | 0 | } |
119 | | }; |
120 | | |
121 | | typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator; |
122 | | typedef const_set_bits_iterator set_iterator; |
123 | | |
124 | 0 | const_set_bits_iterator set_bits_begin() const { |
125 | 0 | return const_set_bits_iterator(*this); |
126 | 0 | } |
127 | 0 | const_set_bits_iterator set_bits_end() const { |
128 | 0 | return const_set_bits_iterator(*this, -1); |
129 | 0 | } |
130 | 0 | iterator_range<const_set_bits_iterator> set_bits() const { |
131 | 0 | return make_range(set_bits_begin(), set_bits_end()); |
132 | 0 | } |
133 | | |
134 | | /// BitVector default ctor - Creates an empty bitvector. |
135 | 0 | BitVector() : Size(0) {} |
136 | | |
137 | | /// BitVector ctor - Creates a bitvector of specified number of bits. All |
138 | | /// bits are initialized to the specified value. |
139 | 0 | explicit BitVector(unsigned s, bool t = false) : Size(s) { |
140 | 0 | size_t Capacity = NumBitWords(s); |
141 | 0 | Bits = allocate(Capacity); |
142 | 0 | init_words(Bits, t); |
143 | 0 | if (t) |
144 | 0 | clear_unused_bits(); |
145 | 0 | } |
146 | | |
147 | | /// BitVector copy ctor. |
148 | 0 | BitVector(const BitVector &RHS) : Size(RHS.size()) { |
149 | 0 | if (Size == 0) { |
150 | 0 | Bits = MutableArrayRef<BitWord>(); |
151 | 0 | return; |
152 | 0 | } |
153 | 0 |
|
154 | 0 | size_t Capacity = NumBitWords(RHS.size()); |
155 | 0 | Bits = allocate(Capacity); |
156 | 0 | std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord)); |
157 | 0 | } |
158 | | |
159 | 0 | BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) { |
160 | 0 | RHS.Bits = MutableArrayRef<BitWord>(); |
161 | 0 | RHS.Size = 0; |
162 | 0 | } |
163 | | |
164 | 0 | ~BitVector() { std::free(Bits.data()); } |
165 | | |
166 | | /// empty - Tests whether there are no bits in this bitvector. |
167 | 0 | bool empty() const { return Size == 0; } |
168 | | |
169 | | /// size - Returns the number of bits in this bitvector. |
170 | 0 | size_type size() const { return Size; } |
171 | | |
172 | | /// count - Returns the number of bits which are set. |
173 | 0 | size_type count() const { |
174 | 0 | unsigned NumBits = 0; |
175 | 0 | for (unsigned i = 0; i < NumBitWords(size()); ++i) |
176 | 0 | NumBits += countPopulation(Bits[i]); |
177 | 0 | return NumBits; |
178 | 0 | } |
179 | | |
180 | | /// any - Returns true if any bit is set. |
181 | 0 | bool any() const { |
182 | 0 | for (unsigned i = 0; i < NumBitWords(size()); ++i) |
183 | 0 | if (Bits[i] != 0) |
184 | 0 | return true; |
185 | 0 | return false; |
186 | 0 | } |
187 | | |
188 | | /// all - Returns true if all bits are set. |
189 | 0 | bool all() const { |
190 | 0 | for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i) |
191 | 0 | if (Bits[i] != ~BitWord(0)) |
192 | 0 | return false; |
193 | 0 |
|
194 | 0 | // If bits remain check that they are ones. The unused bits are always zero. |
195 | 0 | if (unsigned Remainder = Size % BITWORD_SIZE) |
196 | 0 | return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1; |
197 | 0 |
|
198 | 0 | return true; |
199 | 0 | } |
200 | | |
201 | | /// none - Returns true if none of the bits are set. |
202 | 0 | bool none() const { |
203 | 0 | return !any(); |
204 | 0 | } |
205 | | |
206 | | /// find_first_in - Returns the index of the first set bit in the range |
207 | | /// [Begin, End). Returns -1 if all bits in the range are unset. |
208 | 0 | int find_first_in(unsigned Begin, unsigned End) const { |
209 | 0 | assert(Begin <= End && End <= Size); |
210 | 0 | if (Begin == End) |
211 | 0 | return -1; |
212 | 0 |
|
213 | 0 | unsigned FirstWord = Begin / BITWORD_SIZE; |
214 | 0 | unsigned LastWord = (End - 1) / BITWORD_SIZE; |
215 | 0 |
|
216 | 0 | // Check subsequent words. |
217 | 0 | for (unsigned i = FirstWord; i <= LastWord; ++i) { |
218 | 0 | BitWord Copy = Bits[i]; |
219 | 0 |
|
220 | 0 | if (i == FirstWord) { |
221 | 0 | unsigned FirstBit = Begin % BITWORD_SIZE; |
222 | 0 | Copy &= maskTrailingZeros<BitWord>(FirstBit); |
223 | 0 | } |
224 | 0 |
|
225 | 0 | if (i == LastWord) { |
226 | 0 | unsigned LastBit = (End - 1) % BITWORD_SIZE; |
227 | 0 | Copy &= maskTrailingOnes<BitWord>(LastBit + 1); |
228 | 0 | } |
229 | 0 | if (Copy != 0) |
230 | 0 | return i * BITWORD_SIZE + countTrailingZeros(Copy); |
231 | 0 | } |
232 | 0 | return -1; |
233 | 0 | } |
234 | | |
235 | | /// find_last_in - Returns the index of the last set bit in the range |
236 | | /// [Begin, End). Returns -1 if all bits in the range are unset. |
237 | 0 | int find_last_in(unsigned Begin, unsigned End) const { |
238 | 0 | assert(Begin <= End && End <= Size); |
239 | 0 | if (Begin == End) |
240 | 0 | return -1; |
241 | 0 |
|
242 | 0 | unsigned LastWord = (End - 1) / BITWORD_SIZE; |
243 | 0 | unsigned FirstWord = Begin / BITWORD_SIZE; |
244 | 0 |
|
245 | 0 | for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) { |
246 | 0 | unsigned CurrentWord = i - 1; |
247 | 0 |
|
248 | 0 | BitWord Copy = Bits[CurrentWord]; |
249 | 0 | if (CurrentWord == LastWord) { |
250 | 0 | unsigned LastBit = (End - 1) % BITWORD_SIZE; |
251 | 0 | Copy &= maskTrailingOnes<BitWord>(LastBit + 1); |
252 | 0 | } |
253 | 0 |
|
254 | 0 | if (CurrentWord == FirstWord) { |
255 | 0 | unsigned FirstBit = Begin % BITWORD_SIZE; |
256 | 0 | Copy &= maskTrailingZeros<BitWord>(FirstBit); |
257 | 0 | } |
258 | 0 |
|
259 | 0 | if (Copy != 0) |
260 | 0 | return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1; |
261 | 0 | } |
262 | 0 |
|
263 | 0 | return -1; |
264 | 0 | } |
265 | | |
266 | | /// find_first_unset_in - Returns the index of the first unset bit in the |
267 | | /// range [Begin, End). Returns -1 if all bits in the range are set. |
268 | 0 | int find_first_unset_in(unsigned Begin, unsigned End) const { |
269 | 0 | assert(Begin <= End && End <= Size); |
270 | 0 | if (Begin == End) |
271 | 0 | return -1; |
272 | 0 |
|
273 | 0 | unsigned FirstWord = Begin / BITWORD_SIZE; |
274 | 0 | unsigned LastWord = (End - 1) / BITWORD_SIZE; |
275 | 0 |
|
276 | 0 | // Check subsequent words. |
277 | 0 | for (unsigned i = FirstWord; i <= LastWord; ++i) { |
278 | 0 | BitWord Copy = Bits[i]; |
279 | 0 |
|
280 | 0 | if (i == FirstWord) { |
281 | 0 | unsigned FirstBit = Begin % BITWORD_SIZE; |
282 | 0 | Copy |= maskTrailingOnes<BitWord>(FirstBit); |
283 | 0 | } |
284 | 0 |
|
285 | 0 | if (i == LastWord) { |
286 | 0 | unsigned LastBit = (End - 1) % BITWORD_SIZE; |
287 | 0 | Copy |= maskTrailingZeros<BitWord>(LastBit + 1); |
288 | 0 | } |
289 | 0 | if (Copy != ~BitWord(0)) { |
290 | 0 | unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy); |
291 | 0 | return Result < size() ? Result : -1; |
292 | 0 | } |
293 | 0 | } |
294 | 0 | return -1; |
295 | 0 | } |
296 | | |
297 | | /// find_last_unset_in - Returns the index of the last unset bit in the |
298 | | /// range [Begin, End). Returns -1 if all bits in the range are set. |
299 | 0 | int find_last_unset_in(unsigned Begin, unsigned End) const { |
300 | 0 | assert(Begin <= End && End <= Size); |
301 | 0 | if (Begin == End) |
302 | 0 | return -1; |
303 | 0 |
|
304 | 0 | unsigned LastWord = (End - 1) / BITWORD_SIZE; |
305 | 0 | unsigned FirstWord = Begin / BITWORD_SIZE; |
306 | 0 |
|
307 | 0 | for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) { |
308 | 0 | unsigned CurrentWord = i - 1; |
309 | 0 |
|
310 | 0 | BitWord Copy = Bits[CurrentWord]; |
311 | 0 | if (CurrentWord == LastWord) { |
312 | 0 | unsigned LastBit = (End - 1) % BITWORD_SIZE; |
313 | 0 | Copy |= maskTrailingZeros<BitWord>(LastBit + 1); |
314 | 0 | } |
315 | 0 |
|
316 | 0 | if (CurrentWord == FirstWord) { |
317 | 0 | unsigned FirstBit = Begin % BITWORD_SIZE; |
318 | 0 | Copy |= maskTrailingOnes<BitWord>(FirstBit); |
319 | 0 | } |
320 | 0 |
|
321 | 0 | if (Copy != ~BitWord(0)) { |
322 | 0 | unsigned Result = |
323 | 0 | (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1; |
324 | 0 | return Result < Size ? Result : -1; |
325 | 0 | } |
326 | 0 | } |
327 | 0 | return -1; |
328 | 0 | } |
329 | | |
330 | | /// find_first - Returns the index of the first set bit, -1 if none |
331 | | /// of the bits are set. |
332 | 0 | int find_first() const { return find_first_in(0, Size); } |
333 | | |
334 | | /// find_last - Returns the index of the last set bit, -1 if none of the bits |
335 | | /// are set. |
336 | 0 | int find_last() const { return find_last_in(0, Size); } |
337 | | |
338 | | /// find_next - Returns the index of the next set bit following the |
339 | | /// "Prev" bit. Returns -1 if the next set bit is not found. |
340 | 0 | int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); } |
341 | | |
342 | | /// find_prev - Returns the index of the first set bit that precedes the |
343 | | /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. |
344 | 0 | int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); } |
345 | | |
346 | | /// find_first_unset - Returns the index of the first unset bit, -1 if all |
347 | | /// of the bits are set. |
348 | 0 | int find_first_unset() const { return find_first_unset_in(0, Size); } |
349 | | |
350 | | /// find_next_unset - Returns the index of the next unset bit following the |
351 | | /// "Prev" bit. Returns -1 if all remaining bits are set. |
352 | 0 | int find_next_unset(unsigned Prev) const { |
353 | 0 | return find_first_unset_in(Prev + 1, Size); |
354 | 0 | } |
355 | | |
356 | | /// find_last_unset - Returns the index of the last unset bit, -1 if all of |
357 | | /// the bits are set. |
358 | 0 | int find_last_unset() const { return find_last_unset_in(0, Size); } |
359 | | |
360 | | /// find_prev_unset - Returns the index of the first unset bit that precedes |
361 | | /// the bit at \p PriorTo. Returns -1 if all previous bits are set. |
362 | 0 | int find_prev_unset(unsigned PriorTo) { |
363 | 0 | return find_last_unset_in(0, PriorTo); |
364 | 0 | } |
365 | | |
366 | | /// clear - Removes all bits from the bitvector. Does not change capacity. |
367 | 0 | void clear() { |
368 | 0 | Size = 0; |
369 | 0 | } |
370 | | |
371 | | /// resize - Grow or shrink the bitvector. |
372 | 0 | void resize(unsigned N, bool t = false) { |
373 | 0 | if (N > getBitCapacity()) { |
374 | 0 | unsigned OldCapacity = Bits.size(); |
375 | 0 | grow(N); |
376 | 0 | init_words(Bits.drop_front(OldCapacity), t); |
377 | 0 | } |
378 | 0 |
|
379 | 0 | // Set any old unused bits that are now included in the BitVector. This |
380 | 0 | // may set bits that are not included in the new vector, but we will clear |
381 | 0 | // them back out below. |
382 | 0 | if (N > Size) |
383 | 0 | set_unused_bits(t); |
384 | 0 |
|
385 | 0 | // Update the size, and clear out any bits that are now unused |
386 | 0 | unsigned OldSize = Size; |
387 | 0 | Size = N; |
388 | 0 | if (t || N < OldSize) |
389 | 0 | clear_unused_bits(); |
390 | 0 | } |
391 | | |
392 | 0 | void reserve(unsigned N) { |
393 | 0 | if (N > getBitCapacity()) |
394 | 0 | grow(N); |
395 | 0 | } |
396 | | |
397 | | // Set, reset, flip |
398 | 0 | BitVector &set() { |
399 | 0 | init_words(Bits, true); |
400 | 0 | clear_unused_bits(); |
401 | 0 | return *this; |
402 | 0 | } |
403 | | |
404 | 0 | BitVector &set(unsigned Idx) { |
405 | 0 | assert(Bits.data() && "Bits never allocated"); |
406 | 0 | Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); |
407 | 0 | return *this; |
408 | 0 | } |
409 | | |
410 | | /// set - Efficiently set a range of bits in [I, E) |
411 | 0 | BitVector &set(unsigned I, unsigned E) { |
412 | 0 | assert(I <= E && "Attempted to set backwards range!"); |
413 | 0 | assert(E <= size() && "Attempted to set out-of-bounds range!"); |
414 | 0 |
|
415 | 0 | if (I == E) return *this; |
416 | 0 |
|
417 | 0 | if (I / BITWORD_SIZE == E / BITWORD_SIZE) { |
418 | 0 | BitWord EMask = BitWord(1) << (E % BITWORD_SIZE); |
419 | 0 | BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); |
420 | 0 | BitWord Mask = EMask - IMask; |
421 | 0 | Bits[I / BITWORD_SIZE] |= Mask; |
422 | 0 | return *this; |
423 | 0 | } |
424 | 0 |
|
425 | 0 | BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE); |
426 | 0 | Bits[I / BITWORD_SIZE] |= PrefixMask; |
427 | 0 | I = alignTo(I, BITWORD_SIZE); |
428 | 0 |
|
429 | 0 | for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) |
430 | 0 | Bits[I / BITWORD_SIZE] = ~BitWord(0); |
431 | 0 |
|
432 | 0 | BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1; |
433 | 0 | if (I < E) |
434 | 0 | Bits[I / BITWORD_SIZE] |= PostfixMask; |
435 | 0 |
|
436 | 0 | return *this; |
437 | 0 | } |
438 | | |
439 | 0 | BitVector &reset() { |
440 | 0 | init_words(Bits, false); |
441 | 0 | return *this; |
442 | 0 | } |
443 | | |
444 | 0 | BitVector &reset(unsigned Idx) { |
445 | 0 | Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE)); |
446 | 0 | return *this; |
447 | 0 | } |
448 | | |
449 | | /// reset - Efficiently reset a range of bits in [I, E) |
450 | 0 | BitVector &reset(unsigned I, unsigned E) { |
451 | 0 | assert(I <= E && "Attempted to reset backwards range!"); |
452 | 0 | assert(E <= size() && "Attempted to reset out-of-bounds range!"); |
453 | 0 |
|
454 | 0 | if (I == E) return *this; |
455 | 0 |
|
456 | 0 | if (I / BITWORD_SIZE == E / BITWORD_SIZE) { |
457 | 0 | BitWord EMask = BitWord(1) << (E % BITWORD_SIZE); |
458 | 0 | BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); |
459 | 0 | BitWord Mask = EMask - IMask; |
460 | 0 | Bits[I / BITWORD_SIZE] &= ~Mask; |
461 | 0 | return *this; |
462 | 0 | } |
463 | 0 |
|
464 | 0 | BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE); |
465 | 0 | Bits[I / BITWORD_SIZE] &= ~PrefixMask; |
466 | 0 | I = alignTo(I, BITWORD_SIZE); |
467 | 0 |
|
468 | 0 | for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) |
469 | 0 | Bits[I / BITWORD_SIZE] = BitWord(0); |
470 | 0 |
|
471 | 0 | BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1; |
472 | 0 | if (I < E) |
473 | 0 | Bits[I / BITWORD_SIZE] &= ~PostfixMask; |
474 | 0 |
|
475 | 0 | return *this; |
476 | 0 | } |
477 | | |
478 | 0 | BitVector &flip() { |
479 | 0 | for (unsigned i = 0; i < NumBitWords(size()); ++i) |
480 | 0 | Bits[i] = ~Bits[i]; |
481 | 0 | clear_unused_bits(); |
482 | 0 | return *this; |
483 | 0 | } |
484 | | |
485 | 0 | BitVector &flip(unsigned Idx) { |
486 | 0 | Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); |
487 | 0 | return *this; |
488 | 0 | } |
489 | | |
490 | | // Indexing. |
491 | 0 | reference operator[](unsigned Idx) { |
492 | 0 | assert (Idx < Size && "Out-of-bounds Bit access."); |
493 | 0 | return reference(*this, Idx); |
494 | 0 | } |
495 | | |
496 | 0 | bool operator[](unsigned Idx) const { |
497 | 0 | assert (Idx < Size && "Out-of-bounds Bit access."); |
498 | 0 | BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE); |
499 | 0 | return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; |
500 | 0 | } |
501 | | |
502 | 0 | bool test(unsigned Idx) const { |
503 | 0 | return (*this)[Idx]; |
504 | 0 | } |
505 | | |
506 | | // Push single bit to end of vector. |
507 | 0 | void push_back(bool Val) { |
508 | 0 | unsigned OldSize = Size; |
509 | 0 | unsigned NewSize = Size + 1; |
510 | 0 |
|
511 | 0 | // Resize, which will insert zeros. |
512 | 0 | // If we already fit then the unused bits will be already zero. |
513 | 0 | if (NewSize > getBitCapacity()) |
514 | 0 | resize(NewSize, false); |
515 | 0 | else |
516 | 0 | Size = NewSize; |
517 | 0 |
|
518 | 0 | // If true, set single bit. |
519 | 0 | if (Val) |
520 | 0 | set(OldSize); |
521 | 0 | } |
522 | | |
523 | | /// Test if any common bits are set. |
524 | 0 | bool anyCommon(const BitVector &RHS) const { |
525 | 0 | unsigned ThisWords = NumBitWords(size()); |
526 | 0 | unsigned RHSWords = NumBitWords(RHS.size()); |
527 | 0 | for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) |
528 | 0 | if (Bits[i] & RHS.Bits[i]) |
529 | 0 | return true; |
530 | 0 | return false; |
531 | 0 | } |
532 | | |
533 | | // Comparison operators. |
534 | 0 | bool operator==(const BitVector &RHS) const { |
535 | 0 | if (size() != RHS.size()) |
536 | 0 | return false; |
537 | 0 | unsigned NumWords = NumBitWords(size()); |
538 | 0 | return Bits.take_front(NumWords) == RHS.Bits.take_front(NumWords); |
539 | 0 | } |
540 | | |
541 | 0 | bool operator!=(const BitVector &RHS) const { |
542 | 0 | return !(*this == RHS); |
543 | 0 | } |
544 | | |
545 | | /// Intersection, union, disjoint union. |
546 | 0 | BitVector &operator&=(const BitVector &RHS) { |
547 | 0 | unsigned ThisWords = NumBitWords(size()); |
548 | 0 | unsigned RHSWords = NumBitWords(RHS.size()); |
549 | 0 | unsigned i; |
550 | 0 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |
551 | 0 | Bits[i] &= RHS.Bits[i]; |
552 | 0 |
|
553 | 0 | // Any bits that are just in this bitvector become zero, because they aren't |
554 | 0 | // in the RHS bit vector. Any words only in RHS are ignored because they |
555 | 0 | // are already zero in the LHS. |
556 | 0 | for (; i != ThisWords; ++i) |
557 | 0 | Bits[i] = 0; |
558 | 0 |
|
559 | 0 | return *this; |
560 | 0 | } |
561 | | |
562 | | /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. |
563 | 0 | BitVector &reset(const BitVector &RHS) { |
564 | 0 | unsigned ThisWords = NumBitWords(size()); |
565 | 0 | unsigned RHSWords = NumBitWords(RHS.size()); |
566 | 0 | unsigned i; |
567 | 0 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |
568 | 0 | Bits[i] &= ~RHS.Bits[i]; |
569 | 0 | return *this; |
570 | 0 | } |
571 | | |
572 | | /// test - Check if (This - RHS) is zero. |
573 | | /// This is the same as reset(RHS) and any(). |
574 | 0 | bool test(const BitVector &RHS) const { |
575 | 0 | unsigned ThisWords = NumBitWords(size()); |
576 | 0 | unsigned RHSWords = NumBitWords(RHS.size()); |
577 | 0 | unsigned i; |
578 | 0 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |
579 | 0 | if ((Bits[i] & ~RHS.Bits[i]) != 0) |
580 | 0 | return true; |
581 | 0 |
|
582 | 0 | for (; i != ThisWords ; ++i) |
583 | 0 | if (Bits[i] != 0) |
584 | 0 | return true; |
585 | 0 |
|
586 | 0 | return false; |
587 | 0 | } |
588 | | |
589 | 0 | BitVector &operator|=(const BitVector &RHS) { |
590 | 0 | if (size() < RHS.size()) |
591 | 0 | resize(RHS.size()); |
592 | 0 | for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) |
593 | 0 | Bits[i] |= RHS.Bits[i]; |
594 | 0 | return *this; |
595 | 0 | } |
596 | | |
597 | 0 | BitVector &operator^=(const BitVector &RHS) { |
598 | 0 | if (size() < RHS.size()) |
599 | 0 | resize(RHS.size()); |
600 | 0 | for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) |
601 | 0 | Bits[i] ^= RHS.Bits[i]; |
602 | 0 | return *this; |
603 | 0 | } |
604 | | |
605 | 0 | BitVector &operator>>=(unsigned N) { |
606 | 0 | assert(N <= Size); |
607 | 0 | if (LLVM_UNLIKELY(empty() || N == 0)) |
608 | 0 | return *this; |
609 | 0 |
|
610 | 0 | unsigned NumWords = NumBitWords(Size); |
611 | 0 | assert(NumWords >= 1); |
612 | 0 |
|
613 | 0 | wordShr(N / BITWORD_SIZE); |
614 | 0 |
|
615 | 0 | unsigned BitDistance = N % BITWORD_SIZE; |
616 | 0 | if (BitDistance == 0) |
617 | 0 | return *this; |
618 | 0 |
|
619 | 0 | // When the shift size is not a multiple of the word size, then we have |
620 | 0 | // a tricky situation where each word in succession needs to extract some |
621 | 0 | // of the bits from the next word and or them into this word while |
622 | 0 | // shifting this word to make room for the new bits. This has to be done |
623 | 0 | // for every word in the array. |
624 | 0 |
|
625 | 0 | // Since we're shifting each word right, some bits will fall off the end |
626 | 0 | // of each word to the right, and empty space will be created on the left. |
627 | 0 | // The final word in the array will lose bits permanently, so starting at |
628 | 0 | // the beginning, work forwards shifting each word to the right, and |
629 | 0 | // OR'ing in the bits from the end of the next word to the beginning of |
630 | 0 | // the current word. |
631 | 0 |
|
632 | 0 | // Example: |
633 | 0 | // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right |
634 | 0 | // by 4 bits. |
635 | 0 | // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD |
636 | 0 | // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD |
637 | 0 | // Step 3: Word[1] >>= 4 ; 0x0EEFF001 |
638 | 0 | // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001 |
639 | 0 | // Step 5: Word[2] >>= 4 ; 0x02334455 |
640 | 0 | // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 } |
641 | 0 | const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance); |
642 | 0 | const unsigned LSH = BITWORD_SIZE - BitDistance; |
643 | 0 |
|
644 | 0 | for (unsigned I = 0; I < NumWords - 1; ++I) { |
645 | 0 | Bits[I] >>= BitDistance; |
646 | 0 | Bits[I] |= (Bits[I + 1] & Mask) << LSH; |
647 | 0 | } |
648 | 0 |
|
649 | 0 | Bits[NumWords - 1] >>= BitDistance; |
650 | 0 |
|
651 | 0 | return *this; |
652 | 0 | } |
653 | | |
654 | 0 | BitVector &operator<<=(unsigned N) { |
655 | 0 | assert(N <= Size); |
656 | 0 | if (LLVM_UNLIKELY(empty() || N == 0)) |
657 | 0 | return *this; |
658 | 0 |
|
659 | 0 | unsigned NumWords = NumBitWords(Size); |
660 | 0 | assert(NumWords >= 1); |
661 | 0 |
|
662 | 0 | wordShl(N / BITWORD_SIZE); |
663 | 0 |
|
664 | 0 | unsigned BitDistance = N % BITWORD_SIZE; |
665 | 0 | if (BitDistance == 0) |
666 | 0 | return *this; |
667 | 0 |
|
668 | 0 | // When the shift size is not a multiple of the word size, then we have |
669 | 0 | // a tricky situation where each word in succession needs to extract some |
670 | 0 | // of the bits from the previous word and or them into this word while |
671 | 0 | // shifting this word to make room for the new bits. This has to be done |
672 | 0 | // for every word in the array. This is similar to the algorithm outlined |
673 | 0 | // in operator>>=, but backwards. |
674 | 0 |
|
675 | 0 | // Since we're shifting each word left, some bits will fall off the end |
676 | 0 | // of each word to the left, and empty space will be created on the right. |
677 | 0 | // The first word in the array will lose bits permanently, so starting at |
678 | 0 | // the end, work backwards shifting each word to the left, and OR'ing |
679 | 0 | // in the bits from the end of the next word to the beginning of the |
680 | 0 | // current word. |
681 | 0 |
|
682 | 0 | // Example: |
683 | 0 | // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left |
684 | 0 | // by 4 bits. |
685 | 0 | // Step 1: Word[2] <<= 4 ; 0x23344550 |
686 | 0 | // Step 2: Word[2] |= 0x0000000E ; 0x2334455E |
687 | 0 | // Step 3: Word[1] <<= 4 ; 0xEFF00110 |
688 | 0 | // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A |
689 | 0 | // Step 5: Word[0] <<= 4 ; 0xABBCCDD0 |
690 | 0 | // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E } |
691 | 0 | const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance); |
692 | 0 | const unsigned RSH = BITWORD_SIZE - BitDistance; |
693 | 0 |
|
694 | 0 | for (int I = NumWords - 1; I > 0; --I) { |
695 | 0 | Bits[I] <<= BitDistance; |
696 | 0 | Bits[I] |= (Bits[I - 1] & Mask) >> RSH; |
697 | 0 | } |
698 | 0 | Bits[0] <<= BitDistance; |
699 | 0 | clear_unused_bits(); |
700 | 0 |
|
701 | 0 | return *this; |
702 | 0 | } |
703 | | |
704 | | // Assignment operator. |
705 | 0 | const BitVector &operator=(const BitVector &RHS) { |
706 | 0 | if (this == &RHS) return *this; |
707 | 0 |
|
708 | 0 | Size = RHS.size(); |
709 | 0 |
|
710 | 0 | // Handle tombstone when the BitVector is a key of a DenseHash. |
711 | 0 | if (RHS.isInvalid()) { |
712 | 0 | std::free(Bits.data()); |
713 | 0 | Bits = None; |
714 | 0 | return *this; |
715 | 0 | } |
716 | 0 |
|
717 | 0 | unsigned RHSWords = NumBitWords(Size); |
718 | 0 | if (Size <= getBitCapacity()) { |
719 | 0 | if (Size) |
720 | 0 | std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord)); |
721 | 0 | clear_unused_bits(); |
722 | 0 | return *this; |
723 | 0 | } |
724 | 0 |
|
725 | 0 | // Grow the bitvector to have enough elements. |
726 | 0 | unsigned NewCapacity = RHSWords; |
727 | 0 | assert(NewCapacity > 0 && "negative capacity?"); |
728 | 0 | auto NewBits = allocate(NewCapacity); |
729 | 0 | std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord)); |
730 | 0 |
|
731 | 0 | // Destroy the old bits. |
732 | 0 | std::free(Bits.data()); |
733 | 0 | Bits = NewBits; |
734 | 0 |
|
735 | 0 | return *this; |
736 | 0 | } |
737 | | |
738 | 0 | const BitVector &operator=(BitVector &&RHS) { |
739 | 0 | if (this == &RHS) return *this; |
740 | 0 |
|
741 | 0 | std::free(Bits.data()); |
742 | 0 | Bits = RHS.Bits; |
743 | 0 | Size = RHS.Size; |
744 | 0 |
|
745 | 0 | RHS.Bits = MutableArrayRef<BitWord>(); |
746 | 0 | RHS.Size = 0; |
747 | 0 |
|
748 | 0 | return *this; |
749 | 0 | } |
750 | | |
751 | 0 | void swap(BitVector &RHS) { |
752 | 0 | std::swap(Bits, RHS.Bits); |
753 | 0 | std::swap(Size, RHS.Size); |
754 | 0 | } |
755 | | |
756 | 0 | void invalid() { |
757 | 0 | assert(!Size && Bits.empty()); |
758 | 0 | Size = (unsigned)-1; |
759 | 0 | } |
760 | 0 | bool isInvalid() const { return Size == (unsigned)-1; } |
761 | | |
762 | 0 | ArrayRef<BitWord> getData() const { |
763 | 0 | return Bits.take_front(NumBitWords(size())); |
764 | 0 | } |
765 | | |
766 | | //===--------------------------------------------------------------------===// |
767 | | // Portable bit mask operations. |
768 | | //===--------------------------------------------------------------------===// |
769 | | // |
770 | | // These methods all operate on arrays of uint32_t, each holding 32 bits. The |
771 | | // fixed word size makes it easier to work with literal bit vector constants |
772 | | // in portable code. |
773 | | // |
774 | | // The LSB in each word is the lowest numbered bit. The size of a portable |
775 | | // bit mask is always a whole multiple of 32 bits. If no bit mask size is |
776 | | // given, the bit mask is assumed to cover the entire BitVector. |
777 | | |
778 | | /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. |
779 | | /// This computes "*this |= Mask". |
780 | 0 | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
781 | 0 | applyMask<true, false>(Mask, MaskWords); |
782 | 0 | } |
783 | | |
784 | | /// clearBitsInMask - Clear any bits in this vector that are set in Mask. |
785 | | /// Don't resize. This computes "*this &= ~Mask". |
786 | 0 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
787 | 0 | applyMask<false, false>(Mask, MaskWords); |
788 | 0 | } |
789 | | |
790 | | /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. |
791 | | /// Don't resize. This computes "*this |= ~Mask". |
792 | 0 | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
793 | 0 | applyMask<true, true>(Mask, MaskWords); |
794 | 0 | } |
795 | | |
796 | | /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. |
797 | | /// Don't resize. This computes "*this &= Mask". |
798 | 0 | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
799 | 0 | applyMask<false, true>(Mask, MaskWords); |
800 | 0 | } |
801 | | |
802 | | private: |
803 | | /// Perform a logical left shift of \p Count words by moving everything |
804 | | /// \p Count words to the right in memory. |
805 | | /// |
806 | | /// While confusing, words are stored from least significant at Bits[0] to |
807 | | /// most significant at Bits[NumWords-1]. A logical shift left, however, |
808 | | /// moves the current least significant bit to a higher logical index, and |
809 | | /// fills the previous least significant bits with 0. Thus, we actually |
810 | | /// need to move the bytes of the memory to the right, not to the left. |
811 | | /// Example: |
812 | | /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000] |
813 | | /// represents a BitVector where 0xBBBBAAAA contain the least significant |
814 | | /// bits. So if we want to shift the BitVector left by 2 words, we need to |
815 | | /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a |
816 | | /// memmove which moves right, not left. |
817 | 0 | void wordShl(uint32_t Count) { |
818 | 0 | if (Count == 0) |
819 | 0 | return; |
820 | 0 |
|
821 | 0 | uint32_t NumWords = NumBitWords(Size); |
822 | 0 |
|
823 | 0 | auto Src = Bits.take_front(NumWords).drop_back(Count); |
824 | 0 | auto Dest = Bits.take_front(NumWords).drop_front(Count); |
825 | 0 |
|
826 | 0 | // Since we always move Word-sized chunks of data with src and dest both |
827 | 0 | // aligned to a word-boundary, we don't need to worry about endianness |
828 | 0 | // here. |
829 | 0 | std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord)); |
830 | 0 | std::memset(Bits.data(), 0, Count * sizeof(BitWord)); |
831 | 0 | clear_unused_bits(); |
832 | 0 | } |
833 | | |
834 | | /// Perform a logical right shift of \p Count words by moving those |
835 | | /// words to the left in memory. See wordShl for more information. |
836 | | /// |
837 | 0 | void wordShr(uint32_t Count) { |
838 | 0 | if (Count == 0) |
839 | 0 | return; |
840 | 0 |
|
841 | 0 | uint32_t NumWords = NumBitWords(Size); |
842 | 0 |
|
843 | 0 | auto Src = Bits.take_front(NumWords).drop_front(Count); |
844 | 0 | auto Dest = Bits.take_front(NumWords).drop_back(Count); |
845 | 0 | assert(Dest.size() == Src.size()); |
846 | 0 |
|
847 | 0 | std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord)); |
848 | 0 | std::memset(Dest.end(), 0, Count * sizeof(BitWord)); |
849 | 0 | } |
850 | | |
851 | 0 | MutableArrayRef<BitWord> allocate(size_t NumWords) { |
852 | 0 | BitWord *RawBits = static_cast<BitWord *>( |
853 | 0 | safe_malloc(NumWords * sizeof(BitWord))); |
854 | 0 | return MutableArrayRef<BitWord>(RawBits, NumWords); |
855 | 0 | } |
856 | | |
857 | 0 | int next_unset_in_word(int WordIndex, BitWord Word) const { |
858 | 0 | unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word); |
859 | 0 | return Result < size() ? Result : -1; |
860 | 0 | } |
861 | | |
862 | 0 | unsigned NumBitWords(unsigned S) const { |
863 | 0 | return (S + BITWORD_SIZE-1) / BITWORD_SIZE; |
864 | 0 | } |
865 | | |
866 | | // Set the unused bits in the high words. |
867 | 0 | void set_unused_bits(bool t = true) { |
868 | 0 | // Set high words first. |
869 | 0 | unsigned UsedWords = NumBitWords(Size); |
870 | 0 | if (Bits.size() > UsedWords) |
871 | 0 | init_words(Bits.drop_front(UsedWords), t); |
872 | 0 |
|
873 | 0 | // Then set any stray high bits of the last used word. |
874 | 0 | unsigned ExtraBits = Size % BITWORD_SIZE; |
875 | 0 | if (ExtraBits) { |
876 | 0 | BitWord ExtraBitMask = ~BitWord(0) << ExtraBits; |
877 | 0 | if (t) |
878 | 0 | Bits[UsedWords-1] |= ExtraBitMask; |
879 | 0 | else |
880 | 0 | Bits[UsedWords-1] &= ~ExtraBitMask; |
881 | 0 | } |
882 | 0 | } |
883 | | |
884 | | // Clear the unused bits in the high words. |
885 | 0 | void clear_unused_bits() { |
886 | 0 | set_unused_bits(false); |
887 | 0 | } |
888 | | |
889 | 0 | void grow(unsigned NewSize) { |
890 | 0 | size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2); |
891 | 0 | assert(NewCapacity > 0 && "realloc-ing zero space"); |
892 | 0 | BitWord *NewBits = static_cast<BitWord *>( |
893 | 0 | safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord))); |
894 | 0 | Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity); |
895 | 0 | clear_unused_bits(); |
896 | 0 | } |
897 | | |
898 | 0 | void init_words(MutableArrayRef<BitWord> B, bool t) { |
899 | 0 | if (B.size() > 0) |
900 | 0 | memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord)); |
901 | 0 | } |
902 | | |
903 | | template<bool AddBits, bool InvertMask> |
904 | 0 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { |
905 | 0 | static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size."); |
906 | 0 | MaskWords = std::min(MaskWords, (size() + 31) / 32); |
907 | 0 | const unsigned Scale = BITWORD_SIZE / 32; |
908 | 0 | unsigned i; |
909 | 0 | for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { |
910 | 0 | BitWord BW = Bits[i]; |
911 | 0 | // This inner loop should unroll completely when BITWORD_SIZE > 32. |
912 | 0 | for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { |
913 | 0 | uint32_t M = *Mask++; |
914 | 0 | if (InvertMask) M = ~M; |
915 | 0 | if (AddBits) BW |= BitWord(M) << b; |
916 | 0 | else BW &= ~(BitWord(M) << b); |
917 | 0 | } |
918 | 0 | Bits[i] = BW; |
919 | 0 | } |
920 | 0 | for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { |
921 | 0 | uint32_t M = *Mask++; |
922 | 0 | if (InvertMask) M = ~M; |
923 | 0 | if (AddBits) Bits[i] |= BitWord(M) << b; |
924 | 0 | else Bits[i] &= ~(BitWord(M) << b); |
925 | 0 | } |
926 | 0 | if (AddBits) |
927 | 0 | clear_unused_bits(); |
928 | 0 | } Unexecuted instantiation: _ZN4llvm9BitVector9applyMaskILb1ELb0EEEvPKjj Unexecuted instantiation: _ZN4llvm9BitVector9applyMaskILb0ELb0EEEvPKjj Unexecuted instantiation: _ZN4llvm9BitVector9applyMaskILb1ELb1EEEvPKjj Unexecuted instantiation: _ZN4llvm9BitVector9applyMaskILb0ELb1EEEvPKjj |
929 | | |
930 | | public: |
931 | | /// Return the size (in bytes) of the bit vector. |
932 | 0 | size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); } |
933 | 0 | size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; } |
934 | | }; |
935 | | |
936 | 0 | inline size_t capacity_in_bytes(const BitVector &X) { |
937 | 0 | return X.getMemorySize(); |
938 | 0 | } |
939 | | |
940 | | template <> struct DenseMapInfo<BitVector> { |
941 | 0 | static inline BitVector getEmptyKey() { return BitVector(); } |
942 | 0 | static inline BitVector getTombstoneKey() { |
943 | 0 | BitVector V; |
944 | 0 | V.invalid(); |
945 | 0 | return V; |
946 | 0 | } |
947 | 0 | static unsigned getHashValue(const BitVector &V) { |
948 | 0 | return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue( |
949 | 0 | std::make_pair(V.size(), V.getData())); |
950 | 0 | } |
951 | 0 | static bool isEqual(const BitVector &LHS, const BitVector &RHS) { |
952 | 0 | if (LHS.isInvalid() || RHS.isInvalid()) |
953 | 0 | return LHS.isInvalid() == RHS.isInvalid(); |
954 | 0 | return LHS == RHS; |
955 | 0 | } |
956 | | }; |
957 | | } // end namespace llvm |
958 | | |
959 | | namespace std { |
960 | | /// Implement std::swap in terms of BitVector swap. |
961 | | inline void |
962 | 0 | swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { |
963 | 0 | LHS.swap(RHS); |
964 | 0 | } |
965 | | } // end namespace std |
966 | | |
967 | | #endif // LLVM_ADT_BITVECTOR_H |