1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_UTILS_BIT_VECTOR_H_ 6 #define V8_UTILS_BIT_VECTOR_H_ 7 8 #include "src/base/bits.h" 9 #include "src/utils/allocation.h" 10 #include "src/zone/zone.h" 11 12 namespace v8 { 13 namespace internal { 14 15 class V8_EXPORT_PRIVATE BitVector : public ZoneObject { 16 public: 17 union DataStorage { 18 uintptr_t* ptr_; // valid if data_length_ > 1 19 uintptr_t inline_; // valid if data_length_ == 1 20 DataStorage(uintptr_t value)21 DataStorage(uintptr_t value) : inline_(value) {} 22 }; 23 24 // Iterator for the elements of this BitVector. 25 class Iterator { 26 public: Iterator(BitVector * target)27 explicit Iterator(BitVector* target) 28 : target_(target), 29 current_index_(0), 30 current_value_(target->is_inline() ? target->data_.inline_ 31 : target->data_.ptr_[0]), 32 current_(-1) { 33 Advance(); 34 } 35 ~Iterator() = default; 36 Done()37 bool Done() const { return current_index_ >= target_->data_length_; } 38 Advance()39 V8_EXPORT_PRIVATE inline void Advance() { 40 current_++; 41 42 // Skip zeroed words. 43 while (current_value_ == 0) { 44 current_index_++; 45 if (Done()) return; 46 DCHECK(!target_->is_inline()); 47 current_value_ = target_->data_.ptr_[current_index_]; 48 current_ = current_index_ << kDataBitShift; 49 } 50 51 // Skip zeroed bits. 52 uintptr_t trailing_zeros = base::bits::CountTrailingZeros(current_value_); 53 current_ += trailing_zeros; 54 current_value_ >>= trailing_zeros; 55 56 // Get current_value ready for next advance. 57 current_value_ >>= 1; 58 } 59 Current()60 int Current() const { 61 DCHECK(!Done()); 62 return current_; 63 } 64 65 private: 66 BitVector* target_; 67 int current_index_; 68 uintptr_t current_value_; 69 int current_; 70 71 friend class BitVector; 72 }; 73 74 static const int kDataLengthForInline = 1; 75 static const int kDataBits = kBitsPerSystemPointer; 76 static const int kDataBitShift = kBitsPerSystemPointerLog2; 77 static const uintptr_t kOne = 1; // This saves some static_casts. 78 BitVector()79 BitVector() : length_(0), data_length_(kDataLengthForInline), data_(0) {} 80 BitVector(int length,Zone * zone)81 BitVector(int length, Zone* zone) 82 : length_(length), data_length_(SizeFor(length)), data_(0) { 83 DCHECK_LE(0, length); 84 if (!is_inline()) { 85 data_.ptr_ = zone->NewArray<uintptr_t>(data_length_); 86 Clear(); 87 } 88 // Otherwise, clearing is implicit 89 } 90 BitVector(const BitVector & other,Zone * zone)91 BitVector(const BitVector& other, Zone* zone) 92 : length_(other.length_), 93 data_length_(other.data_length_), 94 data_(other.data_.inline_) { 95 if (!is_inline()) { 96 data_.ptr_ = zone->NewArray<uintptr_t>(data_length_); 97 for (int i = 0; i < other.data_length_; i++) { 98 data_.ptr_[i] = other.data_.ptr_[i]; 99 } 100 } 101 } 102 SizeFor(int length)103 static int SizeFor(int length) { 104 if (length <= kDataBits) { 105 return kDataLengthForInline; 106 } 107 108 int data_length = 1 + ((length - 1) / kDataBits); 109 DCHECK_GT(data_length, kDataLengthForInline); 110 return data_length; 111 } 112 CopyFrom(const BitVector & other)113 void CopyFrom(const BitVector& other) { 114 DCHECK_LE(other.length(), length()); 115 CopyFrom(other.data_, other.data_length_); 116 } 117 Resize(int new_length,Zone * zone)118 void Resize(int new_length, Zone* zone) { 119 DCHECK_GT(new_length, length()); 120 int new_data_length = SizeFor(new_length); 121 if (new_data_length > data_length_) { 122 DataStorage old_data = data_; 123 int old_data_length = data_length_; 124 125 // Make sure the new data length is large enough to need allocation. 126 DCHECK_GT(new_data_length, kDataLengthForInline); 127 data_.ptr_ = zone->NewArray<uintptr_t>(new_data_length); 128 data_length_ = new_data_length; 129 CopyFrom(old_data, old_data_length); 130 } 131 length_ = new_length; 132 } 133 Contains(int i)134 bool Contains(int i) const { 135 DCHECK(i >= 0 && i < length()); 136 uintptr_t block = is_inline() ? data_.inline_ : data_.ptr_[i / kDataBits]; 137 return (block & (kOne << (i % kDataBits))) != 0; 138 } 139 Add(int i)140 void Add(int i) { 141 DCHECK(i >= 0 && i < length()); 142 if (is_inline()) { 143 data_.inline_ |= (kOne << i); 144 } else { 145 data_.ptr_[i / kDataBits] |= (kOne << (i % kDataBits)); 146 } 147 } 148 AddAll()149 void AddAll() { 150 // TODO(leszeks): This sets bits outside of the length of this bit-vector, 151 // which is observable if we resize it or copy from it. If this is a 152 // problem, we should clear the high bits either on add, or on resize/copy. 153 if (is_inline()) { 154 data_.inline_ = -1; 155 } else { 156 memset(data_.ptr_, -1, sizeof(uintptr_t) * data_length_); 157 } 158 } 159 Remove(int i)160 void Remove(int i) { 161 DCHECK(i >= 0 && i < length()); 162 if (is_inline()) { 163 data_.inline_ &= ~(kOne << i); 164 } else { 165 data_.ptr_[i / kDataBits] &= ~(kOne << (i % kDataBits)); 166 } 167 } 168 Union(const BitVector & other)169 void Union(const BitVector& other) { 170 DCHECK(other.length() == length()); 171 if (is_inline()) { 172 DCHECK(other.is_inline()); 173 data_.inline_ |= other.data_.inline_; 174 } else { 175 for (int i = 0; i < data_length_; i++) { 176 data_.ptr_[i] |= other.data_.ptr_[i]; 177 } 178 } 179 } 180 UnionIsChanged(const BitVector & other)181 bool UnionIsChanged(const BitVector& other) { 182 DCHECK(other.length() == length()); 183 if (is_inline()) { 184 DCHECK(other.is_inline()); 185 uintptr_t old_data = data_.inline_; 186 data_.inline_ |= other.data_.inline_; 187 return data_.inline_ != old_data; 188 } else { 189 bool changed = false; 190 for (int i = 0; i < data_length_; i++) { 191 uintptr_t old_data = data_.ptr_[i]; 192 data_.ptr_[i] |= other.data_.ptr_[i]; 193 if (data_.ptr_[i] != old_data) changed = true; 194 } 195 return changed; 196 } 197 } 198 Intersect(const BitVector & other)199 void Intersect(const BitVector& other) { 200 DCHECK(other.length() == length()); 201 if (is_inline()) { 202 DCHECK(other.is_inline()); 203 data_.inline_ &= other.data_.inline_; 204 } else { 205 for (int i = 0; i < data_length_; i++) { 206 data_.ptr_[i] &= other.data_.ptr_[i]; 207 } 208 } 209 } 210 IntersectIsChanged(const BitVector & other)211 bool IntersectIsChanged(const BitVector& other) { 212 DCHECK(other.length() == length()); 213 if (is_inline()) { 214 DCHECK(other.is_inline()); 215 uintptr_t old_data = data_.inline_; 216 data_.inline_ &= other.data_.inline_; 217 return data_.inline_ != old_data; 218 } else { 219 bool changed = false; 220 for (int i = 0; i < data_length_; i++) { 221 uintptr_t old_data = data_.ptr_[i]; 222 data_.ptr_[i] &= other.data_.ptr_[i]; 223 if (data_.ptr_[i] != old_data) changed = true; 224 } 225 return changed; 226 } 227 } 228 Subtract(const BitVector & other)229 void Subtract(const BitVector& other) { 230 DCHECK(other.length() == length()); 231 if (is_inline()) { 232 DCHECK(other.is_inline()); 233 data_.inline_ &= ~other.data_.inline_; 234 } else { 235 for (int i = 0; i < data_length_; i++) { 236 data_.ptr_[i] &= ~other.data_.ptr_[i]; 237 } 238 } 239 } 240 Clear()241 void Clear() { 242 if (is_inline()) { 243 data_.inline_ = 0; 244 } else { 245 for (int i = 0; i < data_length_; i++) { 246 data_.ptr_[i] = 0; 247 } 248 } 249 } 250 IsEmpty()251 bool IsEmpty() const { 252 if (is_inline()) { 253 return data_.inline_ == 0; 254 } else { 255 for (int i = 0; i < data_length_; i++) { 256 if (data_.ptr_[i] != 0) return false; 257 } 258 return true; 259 } 260 } 261 Equals(const BitVector & other)262 bool Equals(const BitVector& other) const { 263 DCHECK(other.length() == length()); 264 if (is_inline()) { 265 DCHECK(other.is_inline()); 266 return data_.inline_ == other.data_.inline_; 267 } else { 268 for (int i = 0; i < data_length_; i++) { 269 if (data_.ptr_[i] != other.data_.ptr_[i]) return false; 270 } 271 return true; 272 } 273 } 274 275 int Count() const; 276 length()277 int length() const { return length_; } 278 279 #ifdef DEBUG 280 void Print() const; 281 #endif 282 283 MOVE_ONLY_NO_DEFAULT_CONSTRUCTOR(BitVector); 284 285 private: 286 int length_; 287 int data_length_; 288 DataStorage data_; 289 is_inline()290 bool is_inline() const { return data_length_ == kDataLengthForInline; } 291 CopyFrom(DataStorage other_data,int other_data_length)292 void CopyFrom(DataStorage other_data, int other_data_length) { 293 DCHECK_LE(other_data_length, data_length_); 294 295 if (is_inline()) { 296 DCHECK_EQ(other_data_length, kDataLengthForInline); 297 data_.inline_ = other_data.inline_; 298 } else if (other_data_length == kDataLengthForInline) { 299 data_.ptr_[0] = other_data.inline_; 300 for (int i = 1; i < data_length_; i++) { 301 data_.ptr_[i] = 0; 302 } 303 } else { 304 for (int i = 0; i < other_data_length; i++) { 305 data_.ptr_[i] = other_data.ptr_[i]; 306 } 307 for (int i = other_data_length; i < data_length_; i++) { 308 data_.ptr_[i] = 0; 309 } 310 } 311 } 312 }; 313 314 class GrowableBitVector { 315 public: 316 class Iterator { 317 public: Iterator(const GrowableBitVector * target,Zone * zone)318 Iterator(const GrowableBitVector* target, Zone* zone) 319 : it_(target->bits_ == nullptr ? zone->New<BitVector>(1, zone) 320 : target->bits_) {} Done()321 bool Done() const { return it_.Done(); } Advance()322 void Advance() { it_.Advance(); } Current()323 int Current() const { return it_.Current(); } 324 325 private: 326 BitVector::Iterator it_; 327 }; 328 GrowableBitVector()329 GrowableBitVector() : bits_(nullptr) {} GrowableBitVector(int length,Zone * zone)330 GrowableBitVector(int length, Zone* zone) 331 : bits_(zone->New<BitVector>(length, zone)) {} 332 Contains(int value)333 bool Contains(int value) const { 334 if (!InBitsRange(value)) return false; 335 return bits_->Contains(value); 336 } 337 Add(int value,Zone * zone)338 void Add(int value, Zone* zone) { 339 EnsureCapacity(value, zone); 340 bits_->Add(value); 341 } 342 Union(const GrowableBitVector & other,Zone * zone)343 void Union(const GrowableBitVector& other, Zone* zone) { 344 for (Iterator it(&other, zone); !it.Done(); it.Advance()) { 345 Add(it.Current(), zone); 346 } 347 } 348 Clear()349 void Clear() { 350 if (bits_ != nullptr) bits_->Clear(); 351 } 352 353 private: 354 static const int kInitialLength = 1024; 355 InBitsRange(int value)356 bool InBitsRange(int value) const { 357 return bits_ != nullptr && bits_->length() > value; 358 } 359 EnsureCapacity(int value,Zone * zone)360 void EnsureCapacity(int value, Zone* zone) { 361 if (InBitsRange(value)) return; 362 int new_length = bits_ == nullptr ? kInitialLength : bits_->length(); 363 while (new_length <= value) new_length *= 2; 364 365 if (bits_ == nullptr) { 366 bits_ = zone->New<BitVector>(new_length, zone); 367 } else { 368 bits_->Resize(new_length, zone); 369 } 370 } 371 372 BitVector* bits_; 373 }; 374 375 } // namespace internal 376 } // namespace v8 377 378 #endif // V8_UTILS_BIT_VECTOR_H_ 379