1193323Sed//===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector -*- C++ -*- ===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the SparseBitVector class. See the doxygen comment for 11193323Sed// SparseBitVector for more details on the algorithm used. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef LLVM_ADT_SPARSEBITVECTOR_H 16193323Sed#define LLVM_ADT_SPARSEBITVECTOR_H 17193323Sed 18198090Srdivacky#include "llvm/ADT/ilist.h" 19198090Srdivacky#include "llvm/ADT/ilist_node.h" 20218893Sdim#include "llvm/Support/DataTypes.h" 21234353Sdim#include "llvm/Support/ErrorHandling.h" 22198090Srdivacky#include "llvm/Support/MathExtras.h" 23198090Srdivacky#include "llvm/Support/raw_ostream.h" 24193323Sed#include <cassert> 25193323Sed#include <climits> 26193323Sed 27193323Sednamespace llvm { 28193323Sed 29193323Sed/// SparseBitVector is an implementation of a bitvector that is sparse by only 30193323Sed/// storing the elements that have non-zero bits set. In order to make this 31193323Sed/// fast for the most common cases, SparseBitVector is implemented as a linked 32193323Sed/// list of SparseBitVectorElements. We maintain a pointer to the last 33193323Sed/// SparseBitVectorElement accessed (in the form of a list iterator), in order 34193323Sed/// to make multiple in-order test/set constant time after the first one is 35193323Sed/// executed. Note that using vectors to store SparseBitVectorElement's does 36193323Sed/// not work out very well because it causes insertion in the middle to take 37193323Sed/// enormous amounts of time with a large amount of bits. Other structures that 38193323Sed/// have better worst cases for insertion in the middle (various balanced trees, 39193323Sed/// etc) do not perform as well in practice as a linked list with this iterator 40193323Sed/// kept up to date. They are also significantly more memory intensive. 41193323Sed 42193323Sed 43193323Sedtemplate <unsigned ElementSize = 128> 44193323Sedstruct SparseBitVectorElement 45198090Srdivacky : public ilist_node<SparseBitVectorElement<ElementSize> > { 46193323Sedpublic: 47193323Sed typedef unsigned long BitWord; 48193323Sed enum { 49193323Sed BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT, 50193323Sed BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, 51193323Sed BITS_PER_ELEMENT = ElementSize 52193323Sed }; 53193323Sed 54193323Sedprivate: 55193323Sed // Index of Element in terms of where first bit starts. 56193323Sed unsigned ElementIndex; 57193323Sed BitWord Bits[BITWORDS_PER_ELEMENT]; 58193323Sed // Needed for sentinels 59193323Sed friend struct ilist_sentinel_traits<SparseBitVectorElement>; 60193323Sed SparseBitVectorElement() { 61193323Sed ElementIndex = ~0U; 62193323Sed memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 63193323Sed } 64193323Sed 65193323Sedpublic: 66193323Sed explicit SparseBitVectorElement(unsigned Idx) { 67193323Sed ElementIndex = Idx; 68193323Sed memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 69193323Sed } 70193323Sed 71193323Sed // Comparison. 72193323Sed bool operator==(const SparseBitVectorElement &RHS) const { 73193323Sed if (ElementIndex != RHS.ElementIndex) 74193323Sed return false; 75193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 76193323Sed if (Bits[i] != RHS.Bits[i]) 77193323Sed return false; 78193323Sed return true; 79193323Sed } 80193323Sed 81193323Sed bool operator!=(const SparseBitVectorElement &RHS) const { 82193323Sed return !(*this == RHS); 83193323Sed } 84193323Sed 85193323Sed // Return the bits that make up word Idx in our element. 86193323Sed BitWord word(unsigned Idx) const { 87193323Sed assert (Idx < BITWORDS_PER_ELEMENT); 88193323Sed return Bits[Idx]; 89193323Sed } 90193323Sed 91193323Sed unsigned index() const { 92193323Sed return ElementIndex; 93193323Sed } 94193323Sed 95193323Sed bool empty() const { 96193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 97193323Sed if (Bits[i]) 98193323Sed return false; 99193323Sed return true; 100193323Sed } 101193323Sed 102193323Sed void set(unsigned Idx) { 103193323Sed Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 104193323Sed } 105193323Sed 106193323Sed bool test_and_set (unsigned Idx) { 107193323Sed bool old = test(Idx); 108193323Sed if (!old) { 109193323Sed set(Idx); 110193323Sed return true; 111193323Sed } 112193323Sed return false; 113193323Sed } 114193323Sed 115193323Sed void reset(unsigned Idx) { 116193323Sed Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 117193323Sed } 118193323Sed 119193323Sed bool test(unsigned Idx) const { 120193323Sed return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE)); 121193323Sed } 122193323Sed 123193323Sed unsigned count() const { 124193323Sed unsigned NumBits = 0; 125193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 126193323Sed if (sizeof(BitWord) == 4) 127193323Sed NumBits += CountPopulation_32(Bits[i]); 128193323Sed else if (sizeof(BitWord) == 8) 129193323Sed NumBits += CountPopulation_64(Bits[i]); 130193323Sed else 131234353Sdim llvm_unreachable("Unsupported!"); 132193323Sed return NumBits; 133193323Sed } 134193323Sed 135193323Sed /// find_first - Returns the index of the first set bit. 136193323Sed int find_first() const { 137193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 138193323Sed if (Bits[i] != 0) { 139193323Sed if (sizeof(BitWord) == 4) 140193323Sed return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 141234353Sdim if (sizeof(BitWord) == 8) 142193323Sed return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 143234353Sdim llvm_unreachable("Unsupported!"); 144193323Sed } 145234353Sdim llvm_unreachable("Illegal empty element"); 146193323Sed } 147193323Sed 148193323Sed /// find_next - Returns the index of the next set bit starting from the 149193323Sed /// "Curr" bit. Returns -1 if the next set bit is not found. 150193323Sed int find_next(unsigned Curr) const { 151193323Sed if (Curr >= BITS_PER_ELEMENT) 152193323Sed return -1; 153193323Sed 154193323Sed unsigned WordPos = Curr / BITWORD_SIZE; 155193323Sed unsigned BitPos = Curr % BITWORD_SIZE; 156193323Sed BitWord Copy = Bits[WordPos]; 157193323Sed assert (WordPos <= BITWORDS_PER_ELEMENT 158193323Sed && "Word Position outside of element"); 159193323Sed 160193323Sed // Mask off previous bits. 161243830Sdim Copy &= ~0UL << BitPos; 162193323Sed 163193323Sed if (Copy != 0) { 164193323Sed if (sizeof(BitWord) == 4) 165193323Sed return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy); 166234353Sdim if (sizeof(BitWord) == 8) 167193323Sed return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 168234353Sdim llvm_unreachable("Unsupported!"); 169193323Sed } 170193323Sed 171193323Sed // Check subsequent words. 172193323Sed for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) 173193323Sed if (Bits[i] != 0) { 174193323Sed if (sizeof(BitWord) == 4) 175193323Sed return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 176234353Sdim if (sizeof(BitWord) == 8) 177193323Sed return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 178234353Sdim llvm_unreachable("Unsupported!"); 179193323Sed } 180193323Sed return -1; 181193323Sed } 182193323Sed 183193323Sed // Union this element with RHS and return true if this one changed. 184193323Sed bool unionWith(const SparseBitVectorElement &RHS) { 185193323Sed bool changed = false; 186193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 187193323Sed BitWord old = changed ? 0 : Bits[i]; 188193323Sed 189193323Sed Bits[i] |= RHS.Bits[i]; 190193323Sed if (!changed && old != Bits[i]) 191193323Sed changed = true; 192193323Sed } 193193323Sed return changed; 194193323Sed } 195193323Sed 196193323Sed // Return true if we have any bits in common with RHS 197193323Sed bool intersects(const SparseBitVectorElement &RHS) const { 198193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 199193323Sed if (RHS.Bits[i] & Bits[i]) 200193323Sed return true; 201193323Sed } 202193323Sed return false; 203193323Sed } 204193323Sed 205193323Sed // Intersect this Element with RHS and return true if this one changed. 206193323Sed // BecameZero is set to true if this element became all-zero bits. 207193323Sed bool intersectWith(const SparseBitVectorElement &RHS, 208193323Sed bool &BecameZero) { 209193323Sed bool changed = false; 210193323Sed bool allzero = true; 211193323Sed 212193323Sed BecameZero = false; 213193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 214193323Sed BitWord old = changed ? 0 : Bits[i]; 215193323Sed 216193323Sed Bits[i] &= RHS.Bits[i]; 217193323Sed if (Bits[i] != 0) 218193323Sed allzero = false; 219193323Sed 220193323Sed if (!changed && old != Bits[i]) 221193323Sed changed = true; 222193323Sed } 223193323Sed BecameZero = allzero; 224193323Sed return changed; 225193323Sed } 226193323Sed // Intersect this Element with the complement of RHS and return true if this 227193323Sed // one changed. BecameZero is set to true if this element became all-zero 228193323Sed // bits. 229193323Sed bool intersectWithComplement(const SparseBitVectorElement &RHS, 230193323Sed bool &BecameZero) { 231193323Sed bool changed = false; 232193323Sed bool allzero = true; 233193323Sed 234193323Sed BecameZero = false; 235193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 236193323Sed BitWord old = changed ? 0 : Bits[i]; 237193323Sed 238193323Sed Bits[i] &= ~RHS.Bits[i]; 239193323Sed if (Bits[i] != 0) 240193323Sed allzero = false; 241193323Sed 242193323Sed if (!changed && old != Bits[i]) 243193323Sed changed = true; 244193323Sed } 245193323Sed BecameZero = allzero; 246193323Sed return changed; 247193323Sed } 248193323Sed // Three argument version of intersectWithComplement that intersects 249193323Sed // RHS1 & ~RHS2 into this element 250193323Sed void intersectWithComplement(const SparseBitVectorElement &RHS1, 251193323Sed const SparseBitVectorElement &RHS2, 252193323Sed bool &BecameZero) { 253193323Sed bool allzero = true; 254193323Sed 255193323Sed BecameZero = false; 256193323Sed for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 257193323Sed Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i]; 258193323Sed if (Bits[i] != 0) 259193323Sed allzero = false; 260193323Sed } 261193323Sed BecameZero = allzero; 262193323Sed } 263193323Sed}; 264193323Sed 265243830Sdimtemplate <unsigned ElementSize> 266243830Sdimstruct ilist_traits<SparseBitVectorElement<ElementSize> > 267243830Sdim : public ilist_default_traits<SparseBitVectorElement<ElementSize> > { 268243830Sdim typedef SparseBitVectorElement<ElementSize> Element; 269243830Sdim 270243830Sdim Element *createSentinel() const { return static_cast<Element *>(&Sentinel); } 271243830Sdim static void destroySentinel(Element *) {} 272243830Sdim 273243830Sdim Element *provideInitialHead() const { return createSentinel(); } 274243830Sdim Element *ensureHead(Element *) const { return createSentinel(); } 275243830Sdim static void noteHead(Element *, Element *) {} 276243830Sdim 277243830Sdimprivate: 278243830Sdim mutable ilist_half_node<Element> Sentinel; 279243830Sdim}; 280243830Sdim 281193323Sedtemplate <unsigned ElementSize = 128> 282193323Sedclass SparseBitVector { 283193323Sed typedef ilist<SparseBitVectorElement<ElementSize> > ElementList; 284193323Sed typedef typename ElementList::iterator ElementListIter; 285193323Sed typedef typename ElementList::const_iterator ElementListConstIter; 286193323Sed enum { 287193323Sed BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE 288193323Sed }; 289193323Sed 290193323Sed // Pointer to our current Element. 291193323Sed ElementListIter CurrElementIter; 292193323Sed ElementList Elements; 293193323Sed 294193323Sed // This is like std::lower_bound, except we do linear searching from the 295193323Sed // current position. 296193323Sed ElementListIter FindLowerBound(unsigned ElementIndex) { 297193323Sed 298193323Sed if (Elements.empty()) { 299193323Sed CurrElementIter = Elements.begin(); 300193323Sed return Elements.begin(); 301193323Sed } 302193323Sed 303193323Sed // Make sure our current iterator is valid. 304193323Sed if (CurrElementIter == Elements.end()) 305193323Sed --CurrElementIter; 306193323Sed 307193323Sed // Search from our current iterator, either backwards or forwards, 308193323Sed // depending on what element we are looking for. 309193323Sed ElementListIter ElementIter = CurrElementIter; 310193323Sed if (CurrElementIter->index() == ElementIndex) { 311193323Sed return ElementIter; 312193323Sed } else if (CurrElementIter->index() > ElementIndex) { 313193323Sed while (ElementIter != Elements.begin() 314193323Sed && ElementIter->index() > ElementIndex) 315193323Sed --ElementIter; 316193323Sed } else { 317193323Sed while (ElementIter != Elements.end() && 318193323Sed ElementIter->index() < ElementIndex) 319193323Sed ++ElementIter; 320193323Sed } 321193323Sed CurrElementIter = ElementIter; 322193323Sed return ElementIter; 323193323Sed } 324193323Sed 325193323Sed // Iterator to walk set bits in the bitmap. This iterator is a lot uglier 326193323Sed // than it would be, in order to be efficient. 327193323Sed class SparseBitVectorIterator { 328193323Sed private: 329193323Sed bool AtEnd; 330193323Sed 331193323Sed const SparseBitVector<ElementSize> *BitVector; 332193323Sed 333193323Sed // Current element inside of bitmap. 334193323Sed ElementListConstIter Iter; 335193323Sed 336193323Sed // Current bit number inside of our bitmap. 337193323Sed unsigned BitNumber; 338193323Sed 339193323Sed // Current word number inside of our element. 340193323Sed unsigned WordNumber; 341193323Sed 342193323Sed // Current bits from the element. 343193323Sed typename SparseBitVectorElement<ElementSize>::BitWord Bits; 344193323Sed 345193323Sed // Move our iterator to the first non-zero bit in the bitmap. 346193323Sed void AdvanceToFirstNonZero() { 347193323Sed if (AtEnd) 348193323Sed return; 349193323Sed if (BitVector->Elements.empty()) { 350193323Sed AtEnd = true; 351193323Sed return; 352193323Sed } 353193323Sed Iter = BitVector->Elements.begin(); 354193323Sed BitNumber = Iter->index() * ElementSize; 355193323Sed unsigned BitPos = Iter->find_first(); 356193323Sed BitNumber += BitPos; 357193323Sed WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 358193323Sed Bits = Iter->word(WordNumber); 359193323Sed Bits >>= BitPos % BITWORD_SIZE; 360193323Sed } 361193323Sed 362193323Sed // Move our iterator to the next non-zero bit. 363193323Sed void AdvanceToNextNonZero() { 364193323Sed if (AtEnd) 365193323Sed return; 366193323Sed 367193323Sed while (Bits && !(Bits & 1)) { 368193323Sed Bits >>= 1; 369193323Sed BitNumber += 1; 370193323Sed } 371193323Sed 372193323Sed // See if we ran out of Bits in this word. 373193323Sed if (!Bits) { 374193323Sed int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ; 375193323Sed // If we ran out of set bits in this element, move to next element. 376193323Sed if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) { 377193323Sed ++Iter; 378193323Sed WordNumber = 0; 379193323Sed 380193323Sed // We may run out of elements in the bitmap. 381193323Sed if (Iter == BitVector->Elements.end()) { 382193323Sed AtEnd = true; 383193323Sed return; 384193323Sed } 385193323Sed // Set up for next non zero word in bitmap. 386193323Sed BitNumber = Iter->index() * ElementSize; 387193323Sed NextSetBitNumber = Iter->find_first(); 388193323Sed BitNumber += NextSetBitNumber; 389193323Sed WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 390193323Sed Bits = Iter->word(WordNumber); 391193323Sed Bits >>= NextSetBitNumber % BITWORD_SIZE; 392193323Sed } else { 393193323Sed WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE; 394193323Sed Bits = Iter->word(WordNumber); 395193323Sed Bits >>= NextSetBitNumber % BITWORD_SIZE; 396193323Sed BitNumber = Iter->index() * ElementSize; 397193323Sed BitNumber += NextSetBitNumber; 398193323Sed } 399193323Sed } 400193323Sed } 401193323Sed public: 402193323Sed // Preincrement. 403193323Sed inline SparseBitVectorIterator& operator++() { 404193323Sed ++BitNumber; 405193323Sed Bits >>= 1; 406193323Sed AdvanceToNextNonZero(); 407193323Sed return *this; 408193323Sed } 409193323Sed 410193323Sed // Postincrement. 411193323Sed inline SparseBitVectorIterator operator++(int) { 412193323Sed SparseBitVectorIterator tmp = *this; 413193323Sed ++*this; 414193323Sed return tmp; 415193323Sed } 416193323Sed 417193323Sed // Return the current set bit number. 418193323Sed unsigned operator*() const { 419193323Sed return BitNumber; 420193323Sed } 421193323Sed 422193323Sed bool operator==(const SparseBitVectorIterator &RHS) const { 423193323Sed // If they are both at the end, ignore the rest of the fields. 424193323Sed if (AtEnd && RHS.AtEnd) 425193323Sed return true; 426193323Sed // Otherwise they are the same if they have the same bit number and 427193323Sed // bitmap. 428193323Sed return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber; 429193323Sed } 430193323Sed bool operator!=(const SparseBitVectorIterator &RHS) const { 431193323Sed return !(*this == RHS); 432193323Sed } 433193323Sed SparseBitVectorIterator(): BitVector(NULL) { 434193323Sed } 435193323Sed 436193323Sed 437193323Sed SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS, 438193323Sed bool end = false):BitVector(RHS) { 439193323Sed Iter = BitVector->Elements.begin(); 440193323Sed BitNumber = 0; 441193323Sed Bits = 0; 442193323Sed WordNumber = ~0; 443193323Sed AtEnd = end; 444193323Sed AdvanceToFirstNonZero(); 445193323Sed } 446193323Sed }; 447193323Sedpublic: 448193323Sed typedef SparseBitVectorIterator iterator; 449193323Sed 450193323Sed SparseBitVector () { 451193323Sed CurrElementIter = Elements.begin (); 452193323Sed } 453193323Sed 454193323Sed ~SparseBitVector() { 455193323Sed } 456193323Sed 457193323Sed // SparseBitVector copy ctor. 458193323Sed SparseBitVector(const SparseBitVector &RHS) { 459193323Sed ElementListConstIter ElementIter = RHS.Elements.begin(); 460193323Sed while (ElementIter != RHS.Elements.end()) { 461193323Sed Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 462193323Sed ++ElementIter; 463193323Sed } 464193323Sed 465193323Sed CurrElementIter = Elements.begin (); 466193323Sed } 467193323Sed 468193323Sed // Clear. 469193323Sed void clear() { 470193323Sed Elements.clear(); 471193323Sed } 472193323Sed 473193323Sed // Assignment 474193323Sed SparseBitVector& operator=(const SparseBitVector& RHS) { 475193323Sed Elements.clear(); 476193323Sed 477193323Sed ElementListConstIter ElementIter = RHS.Elements.begin(); 478193323Sed while (ElementIter != RHS.Elements.end()) { 479193323Sed Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 480193323Sed ++ElementIter; 481193323Sed } 482193323Sed 483193323Sed CurrElementIter = Elements.begin (); 484193323Sed 485193323Sed return *this; 486193323Sed } 487193323Sed 488193323Sed // Test, Reset, and Set a bit in the bitmap. 489193323Sed bool test(unsigned Idx) { 490193323Sed if (Elements.empty()) 491193323Sed return false; 492193323Sed 493193323Sed unsigned ElementIndex = Idx / ElementSize; 494193323Sed ElementListIter ElementIter = FindLowerBound(ElementIndex); 495193323Sed 496193323Sed // If we can't find an element that is supposed to contain this bit, there 497193323Sed // is nothing more to do. 498193323Sed if (ElementIter == Elements.end() || 499193323Sed ElementIter->index() != ElementIndex) 500193323Sed return false; 501193323Sed return ElementIter->test(Idx % ElementSize); 502193323Sed } 503193323Sed 504193323Sed void reset(unsigned Idx) { 505193323Sed if (Elements.empty()) 506193323Sed return; 507193323Sed 508193323Sed unsigned ElementIndex = Idx / ElementSize; 509193323Sed ElementListIter ElementIter = FindLowerBound(ElementIndex); 510193323Sed 511193323Sed // If we can't find an element that is supposed to contain this bit, there 512193323Sed // is nothing more to do. 513193323Sed if (ElementIter == Elements.end() || 514193323Sed ElementIter->index() != ElementIndex) 515193323Sed return; 516193323Sed ElementIter->reset(Idx % ElementSize); 517193323Sed 518193323Sed // When the element is zeroed out, delete it. 519193323Sed if (ElementIter->empty()) { 520193323Sed ++CurrElementIter; 521193323Sed Elements.erase(ElementIter); 522193323Sed } 523193323Sed } 524193323Sed 525193323Sed void set(unsigned Idx) { 526193323Sed unsigned ElementIndex = Idx / ElementSize; 527193323Sed SparseBitVectorElement<ElementSize> *Element; 528193323Sed ElementListIter ElementIter; 529193323Sed if (Elements.empty()) { 530193323Sed Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 531193323Sed ElementIter = Elements.insert(Elements.end(), Element); 532193323Sed 533193323Sed } else { 534193323Sed ElementIter = FindLowerBound(ElementIndex); 535193323Sed 536193323Sed if (ElementIter == Elements.end() || 537193323Sed ElementIter->index() != ElementIndex) { 538193323Sed Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 539193323Sed // We may have hit the beginning of our SparseBitVector, in which case, 540193323Sed // we may need to insert right after this element, which requires moving 541193323Sed // the current iterator forward one, because insert does insert before. 542193323Sed if (ElementIter != Elements.end() && 543193323Sed ElementIter->index() < ElementIndex) 544193323Sed ElementIter = Elements.insert(++ElementIter, Element); 545193323Sed else 546193323Sed ElementIter = Elements.insert(ElementIter, Element); 547193323Sed } 548193323Sed } 549193323Sed CurrElementIter = ElementIter; 550193323Sed 551193323Sed ElementIter->set(Idx % ElementSize); 552193323Sed } 553193323Sed 554193323Sed bool test_and_set (unsigned Idx) { 555193323Sed bool old = test(Idx); 556193323Sed if (!old) { 557193323Sed set(Idx); 558193323Sed return true; 559193323Sed } 560193323Sed return false; 561193323Sed } 562193323Sed 563193323Sed bool operator!=(const SparseBitVector &RHS) const { 564193323Sed return !(*this == RHS); 565193323Sed } 566193323Sed 567193323Sed bool operator==(const SparseBitVector &RHS) const { 568193323Sed ElementListConstIter Iter1 = Elements.begin(); 569193323Sed ElementListConstIter Iter2 = RHS.Elements.begin(); 570193323Sed 571193323Sed for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end(); 572193323Sed ++Iter1, ++Iter2) { 573193323Sed if (*Iter1 != *Iter2) 574193323Sed return false; 575193323Sed } 576193323Sed return Iter1 == Elements.end() && Iter2 == RHS.Elements.end(); 577193323Sed } 578193323Sed 579193323Sed // Union our bitmap with the RHS and return true if we changed. 580193323Sed bool operator|=(const SparseBitVector &RHS) { 581193323Sed bool changed = false; 582193323Sed ElementListIter Iter1 = Elements.begin(); 583193323Sed ElementListConstIter Iter2 = RHS.Elements.begin(); 584193323Sed 585193323Sed // If RHS is empty, we are done 586193323Sed if (RHS.Elements.empty()) 587193323Sed return false; 588193323Sed 589193323Sed while (Iter2 != RHS.Elements.end()) { 590193323Sed if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) { 591193323Sed Elements.insert(Iter1, 592193323Sed new SparseBitVectorElement<ElementSize>(*Iter2)); 593193323Sed ++Iter2; 594193323Sed changed = true; 595193323Sed } else if (Iter1->index() == Iter2->index()) { 596193323Sed changed |= Iter1->unionWith(*Iter2); 597193323Sed ++Iter1; 598193323Sed ++Iter2; 599193323Sed } else { 600193323Sed ++Iter1; 601193323Sed } 602193323Sed } 603193323Sed CurrElementIter = Elements.begin(); 604193323Sed return changed; 605193323Sed } 606193323Sed 607193323Sed // Intersect our bitmap with the RHS and return true if ours changed. 608193323Sed bool operator&=(const SparseBitVector &RHS) { 609193323Sed bool changed = false; 610193323Sed ElementListIter Iter1 = Elements.begin(); 611193323Sed ElementListConstIter Iter2 = RHS.Elements.begin(); 612193323Sed 613193323Sed // Check if both bitmaps are empty. 614193323Sed if (Elements.empty() && RHS.Elements.empty()) 615193323Sed return false; 616193323Sed 617193323Sed // Loop through, intersecting as we go, erasing elements when necessary. 618193323Sed while (Iter2 != RHS.Elements.end()) { 619193323Sed if (Iter1 == Elements.end()) { 620193323Sed CurrElementIter = Elements.begin(); 621193323Sed return changed; 622193323Sed } 623193323Sed 624193323Sed if (Iter1->index() > Iter2->index()) { 625193323Sed ++Iter2; 626193323Sed } else if (Iter1->index() == Iter2->index()) { 627193323Sed bool BecameZero; 628193323Sed changed |= Iter1->intersectWith(*Iter2, BecameZero); 629193323Sed if (BecameZero) { 630193323Sed ElementListIter IterTmp = Iter1; 631193323Sed ++Iter1; 632193323Sed Elements.erase(IterTmp); 633193323Sed } else { 634193323Sed ++Iter1; 635193323Sed } 636193323Sed ++Iter2; 637193323Sed } else { 638193323Sed ElementListIter IterTmp = Iter1; 639193323Sed ++Iter1; 640193323Sed Elements.erase(IterTmp); 641193323Sed } 642193323Sed } 643193323Sed Elements.erase(Iter1, Elements.end()); 644193323Sed CurrElementIter = Elements.begin(); 645193323Sed return changed; 646193323Sed } 647193323Sed 648193323Sed // Intersect our bitmap with the complement of the RHS and return true 649193323Sed // if ours changed. 650193323Sed bool intersectWithComplement(const SparseBitVector &RHS) { 651193323Sed bool changed = false; 652193323Sed ElementListIter Iter1 = Elements.begin(); 653193323Sed ElementListConstIter Iter2 = RHS.Elements.begin(); 654193323Sed 655193323Sed // If either our bitmap or RHS is empty, we are done 656193323Sed if (Elements.empty() || RHS.Elements.empty()) 657193323Sed return false; 658193323Sed 659193323Sed // Loop through, intersecting as we go, erasing elements when necessary. 660193323Sed while (Iter2 != RHS.Elements.end()) { 661193323Sed if (Iter1 == Elements.end()) { 662193323Sed CurrElementIter = Elements.begin(); 663193323Sed return changed; 664193323Sed } 665193323Sed 666193323Sed if (Iter1->index() > Iter2->index()) { 667193323Sed ++Iter2; 668193323Sed } else if (Iter1->index() == Iter2->index()) { 669193323Sed bool BecameZero; 670193323Sed changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); 671193323Sed if (BecameZero) { 672193323Sed ElementListIter IterTmp = Iter1; 673193323Sed ++Iter1; 674193323Sed Elements.erase(IterTmp); 675193323Sed } else { 676193323Sed ++Iter1; 677193323Sed } 678193323Sed ++Iter2; 679193323Sed } else { 680193323Sed ++Iter1; 681193323Sed } 682193323Sed } 683193323Sed CurrElementIter = Elements.begin(); 684193323Sed return changed; 685193323Sed } 686193323Sed 687193323Sed bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const { 688193323Sed return intersectWithComplement(*RHS); 689193323Sed } 690193323Sed 691193323Sed 692193323Sed // Three argument version of intersectWithComplement. 693193323Sed // Result of RHS1 & ~RHS2 is stored into this bitmap. 694193323Sed void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, 695193323Sed const SparseBitVector<ElementSize> &RHS2) 696193323Sed { 697193323Sed Elements.clear(); 698193323Sed CurrElementIter = Elements.begin(); 699193323Sed ElementListConstIter Iter1 = RHS1.Elements.begin(); 700193323Sed ElementListConstIter Iter2 = RHS2.Elements.begin(); 701193323Sed 702193323Sed // If RHS1 is empty, we are done 703193323Sed // If RHS2 is empty, we still have to copy RHS1 704193323Sed if (RHS1.Elements.empty()) 705193323Sed return; 706193323Sed 707193323Sed // Loop through, intersecting as we go, erasing elements when necessary. 708193323Sed while (Iter2 != RHS2.Elements.end()) { 709193323Sed if (Iter1 == RHS1.Elements.end()) 710193323Sed return; 711193323Sed 712193323Sed if (Iter1->index() > Iter2->index()) { 713193323Sed ++Iter2; 714193323Sed } else if (Iter1->index() == Iter2->index()) { 715193323Sed bool BecameZero = false; 716193323Sed SparseBitVectorElement<ElementSize> *NewElement = 717193323Sed new SparseBitVectorElement<ElementSize>(Iter1->index()); 718193323Sed NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero); 719193323Sed if (!BecameZero) { 720193323Sed Elements.push_back(NewElement); 721193323Sed } 722193323Sed else 723193323Sed delete NewElement; 724193323Sed ++Iter1; 725193323Sed ++Iter2; 726193323Sed } else { 727193323Sed SparseBitVectorElement<ElementSize> *NewElement = 728193323Sed new SparseBitVectorElement<ElementSize>(*Iter1); 729193323Sed Elements.push_back(NewElement); 730193323Sed ++Iter1; 731193323Sed } 732193323Sed } 733193323Sed 734193323Sed // copy the remaining elements 735193323Sed while (Iter1 != RHS1.Elements.end()) { 736193323Sed SparseBitVectorElement<ElementSize> *NewElement = 737193323Sed new SparseBitVectorElement<ElementSize>(*Iter1); 738193323Sed Elements.push_back(NewElement); 739193323Sed ++Iter1; 740193323Sed } 741193323Sed 742193323Sed return; 743193323Sed } 744193323Sed 745193323Sed void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1, 746193323Sed const SparseBitVector<ElementSize> *RHS2) { 747193323Sed intersectWithComplement(*RHS1, *RHS2); 748193323Sed } 749193323Sed 750193323Sed bool intersects(const SparseBitVector<ElementSize> *RHS) const { 751193323Sed return intersects(*RHS); 752193323Sed } 753193323Sed 754193323Sed // Return true if we share any bits in common with RHS 755193323Sed bool intersects(const SparseBitVector<ElementSize> &RHS) const { 756193323Sed ElementListConstIter Iter1 = Elements.begin(); 757193323Sed ElementListConstIter Iter2 = RHS.Elements.begin(); 758193323Sed 759193323Sed // Check if both bitmaps are empty. 760193323Sed if (Elements.empty() && RHS.Elements.empty()) 761193323Sed return false; 762193323Sed 763193323Sed // Loop through, intersecting stopping when we hit bits in common. 764193323Sed while (Iter2 != RHS.Elements.end()) { 765193323Sed if (Iter1 == Elements.end()) 766193323Sed return false; 767193323Sed 768193323Sed if (Iter1->index() > Iter2->index()) { 769193323Sed ++Iter2; 770193323Sed } else if (Iter1->index() == Iter2->index()) { 771193323Sed if (Iter1->intersects(*Iter2)) 772193323Sed return true; 773193323Sed ++Iter1; 774193323Sed ++Iter2; 775193323Sed } else { 776193323Sed ++Iter1; 777193323Sed } 778193323Sed } 779193323Sed return false; 780193323Sed } 781193323Sed 782193323Sed // Return true iff all bits set in this SparseBitVector are 783193323Sed // also set in RHS. 784193323Sed bool contains(const SparseBitVector<ElementSize> &RHS) const { 785193323Sed SparseBitVector<ElementSize> Result(*this); 786193323Sed Result &= RHS; 787193323Sed return (Result == RHS); 788193323Sed } 789193323Sed 790193323Sed // Return the first set bit in the bitmap. Return -1 if no bits are set. 791193323Sed int find_first() const { 792193323Sed if (Elements.empty()) 793193323Sed return -1; 794193323Sed const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); 795193323Sed return (First.index() * ElementSize) + First.find_first(); 796193323Sed } 797193323Sed 798193323Sed // Return true if the SparseBitVector is empty 799193323Sed bool empty() const { 800193323Sed return Elements.empty(); 801193323Sed } 802193323Sed 803193323Sed unsigned count() const { 804193323Sed unsigned BitCount = 0; 805193323Sed for (ElementListConstIter Iter = Elements.begin(); 806193323Sed Iter != Elements.end(); 807193323Sed ++Iter) 808193323Sed BitCount += Iter->count(); 809193323Sed 810193323Sed return BitCount; 811193323Sed } 812193323Sed iterator begin() const { 813193323Sed return iterator(this); 814193323Sed } 815193323Sed 816193323Sed iterator end() const { 817193323Sed return iterator(this, true); 818193323Sed } 819193323Sed}; 820193323Sed 821193323Sed// Convenience functions to allow Or and And without dereferencing in the user 822193323Sed// code. 823193323Sed 824193323Sedtemplate <unsigned ElementSize> 825193323Sedinline bool operator |=(SparseBitVector<ElementSize> &LHS, 826193323Sed const SparseBitVector<ElementSize> *RHS) { 827193323Sed return LHS |= *RHS; 828193323Sed} 829193323Sed 830193323Sedtemplate <unsigned ElementSize> 831193323Sedinline bool operator |=(SparseBitVector<ElementSize> *LHS, 832193323Sed const SparseBitVector<ElementSize> &RHS) { 833193323Sed return LHS->operator|=(RHS); 834193323Sed} 835193323Sed 836193323Sedtemplate <unsigned ElementSize> 837193323Sedinline bool operator &=(SparseBitVector<ElementSize> *LHS, 838193323Sed const SparseBitVector<ElementSize> &RHS) { 839193323Sed return LHS->operator&=(RHS); 840193323Sed} 841193323Sed 842193323Sedtemplate <unsigned ElementSize> 843193323Sedinline bool operator &=(SparseBitVector<ElementSize> &LHS, 844193323Sed const SparseBitVector<ElementSize> *RHS) { 845193323Sed return LHS &= *RHS; 846193323Sed} 847193323Sed 848193323Sed// Convenience functions for infix union, intersection, difference operators. 849193323Sed 850193323Sedtemplate <unsigned ElementSize> 851193323Sedinline SparseBitVector<ElementSize> 852193323Sedoperator|(const SparseBitVector<ElementSize> &LHS, 853193323Sed const SparseBitVector<ElementSize> &RHS) { 854193323Sed SparseBitVector<ElementSize> Result(LHS); 855193323Sed Result |= RHS; 856193323Sed return Result; 857193323Sed} 858193323Sed 859193323Sedtemplate <unsigned ElementSize> 860193323Sedinline SparseBitVector<ElementSize> 861193323Sedoperator&(const SparseBitVector<ElementSize> &LHS, 862193323Sed const SparseBitVector<ElementSize> &RHS) { 863193323Sed SparseBitVector<ElementSize> Result(LHS); 864193323Sed Result &= RHS; 865193323Sed return Result; 866193323Sed} 867193323Sed 868193323Sedtemplate <unsigned ElementSize> 869193323Sedinline SparseBitVector<ElementSize> 870193323Sedoperator-(const SparseBitVector<ElementSize> &LHS, 871193323Sed const SparseBitVector<ElementSize> &RHS) { 872193323Sed SparseBitVector<ElementSize> Result; 873193323Sed Result.intersectWithComplement(LHS, RHS); 874193323Sed return Result; 875193323Sed} 876193323Sed 877193323Sed 878193323Sed 879193323Sed 880193323Sed// Dump a SparseBitVector to a stream 881193323Sedtemplate <unsigned ElementSize> 882198090Srdivackyvoid dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) { 883208599Srdivacky out << "["; 884193323Sed 885208599Srdivacky typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(), 886208599Srdivacky be = LHS.end(); 887208599Srdivacky if (bi != be) { 888208599Srdivacky out << *bi; 889208599Srdivacky for (++bi; bi != be; ++bi) { 890208599Srdivacky out << " " << *bi; 891208599Srdivacky } 892193323Sed } 893208599Srdivacky out << "]\n"; 894193323Sed} 895193323Sed} // end namespace llvm 896193323Sed 897193323Sed#endif 898