1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_LIBARTBASE_BASE_BIT_VECTOR_INL_H_ 18 #define ART_LIBARTBASE_BASE_BIT_VECTOR_INL_H_ 19 20 #include "bit_vector.h" 21 22 #include <android-base/logging.h> 23 24 #include "base/bit_utils.h" 25 26 namespace art { 27 28 inline bool BitVector::IndexIterator::operator==(const IndexIterator& other) const { 29 DCHECK(bit_storage_ == other.bit_storage_); 30 DCHECK_EQ(storage_size_, other.storage_size_); 31 return bit_index_ == other.bit_index_; 32 } 33 34 inline uint32_t BitVector::IndexIterator::operator*() const { 35 DCHECK_LT(bit_index_, BitSize()); 36 return bit_index_; 37 } 38 39 inline BitVector::IndexIterator& BitVector::IndexIterator::operator++() { 40 DCHECK_LT(bit_index_, BitSize()); 41 bit_index_ = FindIndex(bit_index_ + 1u); 42 return *this; 43 } 44 45 inline BitVector::IndexIterator BitVector::IndexIterator::operator++(int) { 46 IndexIterator result(*this); 47 ++*this; 48 return result; 49 } 50 51 inline uint32_t BitVector::IndexIterator::FindIndex(uint32_t start_index) const { 52 DCHECK_LE(start_index, BitSize()); 53 uint32_t word_index = start_index / kWordBits; 54 if (UNLIKELY(word_index == storage_size_)) { 55 return start_index; 56 } 57 uint32_t word = bit_storage_[word_index]; 58 // Mask out any bits in the first word we've already considered. 59 word &= static_cast<uint32_t>(-1) << (start_index & 0x1f); 60 while (word == 0u) { 61 ++word_index; 62 if (UNLIKELY(word_index == storage_size_)) { 63 return BitSize(); 64 } 65 word = bit_storage_[word_index]; 66 } 67 return word_index * 32u + CTZ(word); 68 } 69 70 inline BitVector::IndexIterator::IndexIterator(const BitVector* bit_vector, begin_tag) 71 : bit_storage_(bit_vector->GetRawStorage()), 72 storage_size_(bit_vector->storage_size_), 73 bit_index_(FindIndex(0u)) { } 74 75 inline BitVector::IndexIterator::IndexIterator(const BitVector* bit_vector, end_tag) 76 : bit_storage_(bit_vector->GetRawStorage()), 77 storage_size_(bit_vector->storage_size_), 78 bit_index_(BitSize()) { } 79 80 inline BitVector::IndexIterator BitVector::IndexContainer::begin() const { 81 return IndexIterator(bit_vector_, IndexIterator::begin_tag()); 82 } 83 84 inline BitVector::IndexIterator BitVector::IndexContainer::end() const { 85 return IndexIterator(bit_vector_, IndexIterator::end_tag()); 86 } 87 88 inline void BitVector::ClearAllBits() { 89 memset(storage_, 0, storage_size_ * kWordBytes); 90 } 91 92 inline bool BitVector::Equal(const BitVector* src) const { 93 return (storage_size_ == src->GetStorageSize()) && 94 (expandable_ == src->IsExpandable()) && 95 (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0); 96 } 97 98 } // namespace art 99 100 #endif // ART_LIBARTBASE_BASE_BIT_VECTOR_INL_H_ 101
