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) 140c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 14150bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 142c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros(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. 1611144af3c9b4da48cd581156e05b24261c8de366aRichard Smith Copy &= ~0UL << BitPos; 1622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Copy != 0) { 1642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 165c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); 16650bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 167c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return WordPos * BITWORD_SIZE + countTrailingZeros(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) 175c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); 17650bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper if (sizeof(BitWord) == 8) 177c6af2432c802d241c8fffbe0371c023e6c58844eMichael J. Spencer return i * BITWORD_SIZE + countTrailingZeros(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 265deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramertemplate <unsigned ElementSize> 266deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramerstruct ilist_traits<SparseBitVectorElement<ElementSize> > 267deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer : public ilist_default_traits<SparseBitVectorElement<ElementSize> > { 268deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer typedef SparseBitVectorElement<ElementSize> Element; 269deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer 270deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer Element *createSentinel() const { return static_cast<Element *>(&Sentinel); } 271deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer static void destroySentinel(Element *) {} 272deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer 273deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer Element *provideInitialHead() const { return createSentinel(); } 274deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer Element *ensureHead(Element *) const { return createSentinel(); } 275deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer static void noteHead(Element *, Element *) {} 276deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer 277deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramerprivate: 278deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer mutable ilist_half_node<Element> Sentinel; 279deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer}; 280deda7b6e75b1796ef1a6d22b395098ffcbf32435Benjamin Kramer 2812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlintemplate <unsigned ElementSize = 128> 2822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinclass SparseBitVector { 2836320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin typedef ilist<SparseBitVectorElement<ElementSize> > ElementList; 2842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::iterator ElementListIter; 2852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::const_iterator ElementListConstIter; 2862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin enum { 2872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE 2882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 2892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Pointer to our current Element. 2912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter CurrElementIter; 2922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementList Elements; 2932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // This is like std::lower_bound, except we do linear searching from the 2952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // current position. 2962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter FindLowerBound(unsigned ElementIndex) { 2972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 2992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 3002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Elements.begin(); 3012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Make sure our current iterator is valid. 3042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (CurrElementIter == Elements.end()) 3052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --CurrElementIter; 3062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Search from our current iterator, either backwards or forwards, 3082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // depending on what element we are looking for. 3092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = CurrElementIter; 3106320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (CurrElementIter->index() == ElementIndex) { 3112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 3126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (CurrElementIter->index() > ElementIndex) { 3132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.begin() 3146320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin && ElementIter->index() > ElementIndex) 3152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --ElementIter; 3162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 3172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.end() && 318c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter->index() < ElementIndex) 3192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++ElementIter; 3202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = ElementIter; 3222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 3232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Iterator to walk set bits in the bitmap. This iterator is a lot uglier 3262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // than it would be, in order to be efficient. 3271b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin class SparseBitVectorIterator { 3282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin private: 3292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool AtEnd; 3302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3311b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *BitVector; 3322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current element inside of bitmap. 3342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter; 3352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bit number inside of our bitmap. 3372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned BitNumber; 3382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current word number inside of our element. 3402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned WordNumber; 3412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bits from the element. 3432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typename SparseBitVectorElement<ElementSize>::BitWord Bits; 3442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the first non-zero bit in the bitmap. 3462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToFirstNonZero() { 3472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BitVector->Elements.empty()) { 3502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 3512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 3546320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 3556320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin unsigned BitPos = Iter->find_first(); 3562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += BitPos; 3572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 3586320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= BitPos % BITWORD_SIZE; 3602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3612f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the next non-zero bit. 3632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToNextNonZero() { 3642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Bits && !(Bits & 1)) { 3682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 3692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += 1; 3702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // See if we ran out of Bits in this word. 3732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (!Bits) { 37408bb6998437528143934de9c76fa312e48e58896Daniel Berlin int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ; 3752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we ran out of set bits in this element, move to next element. 3762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) { 37716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter; 3782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = 0; 3792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // We may run out of elements in the bitmap. 3811b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter == BitVector->Elements.end()) { 3822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 3832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Set up for next non zero word in bitmap. 3866320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 3876320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NextSetBitNumber = Iter->find_first(); 3882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += NextSetBitNumber; 3892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 3906320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 3922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 3932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE; 3946320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 396430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber = Iter->index() * ElementSize; 397430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber += NextSetBitNumber; 3982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin public: 4022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Preincrement. 4032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator& operator++() { 40416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++BitNumber; 4052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 4062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToNextNonZero(); 4072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return *this; 4082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Postincrement. 4112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator operator++(int) { 4122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVectorIterator tmp = *this; 4132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++*this; 4142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return tmp; 4152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Return the current set bit number. 4182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned operator*() const { 4192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return BitNumber; 4202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator==(const SparseBitVectorIterator &RHS) const { 4232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If they are both at the end, ignore the rest of the fields. 4249f711252f5d5ef4e05f5277ab462bf7668b53cfdDaniel Berlin if (AtEnd && RHS.AtEnd) 4252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 4262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Otherwise they are the same if they have the same bit number and 4272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // bitmap. 4282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber; 4292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator!=(const SparseBitVectorIterator &RHS) const { 4312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return !(*this == RHS); 4322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 43316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorIterator(): BitVector(NULL) { 4341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 43516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 43616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 4371b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS, 4381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool end = false):BitVector(RHS) { 4391b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 4402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber = 0; 4412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits = 0; 4422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = ~0; 4432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = end; 4442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToFirstNonZero(); 4452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 4472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 4482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef SparseBitVectorIterator iterator; 4492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector () { 4512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4532f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ~SparseBitVector() { 4552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // SparseBitVector copy ctor. 4582f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector(const SparseBitVector &RHS) { 4592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter ElementIter = RHS.Elements.begin(); 4602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != RHS.Elements.end()) { 4616320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 4626320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++ElementIter; 4632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4683ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner // Clear. 4693ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner void clear() { 4703ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Elements.clear(); 4713ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner } 4723ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 473412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson // Assignment 474412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson SparseBitVector& operator=(const SparseBitVector& RHS) { 475412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson Elements.clear(); 4763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 477412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson ElementListConstIter ElementIter = RHS.Elements.begin(); 478412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson while (ElementIter != RHS.Elements.end()) { 479412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 480412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson ++ElementIter; 481412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson } 482412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson 483412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson CurrElementIter = Elements.begin (); 4843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 485412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson return *this; 486412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson } 4872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Test, Reset, and Set a bit in the bitmap. 4892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test(unsigned Idx) { 4902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 4912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 4922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 4942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 4952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 4972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 4982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 4996320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 5002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 5016320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return ElementIter->test(Idx % ElementSize); 5022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void reset(unsigned Idx) { 5052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 5062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 5072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 5092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 5102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 5122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 5132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 5146320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 5152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 5166320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->reset(Idx % ElementSize); 5172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // When the element is zeroed out, delete it. 5196320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter->empty()) { 5202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++CurrElementIter; 5212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(ElementIter); 5222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void set(unsigned Idx) { 5262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 5276320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *Element; 5286320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementListIter ElementIter; 5292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 5302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 5316320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = Elements.insert(Elements.end(), Element); 5326320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 5332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 5346320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = FindLowerBound(ElementIndex); 5352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5366320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter == Elements.end() || 5376320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) { 5382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 539c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // We may have hit the beginning of our SparseBitVector, in which case, 540c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // we may need to insert right after this element, which requires moving 541c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // the current iterator forward one, because insert does insert before. 5428d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin if (ElementIter != Elements.end() && 5438d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin ElementIter->index() < ElementIndex) 544c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(++ElementIter, Element); 545c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin else 546c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(ElementIter, Element); 5472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 549c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin CurrElementIter = ElementIter; 55008bb6998437528143934de9c76fa312e48e58896Daniel Berlin 5516320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->set(Idx % ElementSize); 5522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 55316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 5541b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool test_and_set (unsigned Idx) { 5551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool old = test(Idx); 556c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin if (!old) { 5571b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin set(Idx); 558c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return true; 559c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 560c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 561c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 562c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 563d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator!=(const SparseBitVector &RHS) const { 564c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return !(*this == RHS); 565c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 566c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 567d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator==(const SparseBitVector &RHS) const { 568c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter1 = Elements.begin(); 569c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 570c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 571d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end(); 572d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin ++Iter1, ++Iter2) { 573d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin if (*Iter1 != *Iter2) 574c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 575c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 576d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return Iter1 == Elements.end() && Iter2 == RHS.Elements.end(); 5771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 5782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Union our bitmap with the RHS and return true if we changed. 5802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator|=(const SparseBitVector &RHS) { 5812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 5822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 5832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 5842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 585ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin // If RHS is empty, we are done 586ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin if (RHS.Elements.empty()) 5872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 5882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 5906320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) { 5916320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.insert(Iter1, 5926320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter2)); 59316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 5956320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 5966320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->unionWith(*Iter2); 59716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 59816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 60016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 6042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 6052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Intersect our bitmap with the RHS and return true if ours changed. 6082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator&=(const SparseBitVector &RHS) { 6092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 6102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 6112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 6122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6136320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 6146320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 6152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 6162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 61907268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 62007268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 62207268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6246320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 62516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6266320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool BecameZero; 6286320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWith(*Iter2, BecameZero); 6292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (BecameZero) { 6302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 6317f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6337f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6347f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 63616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 6382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 63916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 64316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.erase(Iter1, Elements.end()); 6442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 6452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 6462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 648b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // Intersect our bitmap with the complement of the RHS and return true 649b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // if ours changed. 6501b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector &RHS) { 6511b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool changed = false; 6521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter Iter1 = Elements.begin(); 6531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 6541b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 655c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If either our bitmap or RHS is empty, we are done 656c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (Elements.empty() || RHS.Elements.empty()) 6571b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 6581b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6591b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6601b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 66107268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 66207268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6631b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 66407268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6651b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6666320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 66716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6686320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6691b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool BecameZero; 6706320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); 6711b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BecameZero) { 6721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter IterTmp = Iter1; 6737f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6741b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Elements.erase(IterTmp); 6757f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6767f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 67816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6791b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 68016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6811b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6821b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6831b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin CurrElementIter = Elements.begin(); 6841b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 6851b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6861b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6871b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const { 6881b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersectWithComplement(*RHS); 6891b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 69016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 69116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 692b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // Three argument version of intersectWithComplement. 693b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // Result of RHS1 & ~RHS2 is stored into this bitmap. 69416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, 69516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS2) 69616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin { 69716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.clear(); 69807268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 69916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter1 = RHS1.Elements.begin(); 70016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter2 = RHS2.Elements.begin(); 70116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 702c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS1 is empty, we are done 703c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS2 is empty, we still have to copy RHS1 704c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (RHS1.Elements.empty()) 70516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 70616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 70716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 70816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter2 != RHS2.Elements.end()) { 70916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin if (Iter1 == RHS1.Elements.end()) 71016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 71116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 71316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7146320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 71516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool BecameZero = false; 71616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7176320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(Iter1->index()); 7186320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero); 7196320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (!BecameZero) { 72016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 72116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7226320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin else 7236320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin delete NewElement; 72416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 72516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 72616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } else { 727c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 728c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 729c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin Elements.push_back(NewElement); 73016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 73116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 73216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7336320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 73416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // copy the remaining elements 73516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter1 != RHS1.Elements.end()) { 73616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7376320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 73816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 7396320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++Iter1; 74016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7416320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 74216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 74316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 74416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 74516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1, 74616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS2) { 74716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin intersectWithComplement(*RHS1, *RHS2); 74816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 74916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7501b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> *RHS) const { 7511b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersects(*RHS); 7521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 75316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7541b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if we share any bits in common with RHS 7551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> &RHS) const { 7561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter1 = Elements.begin(); 7571b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 7581b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7596320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 7606320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 7611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7621b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7631b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting stopping when we hit bits in common. 7641b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 7651b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter1 == Elements.end()) 7661b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7671b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7686320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 76916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7706320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 7716320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->intersects(*Iter2)) 7721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return true; 77316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 77416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7751b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 77616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 7771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7781b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7791b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7801b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 78116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 78294c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // Return true iff all bits set in this SparseBitVector are 783b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby // also set in RHS. 784b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby bool contains(const SparseBitVector<ElementSize> &RHS) const { 785b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby SparseBitVector<ElementSize> Result(*this); 786b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby Result &= RHS; 787b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby return (Result == RHS); 788b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby } 789b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby 7901b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return the first set bit in the bitmap. Return -1 if no bits are set. 7911b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin int find_first() const { 7921b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Elements.empty()) 7931b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return -1; 7946320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); 7956320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return (First.index() * ElementSize) + First.find_first(); 7961b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7971b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7981b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if the SparseBitVector is empty 7991b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool empty() const { 8001b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return Elements.empty(); 8011b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 80216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 8031b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned count() const { 8041b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned BitCount = 0; 8051b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (ElementListConstIter Iter = Elements.begin(); 8061b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter != Elements.end(); 8071b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ++Iter) 8086320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitCount += Iter->count(); 80916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 8101b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return BitCount; 8111b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 8122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator begin() const { 8131b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return iterator(this); 8142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 8152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 8162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator end() const { 817729bd28f62d83c9681702264a79c4ab03c7c11ecHartmut Kaiser return iterator(this, true); 8182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 8192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin}; 8201b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8211b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin// Convenience functions to allow Or and And without dereferencing in the user 82216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin// code. 82316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 8241b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 82516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> &LHS, 82616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS) { 82716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS |= *RHS; 8281b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8291b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8301b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 83116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> *LHS, 83216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS) { 83316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator|=(RHS); 8341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8351b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8361b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 83716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> *LHS, 8381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> &RHS) { 83916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator&=(RHS); 8401b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8411b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8421b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 84316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> &LHS, 8441b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *RHS) { 8453ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return LHS &= *RHS; 8463ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8473ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8483ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner// Convenience functions for infix union, intersection, difference operators. 8493ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8503ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8513ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8523ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator|(const SparseBitVector<ElementSize> &LHS, 8533ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8543ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result(LHS); 8553ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result |= RHS; 8563ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8573ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8583ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8593ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8603ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8613ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator&(const SparseBitVector<ElementSize> &LHS, 8623ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8633ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result(LHS); 8643ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result &= RHS; 8653ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8663ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8673ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8683ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8693ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8703ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator-(const SparseBitVector<ElementSize> &LHS, 8713ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8723ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result; 8733ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result.intersectWithComplement(LHS, RHS); 8743ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8751b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8767f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin 877ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin 878b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby 879b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461eJohn Mosby 880ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin// Dump a SparseBitVector to a stream 881ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlintemplate <unsigned ElementSize> 8823f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbarvoid dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) { 8833422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << "["; 8843422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby 8853422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(), 8863422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby be = LHS.end(); 8873422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby if (bi != be) { 8883422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << *bi; 8893422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby for (++bi; bi != be; ++bi) { 8903422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << " " << *bi; 8913422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby } 892ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin } 8933422cf05a8a4817c6c525ef4d66026761ec590c1John Mosby out << "]\n"; 8942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin} 8953ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} // end namespace llvm 896d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 8972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#endif 898