SparseBitVector.h revision 3ee87b6f9da0f63762ffaf0c4fcbc39514a059fb
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 182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include <cassert> 192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include <cstring> 202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include "llvm/Support/DataTypes.h" 212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include "llvm/ADT/STLExtras.h" 222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include "llvm/Support/MathExtras.h" 2343d1fd449f1a0ac9d9dafa0b9569bb6b2e976198Anton Korobeynikov#include "llvm/ADT/ilist.h" 24d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman 252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinnamespace llvm { 262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// SparseBitVector is an implementation of a bitvector that is sparse by only 282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// storing the elements that have non-zero bits set. In order to make this 292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// fast for the most common cases, SparseBitVector is implemented as a linked 302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// list of SparseBitVectorElements. We maintain a pointer to the last 312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// SparseBitVectorElement accessed (in the form of a list iterator), in order 322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// to make multiple in-order test/set constant time after the first one is 332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// executed. Note that using vectors to store SparseBitVectorElement's does 342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// not work out very well because it causes insertion in the middle to take 352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// enormous amounts of time with a large amount of bits. Other structures that 362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// have better worst cases for insertion in the middle (various balanced trees, 372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// etc) do not perform as well in practice as a linked list with this iterator 382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin/// kept up to date. They are also significantly more memory intensive. 392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlintemplate <unsigned ElementSize = 128> 42fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanstruct SparseBitVectorElement 43fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman : ilist_node<SparseBitVectorElement<ElementSize> > { 442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef unsigned long BitWord; 462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin enum { 472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORD_SIZE = sizeof(BitWord) * 8, 482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, 492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITS_PER_ELEMENT = ElementSize 502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 516320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinprivate: 532f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Index of Element in terms of where first bit starts. 542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex; 552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord Bits[BITWORDS_PER_ELEMENT]; 566320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Needed for sentinels 57fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman friend class ilist_sentinel_traits<SparseBitVectorElement>; 586320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement() { 59acddf9d019316ac1735667dc92d96092e9f5bf2eScott Michel ElementIndex = ~0U; 606320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 616320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } 626320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin explicit SparseBitVectorElement(unsigned Idx) { 652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementIndex = Idx; 662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Comparison. 702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator==(const SparseBitVectorElement &RHS) const { 712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIndex != RHS.ElementIndex) 722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != RHS.Bits[i]) 752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator!=(const SparseBitVectorElement &RHS) const { 802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return !(*this == RHS); 812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Return the bits that make up word Idx in our element. 842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord word(unsigned Idx) const { 852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert (Idx < BITWORDS_PER_ELEMENT); 862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Bits[Idx]; 872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned index() const { 902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIndex; 912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool empty() const { 942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i]) 962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void set(unsigned Idx) { 1012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 1022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test_and_set (unsigned Idx) { 1052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool old = test(Idx); 106c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin if (!old) { 1072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin set(Idx); 108c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return true; 109c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 110c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 1112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void reset(unsigned Idx) { 1142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 1152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test(unsigned Idx) const { 1182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE)); 1192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned count() const { 1222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned NumBits = 0; 1232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 1242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin NumBits += CountPopulation_32(Bits[i]); 1262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin NumBits += CountPopulation_64(Bits[i]); 1282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 1292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 1302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return NumBits; 1312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin /// find_first - Returns the index of the first set bit. 1342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin int find_first() const { 1352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 1362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) { 1372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 1392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 1412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 1422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 1432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Illegal empty element"); 145d27c991cebe48fdf82b5d9eec6c2a1a244f82622Chris Lattner return 0; // Not reached 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); 1662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 1682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 1692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 1702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Check subsequent words. 1732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) 1742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) { 1752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 1772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 1792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 1802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 1812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return -1; 1832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Union this element with RHS and return true if this one changed. 1862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool unionWith(const SparseBitVectorElement &RHS) { 1872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 1882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 1892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord old = changed ? 0 : Bits[i]; 1902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[i] |= RHS.Bits[i]; 1927f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 1932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 1942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 1962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1981b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if we have any bits in common with RHS 1991b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVectorElement &RHS) const { 2001b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2011b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (RHS.Bits[i] & Bits[i]) 20216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return true; 2031b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 2041b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 2051b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 20616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 2072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Intersect this Element with RHS and return true if this one changed. 2082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // BecameZero is set to true if this element became all-zero bits. 2092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool intersectWith(const SparseBitVectorElement &RHS, 2102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool &BecameZero) { 2112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 2122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool allzero = true; 2132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BecameZero = false; 2152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord old = changed ? 0 : Bits[i]; 2172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[i] &= RHS.Bits[i]; 2192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) 2202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin allzero = false; 2212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2227f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 2232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 2242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2257f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 2262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 2272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2281b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Intersect this Element with the complement of RHS and return true if this 2291b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // one changed. BecameZero is set to true if this element became all-zero 2301b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // bits. 2311b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVectorElement &RHS, 2327f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin bool &BecameZero) { 2331b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool changed = false; 2341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool allzero = true; 2351b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2361b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin BecameZero = false; 2371b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin BitWord old = changed ? 0 : Bits[i]; 2391b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2401b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Bits[i] &= ~RHS.Bits[i]; 2411b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Bits[i] != 0) 2421b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin allzero = false; 2431b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2447f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 2451b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin changed = true; 2461b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 2477f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 2481b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 2491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 25016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Three argument version of intersectWithComplement that intersects 25116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // RHS1 & ~RHS2 into this element 25216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVectorElement &RHS1, 25316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVectorElement &RHS2, 25416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool &BecameZero) { 25516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool allzero = true; 25616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 25716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin BecameZero = false; 25816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 25916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i]; 26016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin if (Bits[i] != 0) 26116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin allzero = false; 26216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 2637f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 26416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 265e6f0479aee718e976fc077507ff6442a58325824Daniel Berlin 266d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin // Get a hash value for this element; 267d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t getHashValue() const { 268d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t HashVal = 0; 269d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 270d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin HashVal ^= Bits[i]; 271d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 272d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return HashVal; 273d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 2742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin}; 2752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlintemplate <unsigned ElementSize = 128> 2772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinclass SparseBitVector { 2786320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin typedef ilist<SparseBitVectorElement<ElementSize> > ElementList; 2792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::iterator ElementListIter; 2802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::const_iterator ElementListConstIter; 2812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin enum { 2822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE 2832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 2842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Pointer to our current Element. 2862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter CurrElementIter; 2872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementList Elements; 2882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // This is like std::lower_bound, except we do linear searching from the 2902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // current position. 2912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter FindLowerBound(unsigned ElementIndex) { 2922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 2942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 2952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Elements.begin(); 2962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Make sure our current iterator is valid. 2992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (CurrElementIter == Elements.end()) 3002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --CurrElementIter; 3012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Search from our current iterator, either backwards or forwards, 3032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // depending on what element we are looking for. 3042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = CurrElementIter; 3056320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (CurrElementIter->index() == ElementIndex) { 3062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 3076320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (CurrElementIter->index() > ElementIndex) { 3082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.begin() 3096320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin && ElementIter->index() > ElementIndex) 3102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --ElementIter; 3112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 3122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.end() && 313c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter->index() < ElementIndex) 3142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++ElementIter; 3152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = ElementIter; 3172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 3182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Iterator to walk set bits in the bitmap. This iterator is a lot uglier 3212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // than it would be, in order to be efficient. 3221b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin class SparseBitVectorIterator { 3232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin private: 3242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool AtEnd; 3252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3261b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *BitVector; 3272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current element inside of bitmap. 3292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter; 3302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bit number inside of our bitmap. 3322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned BitNumber; 3332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current word number inside of our element. 3352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned WordNumber; 3362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bits from the element. 3382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typename SparseBitVectorElement<ElementSize>::BitWord Bits; 3392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the first non-zero bit in the bitmap. 3412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToFirstNonZero() { 3422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3441b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BitVector->Elements.empty()) { 3452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 3462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3481b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 3496320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 3506320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin unsigned BitPos = Iter->find_first(); 3512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += BitPos; 3522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 3536320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= BitPos % BITWORD_SIZE; 3552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the next non-zero bit. 3582f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToNextNonZero() { 3592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3612f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Bits && !(Bits & 1)) { 3632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 3642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += 1; 3652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // See if we ran out of Bits in this word. 3682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (!Bits) { 36908bb6998437528143934de9c76fa312e48e58896Daniel Berlin int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ; 3702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we ran out of set bits in this element, move to next element. 3712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) { 37216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter; 3732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = 0; 3742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // We may run out of elements in the bitmap. 3761b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter == BitVector->Elements.end()) { 3772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 3782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Set up for next non zero word in bitmap. 3816320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 3826320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NextSetBitNumber = Iter->find_first(); 3832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += NextSetBitNumber; 3842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 3856320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 3872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 3882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE; 3896320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 391430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber = Iter->index() * ElementSize; 392430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber += NextSetBitNumber; 3932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin public: 3972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Preincrement. 3982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator& operator++() { 39916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++BitNumber; 4002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 4012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToNextNonZero(); 4022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return *this; 4032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Postincrement. 4062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator operator++(int) { 4072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVectorIterator tmp = *this; 4082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++*this; 4092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return tmp; 4102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Return the current set bit number. 4132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned operator*() const { 4142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return BitNumber; 4152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator==(const SparseBitVectorIterator &RHS) const { 4182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If they are both at the end, ignore the rest of the fields. 4199f711252f5d5ef4e05f5277ab462bf7668b53cfdDaniel Berlin if (AtEnd && RHS.AtEnd) 4202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 4212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Otherwise they are the same if they have the same bit number and 4222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // bitmap. 4232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber; 4242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator!=(const SparseBitVectorIterator &RHS) const { 4262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return !(*this == RHS); 4272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 42816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorIterator(): BitVector(NULL) { 4291b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 43016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 43116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 4321b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS, 4331b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool end = false):BitVector(RHS) { 4341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 4352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber = 0; 4362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits = 0; 4372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = ~0; 4382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = end; 4392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToFirstNonZero(); 4402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 4422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 4432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef SparseBitVectorIterator iterator; 4442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector () { 4462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ~SparseBitVector() { 4502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // SparseBitVector copy ctor. 4532f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector(const SparseBitVector &RHS) { 4542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter ElementIter = RHS.Elements.begin(); 4552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != RHS.Elements.end()) { 4566320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 4576320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++ElementIter; 4582f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4612f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4633ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner // Clear. 4643ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner void clear() { 4653ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Elements.clear(); 4663ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner } 4673ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 468412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson // Assignment 469412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson SparseBitVector& operator=(const SparseBitVector& RHS) { 470412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson Elements.clear(); 4713a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 472412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson ElementListConstIter ElementIter = RHS.Elements.begin(); 473412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson while (ElementIter != RHS.Elements.end()) { 474412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 475412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson ++ElementIter; 476412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson } 477412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson 478412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson CurrElementIter = Elements.begin (); 4793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 480412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson return *this; 481412821284f16a683e9b734baf2b6c9b4635857f2Owen Anderson } 4822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Test, Reset, and Set a bit in the bitmap. 4842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test(unsigned Idx) { 4852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 4862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 4872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 4892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 4902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 4922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 4932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 4946320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 4952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 4966320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return ElementIter->test(Idx % ElementSize); 4972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void reset(unsigned Idx) { 5002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 5012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 5022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 5042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 5052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 5072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 5082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 5096320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 5102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 5116320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->reset(Idx % ElementSize); 5122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // When the element is zeroed out, delete it. 5146320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter->empty()) { 5152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++CurrElementIter; 5162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(ElementIter); 5172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void set(unsigned Idx) { 5212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 5226320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *Element; 5236320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementListIter ElementIter; 5242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 5252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 5266320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = Elements.insert(Elements.end(), Element); 5276320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 5282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 5296320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = FindLowerBound(ElementIndex); 5302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5316320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter == Elements.end() || 5326320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) { 5332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 534c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // We may have hit the beginning of our SparseBitVector, in which case, 535c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // we may need to insert right after this element, which requires moving 536c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // the current iterator forward one, because insert does insert before. 5378d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin if (ElementIter != Elements.end() && 5388d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin ElementIter->index() < ElementIndex) 539c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(++ElementIter, Element); 540c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin else 541c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(ElementIter, Element); 5422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 544c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin CurrElementIter = ElementIter; 54508bb6998437528143934de9c76fa312e48e58896Daniel Berlin 5466320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->set(Idx % ElementSize); 5472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 54816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 5491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool test_and_set (unsigned Idx) { 5501b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool old = test(Idx); 551c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin if (!old) { 5521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin set(Idx); 553c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return true; 554c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 555c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 556c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 557c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 558d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator!=(const SparseBitVector &RHS) const { 559c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return !(*this == RHS); 560c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 561c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 562d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator==(const SparseBitVector &RHS) const { 563c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter1 = Elements.begin(); 564c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 565c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 566d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end(); 567d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin ++Iter1, ++Iter2) { 568d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin if (*Iter1 != *Iter2) 569c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 570c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 571d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return Iter1 == Elements.end() && Iter2 == RHS.Elements.end(); 5721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 5732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Union our bitmap with the RHS and return true if we changed. 5752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator|=(const SparseBitVector &RHS) { 5762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 5772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 5782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 5792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 580ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin // If RHS is empty, we are done 581ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin if (RHS.Elements.empty()) 5822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 5832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 5856320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) { 5866320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.insert(Iter1, 5876320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter2)); 58816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 5906320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 5916320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->unionWith(*Iter2); 59216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 59316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 59516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 5962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 5992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 6002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Intersect our bitmap with the RHS and return true if ours changed. 6032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator&=(const SparseBitVector &RHS) { 6042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 6052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 6062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 6072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6086320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 6096320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 6102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 6112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 61407268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 61507268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 61707268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6196320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 62016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6216320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool BecameZero; 6236320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWith(*Iter2, BecameZero); 6242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (BecameZero) { 6252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 6267f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6287f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6297f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 63116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 6332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 63416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 63816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.erase(Iter1, Elements.end()); 6392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 6402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 6412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6431b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Intersect our bitmap with the complement of the RHS and return true if ours 6441b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // changed. 6451b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector &RHS) { 6461b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool changed = false; 6471b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter Iter1 = Elements.begin(); 6481b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 6491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 650c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If either our bitmap or RHS is empty, we are done 651c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (Elements.empty() || RHS.Elements.empty()) 6521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 6531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6541b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 65607268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 65707268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6581b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 65907268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6601b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6616320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 66216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6636320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6641b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool BecameZero; 6656320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); 6661b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BecameZero) { 6671b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter IterTmp = Iter1; 6687f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6691b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Elements.erase(IterTmp); 6707f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6717f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 67316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6741b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 67516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6761b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6781b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin CurrElementIter = Elements.begin(); 6791b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 6801b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6811b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6821b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const { 6831b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersectWithComplement(*RHS); 6841b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 68516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 68616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 68716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Three argument version of intersectWithComplement. Result of RHS1 & ~RHS2 68816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // is stored into this bitmap. 68916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, 69016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS2) 69116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin { 69216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.clear(); 69307268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 69416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter1 = RHS1.Elements.begin(); 69516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter2 = RHS2.Elements.begin(); 69616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 697c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS1 is empty, we are done 698c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS2 is empty, we still have to copy RHS1 699c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (RHS1.Elements.empty()) 70016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 70116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 70216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 70316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter2 != RHS2.Elements.end()) { 70416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin if (Iter1 == RHS1.Elements.end()) 70516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 70616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7076320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 70816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7096320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 71016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool BecameZero = false; 71116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(Iter1->index()); 7136320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero); 7146320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (!BecameZero) { 71516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 71616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7176320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin else 7186320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin delete NewElement; 71916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 72016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 72116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } else { 722c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 723c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 724c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin Elements.push_back(NewElement); 72516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 72616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 72716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7286320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 72916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // copy the remaining elements 73016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter1 != RHS1.Elements.end()) { 73116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7326320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 73316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 7346320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++Iter1; 73516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7366320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 73716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 73816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 73916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 74016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1, 74116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS2) { 74216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin intersectWithComplement(*RHS1, *RHS2); 74316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 74416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7451b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> *RHS) const { 7461b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersects(*RHS); 7471b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 74816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if we share any bits in common with RHS 7501b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> &RHS) const { 7511b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter1 = Elements.begin(); 7521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 7531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7546320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 7556320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 7561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7571b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7581b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting stopping when we hit bits in common. 7591b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 7601b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter1 == Elements.end()) 7611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7621b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7636320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 76416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7656320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 7666320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->intersects(*Iter2)) 7671b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return true; 76816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 76916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7701b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 77116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 7721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7731b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7741b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7751b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 77616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return the first set bit in the bitmap. Return -1 if no bits are set. 7781b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin int find_first() const { 7791b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Elements.empty()) 7801b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return -1; 7816320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); 7826320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return (First.index() * ElementSize) + First.find_first(); 7831b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7841b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7851b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if the SparseBitVector is empty 7861b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool empty() const { 7871b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return Elements.empty(); 7881b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 78916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7901b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned count() const { 7911b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned BitCount = 0; 7921b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (ElementListConstIter Iter = Elements.begin(); 7931b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter != Elements.end(); 7941b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ++Iter) 7956320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitCount += Iter->count(); 79616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7971b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return BitCount; 7981b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator begin() const { 8001b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return iterator(this); 8012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 8022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 8032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator end() const { 804729bd28f62d83c9681702264a79c4ab03c7c11ecHartmut Kaiser return iterator(this, true); 8052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 8066320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 807d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin // Get a hash value for this bitmap. 808d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t getHashValue() const { 809d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t HashVal = 0; 810d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (ElementListConstIter Iter = Elements.begin(); 811d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin Iter != Elements.end(); 812d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin ++Iter) { 813d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin HashVal ^= Iter->index(); 814d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin HashVal ^= Iter->getHashValue(); 815d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 816d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return HashVal; 817d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 8182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin}; 8191b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8201b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin// Convenience functions to allow Or and And without dereferencing in the user 82116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin// code. 82216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 8231b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 82416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> &LHS, 82516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS) { 82616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS |= *RHS; 8271b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8281b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8291b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 83016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> *LHS, 83116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS) { 83216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator|=(RHS); 8331b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8341b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8351b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 83616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> *LHS, 8371b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> &RHS) { 83816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator&=(RHS); 8391b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8401b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8411b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 84216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> &LHS, 8431b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *RHS) { 8443ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return LHS &= *RHS; 8453ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8463ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8473ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner// Convenience functions for infix union, intersection, difference operators. 8483ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8493ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8503ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8513ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator|(const SparseBitVector<ElementSize> &LHS, 8523ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8533ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result(LHS); 8543ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result |= RHS; 8553ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8563ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8573ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8583ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8593ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8603ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator&(const SparseBitVector<ElementSize> &LHS, 8613ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8623ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result(LHS); 8633ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result &= RHS; 8643ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8653ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} 8663ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner 8673ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnertemplate <unsigned ElementSize> 8683ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattnerinline SparseBitVector<ElementSize> 8693ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattneroperator-(const SparseBitVector<ElementSize> &LHS, 8703ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner const SparseBitVector<ElementSize> &RHS) { 8713ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner SparseBitVector<ElementSize> Result; 8723ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner Result.intersectWithComplement(LHS, RHS); 8733ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return Result; 8741b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8757f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin 876ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin 877ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin// Dump a SparseBitVector to a stream 878ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlintemplate <unsigned ElementSize> 879ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlinvoid dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) { 880ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin out << "[ "; 881ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin 882ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin typename SparseBitVector<ElementSize>::iterator bi; 883ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin for (bi = LHS.begin(); bi != LHS.end(); ++bi) { 884ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin out << *bi << " "; 885ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin } 8863ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner out << " ]\n"; 8872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin} 8883ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner} // end namespace llvm 889d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 8902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#endif 891