SparseBitVector.h revision acddf9d019316ac1735667dc92d96092e9f5bf2e
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 <algorithm> 212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include "llvm/Support/DataTypes.h" 222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include "llvm/ADT/STLExtras.h" 232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#include "llvm/Support/MathExtras.h" 246320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin#include "llvm/ADT/ilist" 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> 422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinstruct SparseBitVectorElement { 432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef unsigned long BitWord; 452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin enum { 462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORD_SIZE = sizeof(BitWord) * 8, 472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, 482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITS_PER_ELEMENT = ElementSize 492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 506320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 516320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *getNext() const { 526320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return Next; 536320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } 546320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *getPrev() const { 556320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return Prev; 566320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } 576320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 586320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin void setNext(SparseBitVectorElement<ElementSize> *RHS) { 596320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Next = RHS; 606320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } 616320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin void setPrev(SparseBitVectorElement<ElementSize> *RHS) { 626320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Prev = RHS; 636320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } 646320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinprivate: 666320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *Next; 676320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *Prev; 682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Index of Element in terms of where first bit starts. 692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex; 702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord Bits[BITWORDS_PER_ELEMENT]; 716320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Needed for sentinels 726320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement() { 73acddf9d019316ac1735667dc92d96092e9f5bf2eScott Michel ElementIndex = ~0U; 746320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 756320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } 766320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 776320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin friend struct ilist_traits<SparseBitVectorElement<ElementSize> >; 782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin explicit SparseBitVectorElement(unsigned Idx) { 802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementIndex = Idx; 812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); 822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ~SparseBitVectorElement() { 852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Copy ctor. 882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVectorElement(const SparseBitVectorElement &RHS) { 892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementIndex = RHS.ElementIndex; 902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits); 912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Comparison. 942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator==(const SparseBitVectorElement &RHS) const { 952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIndex != RHS.ElementIndex) 962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != RHS.Bits[i]) 992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 1002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 1012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator!=(const SparseBitVectorElement &RHS) const { 1042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return !(*this == RHS); 1052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Return the bits that make up word Idx in our element. 1082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord word(unsigned Idx) const { 1092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert (Idx < BITWORDS_PER_ELEMENT); 1102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Bits[Idx]; 1112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned index() const { 1142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIndex; 1152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool empty() const { 1182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 1192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i]) 1202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 1212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 1222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void set(unsigned Idx) { 1252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); 1262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test_and_set (unsigned Idx) { 1292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool old = test(Idx); 130c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin if (!old) { 1312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin set(Idx); 132c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return true; 133c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 134c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 1352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void reset(unsigned Idx) { 1382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); 1392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test(unsigned Idx) const { 1422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE)); 1432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned count() const { 1462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned NumBits = 0; 1472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 1482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin NumBits += CountPopulation_32(Bits[i]); 1502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin NumBits += CountPopulation_64(Bits[i]); 1522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 1532f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 1542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return NumBits; 1552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin /// find_first - Returns the index of the first set bit. 1582f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin int find_first() const { 1592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) 1602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) { 1612f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 1632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 1652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 1662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 1672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Illegal empty element"); 1692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 17108bb6998437528143934de9c76fa312e48e58896Daniel Berlin /// find_next - Returns the index of the next set bit starting from the 17208bb6998437528143934de9c76fa312e48e58896Daniel Berlin /// "Curr" bit. Returns -1 if the next set bit is not found. 17308bb6998437528143934de9c76fa312e48e58896Daniel Berlin int find_next(unsigned Curr) const { 17408bb6998437528143934de9c76fa312e48e58896Daniel Berlin if (Curr >= BITS_PER_ELEMENT) 1752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return -1; 1762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 17708bb6998437528143934de9c76fa312e48e58896Daniel Berlin unsigned WordPos = Curr / BITWORD_SIZE; 17808bb6998437528143934de9c76fa312e48e58896Daniel Berlin unsigned BitPos = Curr % BITWORD_SIZE; 1792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord Copy = Bits[WordPos]; 1802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert (WordPos <= BITWORDS_PER_ELEMENT 1812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin && "Word Position outside of element"); 1822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Mask off previous bits. 1842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Copy &= ~0L << BitPos; 1852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Copy != 0) { 1872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy); 1892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 1902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); 1912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 1922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 1932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 1942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 1952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Check subsequent words. 1962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) 1972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) { 1982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (sizeof(BitWord) == 4) 1992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); 2002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else if (sizeof(BitWord) == 8) 2012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); 2022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin else 2032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin assert(0 && "Unsupported!"); 2042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return -1; 2062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Union this element with RHS and return true if this one changed. 2092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool unionWith(const SparseBitVectorElement &RHS) { 2102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 2112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord old = changed ? 0 : Bits[i]; 2132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[i] |= RHS.Bits[i]; 2157f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 2162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 2172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 2192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2211b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if we have any bits in common with RHS 2221b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVectorElement &RHS) const { 2231b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2241b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (RHS.Bits[i] & Bits[i]) 22516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return true; 2261b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 2271b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 2281b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 22916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 2302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Intersect this Element with RHS and return true if this one changed. 2312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // BecameZero is set to true if this element became all-zero bits. 2322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool intersectWith(const SparseBitVectorElement &RHS, 2332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool &BecameZero) { 2342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 2352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool allzero = true; 2362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BecameZero = false; 2382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitWord old = changed ? 0 : Bits[i]; 2402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits[i] &= RHS.Bits[i]; 2422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Bits[i] != 0) 2432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin allzero = false; 2442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2457f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 2462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 2472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2487f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 2492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 2502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 2511b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Intersect this Element with the complement of RHS and return true if this 2521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // one changed. BecameZero is set to true if this element became all-zero 2531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // bits. 2541b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVectorElement &RHS, 2557f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin bool &BecameZero) { 2561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool changed = false; 2571b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool allzero = true; 2581b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2591b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin BecameZero = false; 2601b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 2611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin BitWord old = changed ? 0 : Bits[i]; 2621b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2631b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Bits[i] &= ~RHS.Bits[i]; 2641b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Bits[i] != 0) 2651b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin allzero = false; 2661b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 2677f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin if (!changed && old != Bits[i]) 2681b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin changed = true; 2691b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 2707f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 2711b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 2721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 27316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Three argument version of intersectWithComplement that intersects 27416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // RHS1 & ~RHS2 into this element 27516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVectorElement &RHS1, 27616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVectorElement &RHS2, 27716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool &BecameZero) { 27816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool allzero = true; 27916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 28016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin BecameZero = false; 28116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 28216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i]; 28316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin if (Bits[i] != 0) 28416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin allzero = false; 28516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 2867f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin BecameZero = allzero; 28716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 288e6f0479aee718e976fc077507ff6442a58325824Daniel Berlin 289d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin // Get a hash value for this element; 290d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t getHashValue() const { 291d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t HashVal = 0; 292d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { 293d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin HashVal ^= Bits[i]; 294d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 295d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return HashVal; 296d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 2972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin}; 2982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 2992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlintemplate <unsigned ElementSize = 128> 3002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinclass SparseBitVector { 3016320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin typedef ilist<SparseBitVectorElement<ElementSize> > ElementList; 3022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::iterator ElementListIter; 3032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef typename ElementList::const_iterator ElementListConstIter; 3042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin enum { 3052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE 3062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 3072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Pointer to our current Element. 3092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter CurrElementIter; 3102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementList Elements; 3112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3122f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // This is like std::lower_bound, except we do linear searching from the 3132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // current position. 3142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter FindLowerBound(unsigned ElementIndex) { 3152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 3172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 3182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return Elements.begin(); 3192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Make sure our current iterator is valid. 3222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (CurrElementIter == Elements.end()) 3232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --CurrElementIter; 3242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Search from our current iterator, either backwards or forwards, 3262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // depending on what element we are looking for. 3272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = CurrElementIter; 3286320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (CurrElementIter->index() == ElementIndex) { 3292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 3306320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (CurrElementIter->index() > ElementIndex) { 3312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.begin() 3326320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin && ElementIter->index() > ElementIndex) 3332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin --ElementIter; 3342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 3352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != Elements.end() && 336c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter->index() < ElementIndex) 3372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++ElementIter; 3382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = ElementIter; 3402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return ElementIter; 3412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Iterator to walk set bits in the bitmap. This iterator is a lot uglier 3442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // than it would be, in order to be efficient. 3451b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin class SparseBitVectorIterator { 3462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin private: 3472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool AtEnd; 3482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *BitVector; 3502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3512f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current element inside of bitmap. 3522f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter; 3532f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3542f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bit number inside of our bitmap. 3552f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned BitNumber; 3562f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3572f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current word number inside of our element. 3582f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned WordNumber; 3592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Current bits from the element. 3612f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typename SparseBitVectorElement<ElementSize>::BitWord Bits; 3622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the first non-zero bit in the bitmap. 3642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToFirstNonZero() { 3652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3671b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BitVector->Elements.empty()) { 3682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 3692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3711b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 3726320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 3736320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin unsigned BitPos = Iter->find_first(); 3742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += BitPos; 3752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 3766320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 3772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= BitPos % BITWORD_SIZE; 3782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Move our iterator to the next non-zero bit. 3812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void AdvanceToNextNonZero() { 3822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (AtEnd) 3832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 3842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Bits && !(Bits & 1)) { 3862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 3872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += 1; 3882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 3892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // See if we ran out of Bits in this word. 3912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (!Bits) { 39208bb6998437528143934de9c76fa312e48e58896Daniel Berlin int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ; 3932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we ran out of set bits in this element, move to next element. 3942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) { 39516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter; 3962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = 0; 3972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 3982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // We may run out of elements in the bitmap. 3991b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter == BitVector->Elements.end()) { 4002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = true; 4012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 4022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Set up for next non zero word in bitmap. 4046320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitNumber = Iter->index() * ElementSize; 4056320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NextSetBitNumber = Iter->find_first(); 4062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber += NextSetBitNumber; 4072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; 4086320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 4092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 4102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 4112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE; 4126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Bits = Iter->word(WordNumber); 4132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= NextSetBitNumber % BITWORD_SIZE; 414430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber = Iter->index() * ElementSize; 415430817ba181071d20f5c7c3ec4dcd5d8b8e318f4Daniel Berlin BitNumber += NextSetBitNumber; 4162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4172f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin public: 4202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Preincrement. 4212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator& operator++() { 42216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++BitNumber; 4232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits >>= 1; 4242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToNextNonZero(); 4252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return *this; 4262f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Postincrement. 4292f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin inline SparseBitVectorIterator operator++(int) { 4302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVectorIterator tmp = *this; 4312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++*this; 4322f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return tmp; 4332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4342f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Return the current set bit number. 4362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned operator*() const { 4372f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return BitNumber; 4382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator==(const SparseBitVectorIterator &RHS) const { 4412f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If they are both at the end, ignore the rest of the fields. 4429f711252f5d5ef4e05f5277ab462bf7668b53cfdDaniel Berlin if (AtEnd && RHS.AtEnd) 4432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return true; 4442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Otherwise they are the same if they have the same bit number and 4452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // bitmap. 4462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber; 4472f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4482f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator!=(const SparseBitVectorIterator &RHS) const { 4492f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return !(*this == RHS); 4502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 45116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorIterator(): BitVector(NULL) { 4521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 45316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 45416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 4551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS, 4561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool end = false):BitVector(RHS) { 4571b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter = BitVector->Elements.begin(); 4582f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin BitNumber = 0; 4592f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Bits = 0; 4602f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin WordNumber = ~0; 4612f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AtEnd = end; 4622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin AdvanceToFirstNonZero(); 4632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4642f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin }; 4652f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlinpublic: 4662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin typedef SparseBitVectorIterator iterator; 4672f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4682f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector () { 4692f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4702f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4712f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4722f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ~SparseBitVector() { 4732f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4742f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4752f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // SparseBitVector copy ctor. 4762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin SparseBitVector(const SparseBitVector &RHS) { 4772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter ElementIter = RHS.Elements.begin(); 4782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (ElementIter != RHS.Elements.end()) { 4796320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); 4806320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++ElementIter; 4812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4832f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin (); 4842f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 4852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Test, Reset, and Set a bit in the bitmap. 4872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool test(unsigned Idx) { 4882f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 4892f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 4902f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4912f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 4922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 4932f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 4942f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 4952f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 4962f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 4976320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 4982f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 4996320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return ElementIter->test(Idx % ElementSize); 5002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void reset(unsigned Idx) { 5032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) 5042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 5052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 5072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter ElementIter = FindLowerBound(ElementIndex); 5082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // If we can't find an element that is supposed to contain this bit, there 5102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // is nothing more to do. 5112f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (ElementIter == Elements.end() || 5126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) 5132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return; 5146320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->reset(Idx % ElementSize); 5152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // When the element is zeroed out, delete it. 5176320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter->empty()) { 5182f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ++CurrElementIter; 5192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(ElementIter); 5202f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5222f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5232f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin void set(unsigned Idx) { 5242f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin unsigned ElementIndex = Idx / ElementSize; 5256320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin SparseBitVectorElement<ElementSize> *Element; 5266320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementListIter ElementIter; 5272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (Elements.empty()) { 5282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 5296320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = Elements.insert(Elements.end(), Element); 5306320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 5312f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 5326320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter = FindLowerBound(ElementIndex); 5332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5346320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (ElementIter == Elements.end() || 5356320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->index() != ElementIndex) { 5362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Element = new SparseBitVectorElement<ElementSize>(ElementIndex); 537c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // We may have hit the beginning of our SparseBitVector, in which case, 538c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // we may need to insert right after this element, which requires moving 539c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin // the current iterator forward one, because insert does insert before. 5408d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin if (ElementIter != Elements.end() && 5418d69b5a1137debfe11e9073c4edb99d477387072Daniel Berlin ElementIter->index() < ElementIndex) 542c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(++ElementIter, Element); 543c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin else 544c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin ElementIter = Elements.insert(ElementIter, Element); 5452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 5462f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 547c3a32d190c458fa14c4a6333c942e0aefd56da7eDaniel Berlin CurrElementIter = ElementIter; 54808bb6998437528143934de9c76fa312e48e58896Daniel Berlin 5496320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ElementIter->set(Idx % ElementSize); 5502f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 55116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 5521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool test_and_set (unsigned Idx) { 5531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool old = test(Idx); 554c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin if (!old) { 5551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin set(Idx); 556c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return true; 557c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 558c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 559c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 560c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 561d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator!=(const SparseBitVector &RHS) const { 562c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return !(*this == RHS); 563c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 564c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 565d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin bool operator==(const SparseBitVector &RHS) const { 566c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter1 = Elements.begin(); 567c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 568c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin 569d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end(); 570d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin ++Iter1, ++Iter2) { 571d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin if (*Iter1 != *Iter2) 572c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin return false; 573c6d939818b7c50f6e14d04447657e670aedc3f6fDaniel Berlin } 574d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return Iter1 == Elements.end() && Iter2 == RHS.Elements.end(); 5751b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 5762f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5772f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Union our bitmap with the RHS and return true if we changed. 5782f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator|=(const SparseBitVector &RHS) { 5792f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 5802f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 5812f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 5822f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 583ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin // If RHS is empty, we are done 584ad92c633c7845e3a8103db5a9ae9231c03b9fb58Daniel Berlin if (RHS.Elements.empty()) 5852f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 5862f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 5872f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 5886320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) { 5896320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin Elements.insert(Iter1, 5906320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter2)); 59116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5922f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin changed = true; 5936320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 5946320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->unionWith(*Iter2); 59516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 59616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 5972f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 59816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 5992f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6002f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6012f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 6022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 6032f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Intersect our bitmap with the RHS and return true if ours changed. 6062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool operator&=(const SparseBitVector &RHS) { 6072f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool changed = false; 6082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter Iter1 = Elements.begin(); 6092f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 6102f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6116320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 6126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 6132f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return false; 6142f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6152f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6162f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin while (Iter2 != RHS.Elements.end()) { 61707268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 61807268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6192f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 62007268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6226320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 62316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6246320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6252f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin bool BecameZero; 6266320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWith(*Iter2, BecameZero); 6272f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin if (BecameZero) { 6282f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 6297f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6302f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6317f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6327f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6332f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 63416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6352f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } else { 6362f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin ElementListIter IterTmp = Iter1; 63716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6382f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin Elements.erase(IterTmp); 6392f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6402f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 64116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.erase(Iter1, Elements.end()); 6422f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin CurrElementIter = Elements.begin(); 6432f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin return changed; 6442f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 6452f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 6461b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Intersect our bitmap with the complement of the RHS and return true if ours 6471b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // changed. 6481b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector &RHS) { 6491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool changed = false; 6501b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter Iter1 = Elements.begin(); 6511b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 6521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 653c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If either our bitmap or RHS is empty, we are done 654c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (Elements.empty() || RHS.Elements.empty()) 6551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 6561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6571b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 6581b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 65907268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin if (Iter1 == Elements.end()) { 66007268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 6611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 66207268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin } 6631b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6646320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 66516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6666320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 6671b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool BecameZero; 6686320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); 6691b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (BecameZero) { 6701b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListIter IterTmp = Iter1; 6717f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6721b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Elements.erase(IterTmp); 6737f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin } else { 6747f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin ++Iter1; 6751b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 67616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 6771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 67816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 6791b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6801b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6811b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin CurrElementIter = Elements.begin(); 6821b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return changed; 6831b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 6841b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 6851b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const { 6861b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersectWithComplement(*RHS); 6871b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 68816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 68916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 69016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Three argument version of intersectWithComplement. Result of RHS1 & ~RHS2 69116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // is stored into this bitmap. 69216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, 69316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS2) 69416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin { 69516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.clear(); 69607268172ff6ef736cccb1b6c92cc9825f9f8cae4Daniel Berlin CurrElementIter = Elements.begin(); 69716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter1 = RHS1.Elements.begin(); 69816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ElementListConstIter Iter2 = RHS2.Elements.begin(); 69916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 700c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS1 is empty, we are done 701c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin // If RHS2 is empty, we still have to copy RHS1 702c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin if (RHS1.Elements.empty()) 70316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 70416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 70516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // Loop through, intersecting as we go, erasing elements when necessary. 70616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter2 != RHS2.Elements.end()) { 70716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin if (Iter1 == RHS1.Elements.end()) 70816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 70916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7106320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 71116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7126320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 71316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin bool BecameZero = false; 71416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7156320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(Iter1->index()); 7166320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero); 7176320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (!BecameZero) { 71816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 71916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7206320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin else 7216320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin delete NewElement; 72216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 72316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 72416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } else { 725c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 726c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 727c27d61d3ae820c6b265900380487cb74fb53510cDaniel Berlin Elements.push_back(NewElement); 72816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 72916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 73016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7316320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 73216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin // copy the remaining elements 73316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin while (Iter1 != RHS1.Elements.end()) { 73416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin SparseBitVectorElement<ElementSize> *NewElement = 7356320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin new SparseBitVectorElement<ElementSize>(*Iter1); 73616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin Elements.push_back(NewElement); 7376320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin ++Iter1; 73816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 7396320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 74016ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return; 74116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 74216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 74316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1, 74416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS2) { 74516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin intersectWithComplement(*RHS1, *RHS2); 74616ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin } 74716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7481b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> *RHS) const { 7491b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return intersects(*RHS); 7501b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 75116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7521b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if we share any bits in common with RHS 7531b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool intersects(const SparseBitVector<ElementSize> &RHS) const { 7541b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter1 = Elements.begin(); 7551b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ElementListConstIter Iter2 = RHS.Elements.begin(); 7561b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7576320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin // Check if both bitmaps are empty. 7586320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Elements.empty() && RHS.Elements.empty()) 7591b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7601b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7611b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Loop through, intersecting stopping when we hit bits in common. 7621b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin while (Iter2 != RHS.Elements.end()) { 7631b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Iter1 == Elements.end()) 7641b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7651b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7666320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->index() > Iter2->index()) { 76716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7686320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin } else if (Iter1->index() == Iter2->index()) { 7696320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin if (Iter1->intersects(*Iter2)) 7701b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return true; 77116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 77216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter2; 7731b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } else { 77416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin ++Iter1; 7751b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7761b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7771b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return false; 7781b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 77916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7801b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return the first set bit in the bitmap. Return -1 if no bits are set. 7811b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin int find_first() const { 7821b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin if (Elements.empty()) 7831b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return -1; 7846320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); 7856320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin return (First.index() * ElementSize) + First.find_first(); 7861b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 7871b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 7881b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin // Return true if the SparseBitVector is empty 7891b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin bool empty() const { 7901b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return Elements.empty(); 7911b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 79216ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 7931b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned count() const { 7941b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin unsigned BitCount = 0; 7951b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin for (ElementListConstIter Iter = Elements.begin(); 7961b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin Iter != Elements.end(); 7971b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin ++Iter) 7986320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin BitCount += Iter->count(); 79916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 8001b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return BitCount; 8011b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin } 8022f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator begin() const { 8031b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin return iterator(this); 8042f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 8052f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 8062f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin iterator end() const { 807729bd28f62d83c9681702264a79c4ab03c7c11ecHartmut Kaiser return iterator(this, true); 8082f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin } 8096320260e060ce4fc5d199d757b15a0f43be66029Daniel Berlin 810d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin // Get a hash value for this bitmap. 811d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t getHashValue() const { 812d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin uint64_t HashVal = 0; 813d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin for (ElementListConstIter Iter = Elements.begin(); 814d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin Iter != Elements.end(); 815d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin ++Iter) { 816d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin HashVal ^= Iter->index(); 817d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin HashVal ^= Iter->getHashValue(); 818d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 819d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin return HashVal; 820d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin } 8212f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin}; 8221b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8231b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin// Convenience functions to allow Or and And without dereferencing in the user 82416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin// code. 82516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin 8261b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 82716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> &LHS, 82816ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> *RHS) { 82916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS |= *RHS; 8301b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8311b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8321b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 83316ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator |=(SparseBitVector<ElementSize> *LHS, 83416ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin const SparseBitVector<ElementSize> &RHS) { 83516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator|=(RHS); 8361b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8371b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8381b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 83916ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> *LHS, 8401b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> &RHS) { 84116ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS->operator&=(RHS); 8421b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8431b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin 8441b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlintemplate <unsigned ElementSize> 84516ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlininline bool operator &=(SparseBitVector<ElementSize> &LHS, 8461b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin const SparseBitVector<ElementSize> *RHS) { 84716ebc260bd374daa4323c78ffefc87aec485f29dDaniel Berlin return LHS &= (*RHS); 8481b6998e8d6807d3e0b6d4904111f43738ceae5e6Daniel Berlin} 8497f44657c2f4409416a083a9e63d2b4ea7cdca43eDaniel Berlin 850ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin 851ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin// Dump a SparseBitVector to a stream 852ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlintemplate <unsigned ElementSize> 853ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlinvoid dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) { 854ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin out << "[ "; 855ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin 856ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin typename SparseBitVector<ElementSize>::iterator bi; 857ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin for (bi = LHS.begin(); bi != LHS.end(); ++bi) { 858ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin out << *bi << " "; 859ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin } 860d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin out << " ]\n"; 861ec39cb98d38bc0474a9ba207bcee31718db0e178Daniel Berlin} 8622f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin} 8632f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin 864d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 865d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 8662f5d5937eccfaa17c01ab5136bfde20f2f6d767cDaniel Berlin#endif 867