1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_BIT_VECTOR_H_
6#define RUNTIME_VM_BIT_VECTOR_H_
7
8#include "vm/allocation.h"
9#include "vm/isolate.h"
10#include "vm/zone.h"
11
12namespace dart {
13
14// Bit vector implementation.
15class BitVector : public ZoneAllocated {
16 public:
17 // Iterator for the elements of this BitVector.
18 class Iterator : public ValueObject {
19 public:
20 explicit Iterator(BitVector* target)
21 : target_(target),
22 bit_index_(-1),
23 word_index_(0),
24 current_word_(target->data_[0]) {
25 ASSERT(target->data_length_ > 0);
26 Advance();
27 }
28 ~Iterator() {}
29
30 bool Done() const { return word_index_ >= target_->data_length_; }
31 void Advance();
32
33 intptr_t Current() const {
34 ASSERT(!Done());
35 return bit_index_;
36 }
37
38 private:
39 BitVector* target_;
40 intptr_t bit_index_;
41 intptr_t word_index_;
42 uword current_word_;
43
44 friend class BitVector;
45 };
46
47 BitVector(Zone* zone, intptr_t length)
48 : length_(length),
49 data_length_(SizeFor(length)),
50 data_(zone->Alloc<uword>(data_length_)) {
51 Clear();
52 }
53
54 void CopyFrom(const BitVector* other) {
55 Clear();
56 AddAll(other);
57 }
58
59 static intptr_t SizeFor(intptr_t length) {
60 return 1 + ((length - 1) / kBitsPerWord);
61 }
62
63 void Add(intptr_t i) {
64 ASSERT(i >= 0 && i < length());
65 data_[i / kBitsPerWord] |= (static_cast<uword>(1) << (i % kBitsPerWord));
66 }
67
68 void Remove(intptr_t i) {
69 ASSERT(i >= 0 && i < length());
70 data_[i / kBitsPerWord] &= ~(static_cast<uword>(1) << (i % kBitsPerWord));
71 }
72
73 void Set(intptr_t i, bool value) { value ? Add(i) : Remove(i); }
74
75 bool Equals(const BitVector& other) const;
76
77 // Add all elements that are in the bitvector from.
78 bool AddAll(const BitVector* from);
79
80 // Remove all elements that are in the bitvector from.
81 bool RemoveAll(const BitVector* from);
82
83 // From the bitvector gen add those elements that are not in the
84 // bitvector kill.
85 bool KillAndAdd(BitVector* kill, BitVector* gen);
86
87 void Intersect(const BitVector* other);
88
89 bool IsEmpty() const;
90
91 bool Contains(intptr_t i) const {
92 ASSERT(i >= 0 && i < length());
93 uword block = data_[i / kBitsPerWord];
94 return (block & (static_cast<uword>(1) << (i % kBitsPerWord))) != 0;
95 }
96
97 bool SubsetOf(const BitVector& other) {
98 ASSERT(length_ == other.length_);
99 for (intptr_t i = 0; i < data_length_; ++i) {
100 if ((data_[i] & other.data_[i]) != data_[i]) return false;
101 }
102 return true;
103 }
104
105 void Clear() {
106 for (intptr_t i = 0; i < data_length_; i++) {
107 data_[i] = 0;
108 }
109 }
110
111 void SetAll() {
112 for (intptr_t i = 0; i < data_length_; i++) {
113 data_[i] = static_cast<uword>(-1);
114 }
115 }
116
117 intptr_t length() const { return length_; }
118
119 void Print() const;
120
121 private:
122 intptr_t length_;
123 intptr_t data_length_;
124 uword* data_;
125
126 DISALLOW_COPY_AND_ASSIGN(BitVector);
127};
128
129} // namespace dart
130
131#endif // RUNTIME_VM_BIT_VECTOR_H_
132