12f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin//===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector -*- C++ -*- ===// 22f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// 32f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// The LLVM Compiler Infrastructure 42f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 72f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// 82f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin//===----------------------------------------------------------------------===// 92f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// 102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// This file defines the SparseBitVector class. See the doxygen comment for 112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// SparseBitVector for more details on the algorithm used. 122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin// 132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin//===----------------------------------------------------------------------===// 142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#ifndef LLVM_ADT_SPARSEBITVECTOR_H 162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#define LLVM_ADT_SPARSEBITVECTOR_H 172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1843d1fd449f1a0ac9d9dafa0b9569bb6b2e976198Anton Korobeynikov#include "llvm/ADT/ilist.h" 19f595d6dd9a61c7387768d4e041539fcc6525a99bJeffrey Yasskin#include "llvm/ADT/ilist_node.h" 201f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 2150bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper#include "llvm/Support/ErrorHandling.h" 223f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbar#include "llvm/Support/MathExtras.h" 233f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbar#include "llvm/Support/raw_ostream.h" 24ee3d6fd219da0e528ddfc170c6058bd78473ecccBenjamin Kramer#include <cassert> 25ee3d6fd219da0e528ddfc170c6058bd78473ecccBenjamin Kramer#include <climits> 26d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman 272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinnamespace llvm { 282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// SparseBitVector is an implementation of a bitvector that is sparse by only 302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// storing the elements that have non-zero bits set. In order to make this 312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// fast for the most common cases, SparseBitVector is implemented as a linked 322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// list of SparseBitVectorElements. We maintain a pointer to the last 332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// SparseBitVectorElement accessed (in the form of a list iterator), in order 342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// to make multiple in-order test/set constant time after the first one is 352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// executed. Note that using vectors to store SparseBitVectorElement's does 362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// not work out very well because it causes insertion in the middle to take 372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// enormous amounts of time with a large amount of bits. Other structures that 382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// have better worst cases for insertion in the middle (various balanced trees, 392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// etc) do not perform as well in practice as a linked list with this iterator 402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// kept up to date. They are also significantly more memory intensive. 412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlintemplate <unsigned ElementSize = 128> 44fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanstruct SparseBitVectorElement 4559bf4fcc0680e75b408579064d1205a132361196Duncan Sands : public ilist_node<SparseBitVectorElement<ElementSize> > { 462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef unsigned long BitWord; 482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin enum { 49de551f91d8816632a76a065084caab9fab6aacffDan Gohman BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT, 502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, 512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITS_PER_ELEMENT = ElementSize 522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 536320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinprivate: 552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Index of Element in terms of where first bit starts. 562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex; 572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord Bits[BITWORDS_PER_ELEMENT]; 586320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Needed for sentinels 5913bb81addfc15d9852711191696f5bd6e52f9552Bill Wendling friend struct ilist_sentinel_traits<SparseBitVectorElement>; 606320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement() { 61acddf9d019316ac1735667dc92d96092e9f5bf2eScott Michel ElementIndex = ~0U; 626320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 636320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } 646320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin explicit SparseBitVectorElement(unsigned Idx) { 672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementIndex = Idx; 682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Comparison. 722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator==(const SparseBitVectorElement &RHS) const { 732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIndex != RHS.ElementIndex) 742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != RHS.Bits[i]) 772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator!=(const SparseBitVectorElement &RHS) const { 822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return !(*this == RHS); 832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Return the bits that make up word Idx in our element. 862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord word(unsigned Idx) const { 872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert (Idx < BITWORDS_PER_ELEMENT); 882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Bits[Idx]; 892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned index() const { 922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIndex; 932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool empty() const { 962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i]) 982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 1002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void set(unsigned Idx) { 1032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 1042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test_and_set (unsigned Idx) { 1072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool old = test(Idx); 108c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin if (!old) { 1092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin set(Idx); 110c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return true; 111c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 112c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 1132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void reset(unsigned Idx) { 1162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 1172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test(unsigned Idx) const { 1202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE)); 1212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned count() const { 1242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned NumBits = 0; 1252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 1262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin NumBits += CountPopulation_32(Bits[i]); 1282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin NumBits += CountPopulation_64(Bits[i]); 1302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 13150bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return NumBits; 1332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin /// find_first - Returns the index of the first set bit. 1362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin int find_first() const { 1372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 1382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) { 1392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 14150bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 1422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 14350bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 14550bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Illegal empty element"); 1462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 14808bb6998437528143934de9c76fa312e48e58896Daniel Berlin /// find_next - Returns the index of the next set bit starting from the 14908bb6998437528143934de9c76fa312e48e58896Daniel Berlin /// "Curr" bit. Returns -1 if the next set bit is not found. 15008bb6998437528143934de9c76fa312e48e58896Daniel Berlin int find_next(unsigned Curr) const { 15108bb6998437528143934de9c76fa312e48e58896Daniel Berlin if (Curr >= BITS_PER_ELEMENT) 1522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return -1; 1532f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 15408bb6998437528143934de9c76fa312e48e58896Daniel Berlin unsigned WordPos = Curr / BITWORD_SIZE; 15508bb6998437528143934de9c76fa312e48e58896Daniel Berlin unsigned BitPos = Curr % BITWORD_SIZE; 1562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord Copy = Bits[WordPos]; 1572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert (WordPos <= BITWORDS_PER_ELEMENT 1582f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin && "Word Position outside of element"); 1592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Mask off previous bits. 1612f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Copy &= ~0L << BitPos; 1622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Copy != 0) { 1642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy); 16650bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 1672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 16850bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Check subsequent words. 1722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) 1732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) { 1742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 17650bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 1772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 17850bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 1792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return -1; 1812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Union this element with RHS and return true if this one changed. 1842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool unionWith(const SparseBitVectorElement &RHS) { 1852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 1862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 1872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord old = changed ? 0 : Bits[i]; 1882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[i] |= RHS.Bits[i]; 1907f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 1912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 1922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 1942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1961b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if we have any bits in common with RHS 1971b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVectorElement &RHS) const { 1981b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 1991b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (RHS.Bits[i] & Bits[i]) 20016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return true; 2011b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 2021b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 2031b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 20416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 2052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Intersect this Element with RHS and return true if this one changed. 2062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // BecameZero is set to true if this element became all-zero bits. 2072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool intersectWith(const SparseBitVectorElement &RHS, 2082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool &BecameZero) { 2092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 2102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool allzero = true; 2112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BecameZero = false; 2132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord old = changed ? 0 : Bits[i]; 2152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[i] &= RHS.Bits[i]; 2172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) 2182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin allzero = false; 2192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2207f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 2212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 2222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2237f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 2242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 2252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2261b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Intersect this Element with the complement of RHS and return true if this 2271b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // one changed. BecameZero is set to true if this element became all-zero 2281b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // bits. 2291b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVectorElement &RHS, 2307f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin bool &BecameZero) { 2311b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool changed = false; 2321b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool allzero = true; 2331b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin BecameZero = false; 2351b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2361b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin BitWord old = changed ? 0 : Bits[i]; 2371b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Bits[i] &= ~RHS.Bits[i]; 2391b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Bits[i] != 0) 2401b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin allzero = false; 2411b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2427f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 2431b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin changed = true; 2441b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 2457f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 2461b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 2471b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 24816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Three argument version of intersectWithComplement that intersects 24916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // RHS1 & ~RHS2 into this element 25016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVectorElement &RHS1, 25116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVectorElement &RHS2, 25216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool &BecameZero) { 25316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool allzero = true; 25416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 25516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin BecameZero = false; 25616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 25716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i]; 25816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin if (Bits[i] != 0) 25916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin allzero = false; 26016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 2617f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 26216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 2632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin}; 2642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlintemplate <unsigned ElementSize = 128> 2662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinclass SparseBitVector { 2676320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin typedef ilist<SparseBitVectorElement<ElementSize> > ElementList; 2682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::iterator ElementListIter; 2692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::const_iterator ElementListConstIter; 2702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin enum { 2712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE 2722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 2732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Pointer to our current Element. 2752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter CurrElementIter; 2762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementList Elements; 2772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // This is like std::lower_bound, except we do linear searching from the 2792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // current position. 2802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter FindLowerBound(unsigned ElementIndex) { 2812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 2832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 2842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Elements.begin(); 2852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Make sure our current iterator is valid. 2882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (CurrElementIter == Elements.end()) 2892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --CurrElementIter; 2902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Search from our current iterator, either backwards or forwards, 2922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // depending on what element we are looking for. 2932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = CurrElementIter; 2946320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (CurrElementIter->index() == ElementIndex) { 2952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 2966320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (CurrElementIter->index() > ElementIndex) { 2972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.begin() 2986320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin && ElementIter->index() > ElementIndex) 2992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --ElementIter; 3002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 3012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.end() && 302c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter->index() < ElementIndex) 3032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++ElementIter; 3042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = ElementIter; 3062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 3072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Iterator to walk set bits in the bitmap. This iterator is a lot uglier 3102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // than it would be, in order to be efficient. 3111b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin class SparseBitVectorIterator { 3122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin private: 3132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool AtEnd; 3142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3151b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *BitVector; 3162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current element inside of bitmap. 3182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter; 3192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bit number inside of our bitmap. 3212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned BitNumber; 3222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current word number inside of our element. 3242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned WordNumber; 3252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bits from the element. 3272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typename SparseBitVectorElement<ElementSize>::BitWord Bits; 3282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the first non-zero bit in the bitmap. 3302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToFirstNonZero() { 3312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3331b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BitVector->Elements.empty()) { 3342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 3352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3371b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 3386320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 3396320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin unsigned BitPos = Iter->find_first(); 3402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += BitPos; 3412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 3426320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= BitPos % BITWORD_SIZE; 3442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the next non-zero bit. 3472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToNextNonZero() { 3482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Bits && !(Bits & 1)) { 3522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 3532f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += 1; 3542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // See if we ran out of Bits in this word. 3572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (!Bits) { 35808bb6998437528143934de9c76fa312e48e58896Daniel Berlin int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ; 3592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we ran out of set bits in this element, move to next element. 3602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) { 36116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter; 3622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = 0; 3632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // We may run out of elements in the bitmap. 3651b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter == BitVector->Elements.end()) { 3662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 3672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Set up for next non zero word in bitmap. 3706320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 3716320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NextSetBitNumber = Iter->find_first(); 3722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += NextSetBitNumber; 3732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 3746320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 3762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 3772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE; 3786320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 380430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber = Iter->index() * ElementSize; 381430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber += NextSetBitNumber; 3822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin public: 3862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Preincrement. 3872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator& operator++() { 38816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++BitNumber; 3892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 3902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToNextNonZero(); 3912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return *this; 3922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Postincrement. 3952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator operator++(int) { 3962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVectorIterator tmp = *this; 3972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++*this; 3982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return tmp; 3992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Return the current set bit number. 4022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned operator*() const { 4032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return BitNumber; 4042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator==(const SparseBitVectorIterator &RHS) const { 4072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If they are both at the end, ignore the rest of the fields. 4089f711252f5d5ef4e05f5277ab462bf7668b53cfdDaniel Berlin if (AtEnd && RHS.AtEnd) 4092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 4102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Otherwise they are the same if they have the same bit number and 4112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // bitmap. 4122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber; 4132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator!=(const SparseBitVectorIterator &RHS) const { 4152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return !(*this == RHS); 4162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 41716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorIterator(): BitVector(NULL) { 4181b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 41916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 42016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 4211b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS, 4221b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool end = false):BitVector(RHS) { 4231b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 4242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber = 0; 4252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits = 0; 4262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = ~0; 4272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = end; 4282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToFirstNonZero(); 4292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 4312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 4322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef SparseBitVectorIterator iterator; 4332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector () { 4352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ~SparseBitVector() { 4392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // SparseBitVector copy ctor. 4422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector(const SparseBitVector &RHS) { 4432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter ElementIter = RHS.Elements.begin(); 4442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != RHS.Elements.end()) { 4456320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 4466320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++ElementIter; 4472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4523ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner // Clear. 4533ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner void clear() { 4543ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Elements.clear(); 4553ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner } 4563ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 457412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson // Assignment 458412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson SparseBitVector& operator=(const SparseBitVector& RHS) { 459412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson Elements.clear(); 4603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 461412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson ElementListConstIter ElementIter = RHS.Elements.begin(); 462412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson while (ElementIter != RHS.Elements.end()) { 463412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 464412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson ++ElementIter; 465412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson } 466412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson 467412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson CurrElementIter = Elements.begin (); 4683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 469412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson return *this; 470412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson } 4712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Test, Reset, and Set a bit in the bitmap. 4732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test(unsigned Idx) { 4742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 4752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 4762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 4782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 4792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 4812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 4822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 4836320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 4842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 4856320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return ElementIter->test(Idx % ElementSize); 4862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void reset(unsigned Idx) { 4892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 4902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 4912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 4932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 4942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 4962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 4972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 4986320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 4992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 5006320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->reset(Idx % ElementSize); 5012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // When the element is zeroed out, delete it. 5036320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter->empty()) { 5042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++CurrElementIter; 5052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(ElementIter); 5062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void set(unsigned Idx) { 5102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 5116320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *Element; 5126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementListIter ElementIter; 5132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 5142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 5156320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = Elements.insert(Elements.end(), Element); 5166320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 5172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 5186320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = FindLowerBound(ElementIndex); 5192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5206320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter == Elements.end() || 5216320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) { 5222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 523c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // We may have hit the beginning of our SparseBitVector, in which case, 524c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // we may need to insert right after this element, which requires moving 525c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // the current iterator forward one, because insert does insert before. 5268d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin if (ElementIter != Elements.end() && 5278d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin ElementIter->index() < ElementIndex) 528c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(++ElementIter, Element); 529c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin else 530c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(ElementIter, Element); 5312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 533c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin CurrElementIter = ElementIter; 53408bb6998437528143934de9c76fa312e48e58896Daniel Berlin 5356320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->set(Idx % ElementSize); 5362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 53716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 5381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool test_and_set (unsigned Idx) { 5391b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool old = test(Idx); 540c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin if (!old) { 5411b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin set(Idx); 542c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return true; 543c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 544c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 545c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 546c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 547d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator!=(const SparseBitVector &RHS) const { 548c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return !(*this == RHS); 549c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 550c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 551d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator==(const SparseBitVector &RHS) const { 552c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter1 = Elements.begin(); 553c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 554c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 555d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end(); 556d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin ++Iter1, ++Iter2) { 557d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin if (*Iter1 != *Iter2) 558c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 559c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 560d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return Iter1 == Elements.end() && Iter2 == RHS.Elements.end(); 5611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 5622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Union our bitmap with the RHS and return true if we changed. 5642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator|=(const SparseBitVector &RHS) { 5652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 5662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 5672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 5682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 569ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin // If RHS is empty, we are done 570ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin if (RHS.Elements.empty()) 5712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 5722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 5746320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) { 5756320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.insert(Iter1, 5766320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter2)); 57716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 5796320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 5806320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->unionWith(*Iter2); 58116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 58216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 58416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 5852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 5882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 5892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Intersect our bitmap with the RHS and return true if ours changed. 5922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator&=(const SparseBitVector &RHS) { 5932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 5942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 5952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 5962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5976320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 5986320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 5992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 6002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 60307268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 60407268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 60607268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6086320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 60916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6106320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool BecameZero; 6126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWith(*Iter2, BecameZero); 6132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (BecameZero) { 6142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 6157f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6177f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6187f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 62016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 6222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 62316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 62716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.erase(Iter1, Elements.end()); 6282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 6292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 6302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 632b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // Intersect our bitmap with the complement of the RHS and return true 633b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // if ours changed. 6341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector &RHS) { 6351b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool changed = false; 6361b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter Iter1 = Elements.begin(); 6371b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 6381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 639c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If either our bitmap or RHS is empty, we are done 640c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (Elements.empty() || RHS.Elements.empty()) 6411b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 6421b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6431b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6441b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 64507268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 64607268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6471b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 64807268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6506320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 65116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6526320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool BecameZero; 6546320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); 6551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BecameZero) { 6561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter IterTmp = Iter1; 6577f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6581b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Elements.erase(IterTmp); 6597f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6607f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 66216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6631b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 66416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6651b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6661b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6671b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin CurrElementIter = Elements.begin(); 6681b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 6691b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6701b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6711b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const { 6721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersectWithComplement(*RHS); 6731b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 67416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 67516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 676b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // Three argument version of intersectWithComplement. 677b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // Result of RHS1 & ~RHS2 is stored into this bitmap. 67816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, 67916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS2) 68016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin { 68116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.clear(); 68207268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 68316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter1 = RHS1.Elements.begin(); 68416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter2 = RHS2.Elements.begin(); 68516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 686c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS1 is empty, we are done 687c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS2 is empty, we still have to copy RHS1 688c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (RHS1.Elements.empty()) 68916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 69016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 69116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 69216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter2 != RHS2.Elements.end()) { 69316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin if (Iter1 == RHS1.Elements.end()) 69416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 69516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 6966320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 69716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6986320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 69916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool BecameZero = false; 70016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7016320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(Iter1->index()); 7026320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero); 7036320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (!BecameZero) { 70416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 70516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7066320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin else 7076320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin delete NewElement; 70816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 70916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 71016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } else { 711c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 712c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 713c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin Elements.push_back(NewElement); 71416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 71516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 71616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7176320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 71816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // copy the remaining elements 71916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter1 != RHS1.Elements.end()) { 72016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7216320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 72216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 7236320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++Iter1; 72416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7256320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 72616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 72716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 72816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 72916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1, 73016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS2) { 73116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin intersectWithComplement(*RHS1, *RHS2); 73216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 73316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> *RHS) const { 7351b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersects(*RHS); 7361b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 73716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if we share any bits in common with RHS 7391b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> &RHS) const { 7401b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter1 = Elements.begin(); 7411b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 7421b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7436320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 7446320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 7451b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7461b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7471b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting stopping when we hit bits in common. 7481b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 7491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter1 == Elements.end()) 7501b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7511b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7526320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 75316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7546320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 7556320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->intersects(*Iter2)) 7561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return true; 75716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 75816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7591b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 76016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 7611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7621b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7631b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7641b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 76516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 766b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // Return true iff all bits set in this SparseBitVector are 767b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // also set in RHS. 768b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby bool contains(const SparseBitVector<ElementSize> &RHS) const { 769b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby SparseBitVector<ElementSize> Result(*this); 770b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby Result &= RHS; 771b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby return (Result == RHS); 772b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby } 773b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby 7741b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return the first set bit in the bitmap. Return -1 if no bits are set. 7751b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin int find_first() const { 7761b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Elements.empty()) 7771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return -1; 7786320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); 7796320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return (First.index() * ElementSize) + First.find_first(); 7801b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7811b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7821b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if the SparseBitVector is empty 7831b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool empty() const { 7841b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return Elements.empty(); 7851b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 78616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7871b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned count() const { 7881b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned BitCount = 0; 7891b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (ElementListConstIter Iter = Elements.begin(); 7901b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter != Elements.end(); 7911b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ++Iter) 7926320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitCount += Iter->count(); 79316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7941b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return BitCount; 7951b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator begin() const { 7971b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return iterator(this); 7982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 7992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 8002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator end() const { 801729bd28f62d83c9681702264a79c4ab03c7c11ecHartmut Kaiser return iterator(this, true); 8022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 8032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin}; 8041b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8051b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin// Convenience functions to allow Or and And without dereferencing in the user 80616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin// code. 80716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 8081b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 80916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> &LHS, 81016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS) { 81116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS |= *RHS; 8121b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8131b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8141b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 81516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> *LHS, 81616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS) { 81716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator|=(RHS); 8181b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8191b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8201b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 82116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> *LHS, 8221b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> &RHS) { 82316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator&=(RHS); 8241b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8251b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8261b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 82716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> &LHS, 8281b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *RHS) { 8293ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return LHS &= *RHS; 8303ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8313ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8323ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner// Convenience functions for infix union, intersection, difference operators. 8333ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8343ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8353ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8363ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator|(const SparseBitVector<ElementSize> &LHS, 8373ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8383ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result(LHS); 8393ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result |= RHS; 8403ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8413ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8423ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8433ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8443ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8453ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator&(const SparseBitVector<ElementSize> &LHS, 8463ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8473ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result(LHS); 8483ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result &= RHS; 8493ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8503ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8513ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8523ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8533ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8543ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator-(const SparseBitVector<ElementSize> &LHS, 8553ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8563ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result; 8573ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result.intersectWithComplement(LHS, RHS); 8583ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8591b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8607f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin 861ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin 862b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby 863b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby 864ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin// Dump a SparseBitVector to a stream 865ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlintemplate <unsigned ElementSize> 8663f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbarvoid dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) { 8673422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << "["; 8683422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby 8693422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(), 8703422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby be = LHS.end(); 8713422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby if (bi != be) { 8723422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << *bi; 8733422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby for (++bi; bi != be; ++bi) { 8743422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << " " << *bi; 8753422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby } 876ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin } 8773422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << "]\n"; 8782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin} 8793ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} // end namespace llvm 880d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 8812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#endif 882