1413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom/* 2413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * Copyright (C) 2011 The Android Open Source Project 3413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * 4413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * Licensed under the Apache License, Version 2.0 (the "License"); 5413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * you may not use this file except in compliance with the License. 6413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * You may obtain a copy of the License at 7413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * 8413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * http://www.apache.org/licenses/LICENSE-2.0 9413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * 10413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * Unless required by applicable law or agreed to in writing, software 11413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * distributed under the License is distributed on an "AS IS" BASIS, 12413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * See the License for the specific language governing permissions and 14413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * limitations under the License. 15413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom */ 16413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 17413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom#include "bit_vector.h" 18413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 195a2e4ccabf4cda7050c63685be23339eac8779dfIan Rogers#include <limits> 20c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers#include <sstream> 21c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers 22e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers#include "allocator.h" 23e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers#include "bit_vector-inl.h" 24e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 25413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstromnamespace art { 26413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 27067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas GampeBitVector::BitVector(bool expandable, 28413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom Allocator* allocator, 29413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom uint32_t storage_size, 30413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom uint32_t* storage) 31e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers : storage_(storage), 32413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom storage_size_(storage_size), 33e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers allocator_(allocator), 34e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers expandable_(expandable) { 35067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe DCHECK(storage_ != nullptr); 36067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe 37575e78c41ece0dec969d31f46be563d4eb7ae43bAndreas Gampe static_assert(sizeof(*storage_) == kWordBytes, "word bytes"); 38575e78c41ece0dec969d31f46be563d4eb7ae43bAndreas Gampe static_assert(sizeof(*storage_) * 8u == kWordBits, "word bits"); 39067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe} 40067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe 41067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas GampeBitVector::BitVector(uint32_t start_bits, 42067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe bool expandable, 43067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe Allocator* allocator) 44067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe : BitVector(expandable, 45067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe allocator, 46067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe BitsToWords(start_bits), 47067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe static_cast<uint32_t*>(allocator->Alloc(BitsToWords(start_bits) * kWordBytes))) { 48067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe} 49067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe 50067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe 51067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas GampeBitVector::BitVector(const BitVector& src, 52067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe bool expandable, 53067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe Allocator* allocator) 54067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe : BitVector(expandable, 55067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe allocator, 56067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe src.storage_size_, 57067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe static_cast<uint32_t*>(allocator->Alloc(src.storage_size_ * kWordBytes))) { 58067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe // Direct memcpy would be faster, but this should be fine too and is cleaner. 59067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe Copy(&src); 60413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} 61413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 62413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian CarlstromBitVector::~BitVector() { 63413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom allocator_->Free(storage_); 64413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} 65413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 66e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogersbool BitVector::SameBitsSet(const BitVector *src) const { 67ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler int our_highest = GetHighestBitSet(); 68ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler int src_highest = src->GetHighestBitSet(); 69ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 70ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // If the highest bit set is different, we are different. 71ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler if (our_highest != src_highest) { 72b5c9b4008760c9042061490f22aaff990ed04c9aJean Christophe Beyler return false; 73ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 74ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 75ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // If the highest bit set is -1, both are cleared, we are the same. 76ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // If the highest bit set is 0, both have a unique bit set, we are the same. 77b5c9b4008760c9042061490f22aaff990ed04c9aJean Christophe Beyler if (our_highest <= 0) { 78ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler return true; 79ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 80ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 81b5c9b4008760c9042061490f22aaff990ed04c9aJean Christophe Beyler // Get the highest bit set's cell's index 82b5c9b4008760c9042061490f22aaff990ed04c9aJean Christophe Beyler // No need of highest + 1 here because it can't be 0 so BitsToWords will work here. 83b5c9b4008760c9042061490f22aaff990ed04c9aJean Christophe Beyler int our_highest_index = BitsToWords(our_highest); 84ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 85ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // This memcmp is enough: we know that the highest bit set is the same for both: 86ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less. 87ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index, 88ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // they are automatically at 0. 89a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko return (memcmp(storage_, src->GetRawStorage(), our_highest_index * kWordBytes) == 0); 90ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler} 91ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 927d275379bf490a87805852129e3fe2e8afe961e7David Brazdilbool BitVector::IsSubsetOf(const BitVector *other) const { 937d275379bf490a87805852129e3fe2e8afe961e7David Brazdil int this_highest = GetHighestBitSet(); 947d275379bf490a87805852129e3fe2e8afe961e7David Brazdil int other_highest = other->GetHighestBitSet(); 957d275379bf490a87805852129e3fe2e8afe961e7David Brazdil 967d275379bf490a87805852129e3fe2e8afe961e7David Brazdil // If the highest bit set is -1, this is empty and a trivial subset. 977d275379bf490a87805852129e3fe2e8afe961e7David Brazdil if (this_highest < 0) { 987d275379bf490a87805852129e3fe2e8afe961e7David Brazdil return true; 997d275379bf490a87805852129e3fe2e8afe961e7David Brazdil } 1007d275379bf490a87805852129e3fe2e8afe961e7David Brazdil 1017d275379bf490a87805852129e3fe2e8afe961e7David Brazdil // If the highest bit set is higher, this cannot be a subset. 1027d275379bf490a87805852129e3fe2e8afe961e7David Brazdil if (this_highest > other_highest) { 1037d275379bf490a87805852129e3fe2e8afe961e7David Brazdil return false; 1047d275379bf490a87805852129e3fe2e8afe961e7David Brazdil } 1057d275379bf490a87805852129e3fe2e8afe961e7David Brazdil 1067d275379bf490a87805852129e3fe2e8afe961e7David Brazdil // Compare each 32-bit word. 1077d275379bf490a87805852129e3fe2e8afe961e7David Brazdil size_t this_highest_index = BitsToWords(this_highest + 1); 1087d275379bf490a87805852129e3fe2e8afe961e7David Brazdil for (size_t i = 0; i < this_highest_index; ++i) { 1097d275379bf490a87805852129e3fe2e8afe961e7David Brazdil uint32_t this_storage = storage_[i]; 1107d275379bf490a87805852129e3fe2e8afe961e7David Brazdil uint32_t other_storage = other->storage_[i]; 1117d275379bf490a87805852129e3fe2e8afe961e7David Brazdil if ((this_storage | other_storage) != other_storage) { 1127d275379bf490a87805852129e3fe2e8afe961e7David Brazdil return false; 1137d275379bf490a87805852129e3fe2e8afe961e7David Brazdil } 1147d275379bf490a87805852129e3fe2e8afe961e7David Brazdil } 1157d275379bf490a87805852129e3fe2e8afe961e7David Brazdil return true; 1167d275379bf490a87805852129e3fe2e8afe961e7David Brazdil} 1177d275379bf490a87805852129e3fe2e8afe961e7David Brazdil 118413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstromvoid BitVector::Intersect(const BitVector* src) { 119ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler uint32_t src_storage_size = src->storage_size_; 120ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 121ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Get the minimum size between us and source. 122ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler uint32_t min_size = (storage_size_ < src_storage_size) ? storage_size_ : src_storage_size; 123ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 124ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler uint32_t idx; 125ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler for (idx = 0; idx < min_size; idx++) { 126413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom storage_[idx] &= src->GetRawStorageWord(idx); 127413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom } 128ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 129ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Now, due to this being an intersection, there are two possibilities: 130ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // - Either src was larger than us: we don't care, all upper bits would thus be 0. 131ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // - Either we are larger than src: we don't care, all upper bits would have been 0 too. 132ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // So all we need to do is set all remaining bits to 0. 133ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler for (; idx < storage_size_; idx++) { 134ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler storage_[idx] = 0; 135ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 136413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} 137413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 138804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffraybool BitVector::Union(const BitVector* src) { 1395afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler // Get the highest bit to determine how much we need to expand. 1405afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler int highest_bit = src->GetHighestBitSet(); 141804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray bool changed = false; 1425afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler 1435afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler // If src has no bit set, we are done: there is no need for a union with src. 1445afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler if (highest_bit == -1) { 145804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray return changed; 1465afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler } 147ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 1485afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler // Update src_size to how many cells we actually care about: where the bit is + 1. 1495afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler uint32_t src_size = BitsToWords(highest_bit + 1); 150ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 151ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Is the storage size smaller than src's? 152ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler if (storage_size_ < src_size) { 153804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray changed = true; 154804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 155e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers EnsureSize(highest_bit); 156ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 157ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Paranoid: storage size should be big enough to hold this bit now. 158a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits); 159ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 160ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 1615afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler for (uint32_t idx = 0; idx < src_size; idx++) { 162804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t existing = storage_[idx]; 163804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t update = existing | src->GetRawStorageWord(idx); 164804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray if (existing != update) { 165804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray changed = true; 166804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray storage_[idx] = update; 167804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 168413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom } 169804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray return changed; 170804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray} 171804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 172804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffraybool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) { 173804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Get the highest bit to determine how much we need to expand. 174804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray int highest_bit = union_with->GetHighestBitSet(); 175804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray bool changed = false; 176804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 177804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // If src has no bit set, we are done: there is no need for a union with src. 178804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray if (highest_bit == -1) { 179804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray return changed; 180804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 181804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 182804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Update union_with_size to how many cells we actually care about: where the bit is + 1. 183804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t union_with_size = BitsToWords(highest_bit + 1); 184804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 185804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Is the storage size smaller than src's? 186804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray if (storage_size_ < union_with_size) { 187b556761d14e8dd0d41f1cc0f7d19726fe3497e8fNicolas Geoffray EnsureSize(highest_bit); 188804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 189804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // Paranoid: storage size should be big enough to hold this bit now. 190a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits); 191804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 192804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 193804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t not_in_size = not_in->GetStorageSize(); 194804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 195804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t idx = 0; 196804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray for (; idx < std::min(not_in_size, union_with_size); idx++) { 197804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t existing = storage_[idx]; 198804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t update = existing | 199804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx)); 200804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray if (existing != update) { 201804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray changed = true; 202804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray storage_[idx] = update; 203804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 204804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 205804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray 206804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray for (; idx < union_with_size; idx++) { 207804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t existing = storage_[idx]; 208804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray uint32_t update = existing | union_with->GetRawStorageWord(idx); 209804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray if (existing != update) { 210804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray changed = true; 211804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray storage_[idx] = update; 212804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 213804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray } 214804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray return changed; 215413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} 216413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 217ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beylervoid BitVector::Subtract(const BitVector *src) { 218e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t src_size = src->storage_size_; 219ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 220e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // We only need to operate on bytes up to the smaller of the sizes of the two operands. 221e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers unsigned int min_size = (storage_size_ > src_size) ? src_size : storage_size_; 222ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 223e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Difference until max, we know both accept it: 224e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // There is no need to do more: 225e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // If we are bigger than src, the upper bits are unchanged. 226e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // If we are smaller than src, the non-existant upper bits are 0 and thus can't get subtracted. 227e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers for (uint32_t idx = 0; idx < min_size; idx++) { 228e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers storage_[idx] &= (~(src->GetRawStorageWord(idx))); 229e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 230ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler} 231ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 232ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstromuint32_t BitVector::NumSetBits() const { 233ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom uint32_t count = 0; 234ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom for (uint32_t word = 0; word < storage_size_; word++) { 2358194963098247be6bca9cc4a54dbfa65c73e8cccVladimir Marko count += POPCOUNT(storage_[word]); 236ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom } 237ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom return count; 238ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom} 239413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 240d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Markouint32_t BitVector::NumSetBits(uint32_t end) const { 241a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko DCHECK_LE(end, storage_size_ * kWordBits); 242d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko return NumSetBits(storage_, end); 243413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} 244413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 245ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstromvoid BitVector::SetInitialBits(uint32_t num_bits) { 246ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // If num_bits is 0, clear everything. 247ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler if (num_bits == 0) { 248ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler ClearAllBits(); 249ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler return; 250ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 251ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 252ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Set the highest bit we want to set to get the BitVector allocated if need be. 253ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler SetBit(num_bits - 1); 254ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 255ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom uint32_t idx; 256ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // We can set every storage element with -1. 257e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers for (idx = 0; idx < WordIndex(num_bits); idx++) { 2585a2e4ccabf4cda7050c63685be23339eac8779dfIan Rogers storage_[idx] = std::numeric_limits<uint32_t>::max(); 259413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom } 260ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 261ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Handle the potentially last few bits. 262ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom uint32_t rem_num_bits = num_bits & 0x1f; 263ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler if (rem_num_bits != 0) { 2645a2e4ccabf4cda7050c63685be23339eac8779dfIan Rogers storage_[idx] = (1U << rem_num_bits) - 1; 2654812d436ebf538043a7827253b2e940a52a43fcbVladimir Marko ++idx; 266413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom } 267ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 268ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Now set the upper ones to 0. 269ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler for (; idx < storage_size_; idx++) { 270ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler storage_[idx] = 0; 271ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 272ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler} 273ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 274ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beylerint BitVector::GetHighestBitSet() const { 275ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler unsigned int max = storage_size_; 276ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler for (int idx = max - 1; idx >= 0; idx--) { 277ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // If not 0, we have more work: check the bits. 278ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler uint32_t value = storage_[idx]; 279ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 280ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler if (value != 0) { 281e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Return highest bit set in value plus bits from previous storage indexes. 282e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return 31 - CLZ(value) + (idx * kWordBits); 283ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 284ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 285ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 286ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // All zero, therefore return -1. 287ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler return -1; 288ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler} 289ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 290ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beylervoid BitVector::Copy(const BitVector *src) { 291ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Get highest bit set, we only need to copy till then. 292ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler int highest_bit = src->GetHighestBitSet(); 293ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 294ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // If nothing is set, clear everything. 295ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler if (highest_bit == -1) { 296ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler ClearAllBits(); 297ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler return; 298ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 299ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 300ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Set upper bit to ensure right size before copy. 301ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler SetBit(highest_bit); 302ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 303ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Now set until highest bit's storage. 304a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko uint32_t size = 1 + (highest_bit / kWordBits); 305a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko memcpy(storage_, src->GetRawStorage(), kWordBytes * size); 306ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 307ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler // Set upper bits to 0. 308ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler uint32_t left = storage_size_ - size; 309ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 310ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler if (left > 0) { 311a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko memset(storage_ + size, 0, kWordBytes * left); 312ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler } 313413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} 314413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 315d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Markouint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) { 316e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t word_end = WordIndex(end); 317d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko uint32_t partial_word_bits = end & 0x1f; 318d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko 319d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko uint32_t count = 0u; 320d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko for (uint32_t word = 0u; word < word_end; word++) { 3218194963098247be6bca9cc4a54dbfa65c73e8cccVladimir Marko count += POPCOUNT(storage[word]); 322d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko } 323d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko if (partial_word_bits != 0u) { 3248194963098247be6bca9cc4a54dbfa65c73e8cccVladimir Marko count += POPCOUNT(storage[word_end] & ~(0xffffffffu << partial_word_bits)); 325d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko } 326d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko return count; 327d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko} 328d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko 329622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffrayvoid BitVector::Dump(std::ostream& os, const char *prefix) const { 3305afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler std::ostringstream buffer; 331520f37bb5c34c5d86ad0091cb84a84c163a2fa9cJean Christophe Beyler DumpHelper(prefix, buffer); 332804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray os << buffer.str() << std::endl; 3335afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler} 3345afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler 335520f37bb5c34c5d86ad0091cb84a84c163a2fa9cJean Christophe Beylervoid BitVector::DumpHelper(const char* prefix, std::ostringstream& buffer) const { 3365afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler // Initialize it. 3375afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler if (prefix != nullptr) { 3385afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler buffer << prefix; 3395afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler } 3405afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler 341804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray buffer << '('; 342014d77a2107fec8ba978a7428fd4d04e0bf8e168Jean Christophe Beyler for (size_t i = 0; i < storage_size_ * kWordBits; i++) { 343804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray buffer << IsBitSet(i); 3445afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler } 345804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray buffer << ')'; 3465afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler} 3475afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler 348e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogersvoid BitVector::EnsureSize(uint32_t idx) { 349e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers if (idx >= storage_size_ * kWordBits) { 350e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << idx; 351e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 352e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers /* Round up to word boundaries for "idx+1" bits */ 353e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t new_size = BitsToWords(idx + 1); 354e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers DCHECK_GT(new_size, storage_size_); 355e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t *new_storage = 356e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers static_cast<uint32_t*>(allocator_->Alloc(new_size * kWordBytes)); 357e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers memcpy(new_storage, storage_, storage_size_ * kWordBytes); 358e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Zero out the new storage words. 359e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * kWordBytes); 360dc8aa69496ea43f0a60f1f527822a90f6c3d6d03Andreas Gampe // TODO: collect stats on space wasted because of resize. 361dc8aa69496ea43f0a60f1f527822a90f6c3d6d03Andreas Gampe 362dc8aa69496ea43f0a60f1f527822a90f6c3d6d03Andreas Gampe // Free old storage. 363dc8aa69496ea43f0a60f1f527822a90f6c3d6d03Andreas Gampe allocator_->Free(storage_); 364dc8aa69496ea43f0a60f1f527822a90f6c3d6d03Andreas Gampe 365dc8aa69496ea43f0a60f1f527822a90f6c3d6d03Andreas Gampe // Set fields. 366e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers storage_ = new_storage; 367e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers storage_size_ = new_size; 368e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 369e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers} 370e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 371067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas GampeAllocator* BitVector::GetAllocator() const { 372067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe return allocator_; 373067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe} 374067f1ed7816cf4eb5d6258ca31b387ddb2073ab7Andreas Gampe 375413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} // namespace art 376