SVF::CoreBitVector Class Reference

#include <CoreBitVector.h>

Inheritance diagram for SVF::CoreBitVector:

Classes
class	CoreBitVectorIterator

Public Types
typedef unsigned long long	Word
typedef CoreBitVectorIterator	const_iterator
typedef const_iterator	iterator

Public Member Functions
	CoreBitVector (void)
	Construct empty CBV.
	CoreBitVector (size_t n)
	Construct empty CBV with space reserved for n Words.
	CoreBitVector (const CoreBitVector &cbv)
	Copy constructor.
	CoreBitVector (CoreBitVector &&cbv)
	Move constructor.
CoreBitVector &	operator= (const CoreBitVector &rhs)
	Copy assignment.
CoreBitVector &	operator= (CoreBitVector &&rhs)
	Move assignment.
bool	empty (void) const
	Returns true if no bits are set.
u32_t	count (void) const
	Returns number of bits set.
void	clear (void)
	Empty the CBV.
bool	test (u32_t bit) const
	Returns true if bit is set in this CBV.
bool	test_and_set (u32_t bit)
void	set (u32_t bit)
	Sets bit in the CBV.
void	reset (u32_t bit)
	Resets bit in the CBV.
bool	contains (const CoreBitVector &rhs) const
	Returns true if this CBV is a superset of rhs.
bool	intersects (const CoreBitVector &rhs) const
	Returns true if this CBV and rhs share any set bits.
bool	operator== (const CoreBitVector &rhs) const
	Returns true if this CBV and rhs have the same bits set.
bool	operator!= (const CoreBitVector &rhs) const
	Returns true if either this CBV or rhs has a bit set unique to the other.
bool	operator|= (const CoreBitVector &rhs)
bool	operator&= (const CoreBitVector &rhs)
bool	operator-= (const CoreBitVector &rhs)
bool	intersectWithComplement (const CoreBitVector &rhs)
void	intersectWithComplement (const CoreBitVector &lhs, const CoreBitVector &rhs)
	Put intersection of lhs with complement of rhs into this CBV.
size_t	hash (void) const
	Hash for this CBV.
const_iterator	begin (void) const
const_iterator	end (void) const

Static Public Attributes
static const size_t	WordSize = sizeof(Word) * CHAR_BIT

Private Member Functions
void	extendBackward (u32_t bit)
	Add enough words (prepend) to be able to include bit.
void	extendForward (u32_t bit)
	Add enough words (append) to be able to include bit.
void	extendTo (u32_t bit)
	Add enough words (append xor prepend) to be able to include bit.
size_t	indexForBit (u32_t bit) const
	Returns the index into words which would hold bit.
bool	canHold (u32_t bit) const
	Returns true if bit can fit in this CBV without resizing.
u32_t	finalBit (void) const
	Returns the last bit that this CBV can hold.
u32_t	firstCommonBit (const CoreBitVector &rhs) const
	Returns the first bit position that both this CBV and rhs can hold.
size_t	nextSetIndex (const size_t start) const

Private Attributes
u32_t	offset
	The first bit of the first word.
std::vector< Word >	words
	Our actual bit vector.

Detailed Description

A contiguous bit vector that only contains what it needs according to the operations carried. For example, when two bit vectors are unioned, their sizes may be increased to fit all the bits from the other set. This implementation never shrinks. Since points-to sets (generally) grow monotonically, does not have too big an impact on points-to analysis and so it isn't implemented. Abbreviated CBV.

Definition at line 30 of file CoreBitVector.h.

Member Typedef Documentation

const_iterator

typedef CoreBitVectorIterator SVF::CoreBitVector::const_iterator

Definition at line 37 of file CoreBitVector.h.

iterator

typedef const_iterator SVF::CoreBitVector::iterator

Definition at line 38 of file CoreBitVector.h.

Word

typedef unsigned long long SVF::CoreBitVector::Word

Definition at line 33 of file CoreBitVector.h.

Constructor & Destructor Documentation

CoreBitVector() [1/4]

SVF::CoreBitVector::CoreBitVector

(

void

)

Construct empty CBV.

Definition at line 24 of file CoreBitVector.cpp.

    : CoreBitVector(0) { }

CoreBitVector() [2/4]

SVF::CoreBitVector::CoreBitVector

(

size_t

n

)

Construct empty CBV with space reserved for n Words.

Definition at line 27 of file CoreBitVector.cpp.

    : offset(0), words(n, 0) { }

CoreBitVector() [3/4]

SVF::CoreBitVector::CoreBitVector

(

const CoreBitVector &

cbv

)

Copy constructor.

Definition at line 30 of file CoreBitVector.cpp.

    : offset(cbv.offset), words(cbv.words) { }

CoreBitVector() [4/4]

SVF::CoreBitVector::CoreBitVector

(

CoreBitVector &&

cbv

)

Move constructor.

Definition at line 33 of file CoreBitVector.cpp.

    : offset(cbv.offset), words(std::move(cbv.words)) { }

Member Function Documentation

begin()

CoreBitVector::const_iterator SVF::CoreBitVector::begin

(

void

)

const

Definition at line 315 of file CoreBitVector.cpp.

{
    return CoreBitVectorIterator(this);
}

canHold()

bool SVF::CoreBitVector::canHold ( u32_t  bit ) const

private

Returns true if bit can fit in this CBV without resizing.

Definition at line 366 of file CoreBitVector.cpp.

{
    return bit >= offset && bit < offset + words.size() * WordSize;
}

clear()

void SVF::CoreBitVector::clear

(

void

)

Empty the CBV.

Definition at line 65 of file CoreBitVector.cpp.

{
    offset = 0;
    words.clear();
    words.shrink_to_fit();
}

contains()

bool SVF::CoreBitVector::contains

(

const CoreBitVector &

rhs

)

const

Returns true if this CBV is a superset of rhs.

Definition at line 105 of file CoreBitVector.cpp.

{
    CoreBitVector tmp(*this);
    tmp &= rhs;
    return tmp == rhs;
}

count()

u32_t SVF::CoreBitVector::count

(

void

)

const

Returns number of bits set.

Definition at line 58 of file CoreBitVector.cpp.

{
    u32_t n = 0;
    for (const Word &w : words) n += countPopulation(w);
    return n;
}

empty()

bool SVF::CoreBitVector::empty

(

void

)

const

Returns true if no bits are set.

Definition at line 50 of file CoreBitVector.cpp.

{
    for (const Word& w : words)
        if (w)
            return false;
    return true;
}

end()

CoreBitVector::const_iterator SVF::CoreBitVector::end

(

void

)

const

Definition at line 310 of file CoreBitVector.cpp.

{
    return CoreBitVectorIterator(this, true);
}

extendBackward()

void SVF::CoreBitVector::extendBackward ( u32_t  bit )

private

Add enough words (prepend) to be able to include bit.

Definition at line 320 of file CoreBitVector.cpp.

{
    // New offset is the starting bit of the word which contains bit.
    u32_t newOffset = (bit / WordSize) * WordSize;
 
    // TODO: maybe assertions?
    // Check if bit can already be included in this BV or if it's extendForward's problem.
    if (newOffset >= offset) return;
 
    words.insert(words.begin(), (offset - newOffset) / WordSize, 0);
    offset = newOffset;
}

extendForward()

void SVF::CoreBitVector::extendForward ( u32_t  bit )

private

Add enough words (append) to be able to include bit.

Definition at line 333 of file CoreBitVector.cpp.

{
    // TODO: maybe assertions?
    // Not our problem; extendBackward's problem, or there is nothing to do.
    if (bit < offset || canHold(bit)) return;
 
    // Starting bit of word which would contain bit.
    u32_t bitsWord = (bit / WordSize) * WordSize;
 
    // Add 1 to represent the final word starting at bitsWord.
    u32_t wordsToAdd = 1 + (bitsWord - words.size() * WordSize - offset) / WordSize;
    words.insert(words.end(), wordsToAdd, 0);
}

extendTo()

void SVF::CoreBitVector::extendTo ( u32_t  bit )

private

Add enough words (append xor prepend) to be able to include bit.

Definition at line 347 of file CoreBitVector.cpp.

{
    if (offset == 0 && words.size() == 0)
    {
        offset = (bit / WordSize) * WordSize;
        words.push_back(0);
    }
    else if (bit < offset) extendBackward(bit);
    else if (bit >= offset + words.size() * WordSize) extendForward(bit);
}

finalBit()

u32_t SVF::CoreBitVector::finalBit ( void  ) const

private

Returns the last bit that this CBV can hold.

Definition at line 371 of file CoreBitVector.cpp.

{
    return offset + words.size() * WordSize - 1;
}

firstCommonBit()

u32_t SVF::CoreBitVector::firstCommonBit ( const CoreBitVector &  rhs ) const

private

Returns the first bit position that both this CBV and rhs can hold.

hash()

size_t SVF::CoreBitVector::hash

(

void

)

const

Hash for this CBV.

Definition at line 298 of file CoreBitVector.cpp.

{
    // From https://stackoverflow.com/a/27216842
    size_t h = words.size();
    for (const Word &w : words)
    {
        h ^= w + 0x9e3779b9 + (h << 6) + (h >> 2);
    }
 
    return h + offset;
}

indexForBit()

size_t SVF::CoreBitVector::indexForBit ( u32_t  bit ) const

private

Returns the index into words which would hold bit.

Definition at line 358 of file CoreBitVector.cpp.

{
    assert(canHold(bit));
    // Recall, offset (and the bits in that word) are represented by words[0],
    // so solve (offset + x) / WordSize == 0... x == -offset.
    return (bit - offset) / WordSize;
}

intersects()

bool SVF::CoreBitVector::intersects

(

const CoreBitVector &

rhs

)

const

Returns true if this CBV and rhs share any set bits.

Definition at line 112 of file CoreBitVector.cpp.

{
    // TODO: want some common iteration method.
    if (empty() && rhs.empty()) return false;
 
    const CoreBitVector &earlierOffsetCBV = offset <= rhs.offset ? *this : rhs;
    const CoreBitVector &laterOffsetCBV = offset <= rhs.offset ? rhs : *this;
 
    size_t earlierOffset = (offset < rhs.offset ? offset : rhs.offset) / WordSize;
    size_t laterOffset = (offset > rhs.offset ? offset : rhs.offset) / WordSize;
    laterOffset -= earlierOffset;
 
    const Word *eWords = &earlierOffsetCBV.words[0];
    const size_t eSize = earlierOffsetCBV.words.size();
    const Word *lWords = &laterOffsetCBV.words[0];
    const size_t lSize = laterOffsetCBV.words.size();
 
    size_t e = 0;
    for ( ; e != laterOffset && e != eSize; ++e) { }
 
    size_t l = 0;
    for ( ; e != eSize && l != lSize; ++e, ++l)
    {
        if (eWords[e] & lWords[l]) return true;
    }
 
    return false;
}

intersectWithComplement() [1/2]

void SVF::CoreBitVector::intersectWithComplement	(	const CoreBitVector &	lhs,
		const CoreBitVector &	rhs
	)

Put intersection of lhs with complement of rhs into this CBV.

Definition at line 291 of file CoreBitVector.cpp.

{
    // TODO: inefficient!
    *this = lhs;
    intersectWithComplement(rhs);
}

intersectWithComplement() [2/2]

bool SVF::CoreBitVector::intersectWithComplement

(

const CoreBitVector &

rhs

)

Put intersection of this CBV with complement of rhs into this CBV. Returns true if this CBV changed.

Definition at line 286 of file CoreBitVector.cpp.

{
    return *this -= rhs;
}

nextSetIndex()

size_t SVF::CoreBitVector::nextSetIndex ( const size_t  start ) const

private

Returns the next index in the words array at or after start which contains set bits. This index and start are indices into the words array not accounting for the offset. Returns a value greater than or equal to words.size() when there are no more set bits.

Definition at line 376 of file CoreBitVector.cpp.

{
    size_t index = start;
    for ( ; index < words.size(); ++index)
    {
        if (words[index]) break;
    }
 
    return index;
}

operator!=()

bool SVF::CoreBitVector::operator!=

(

const CoreBitVector &

rhs

)

const

Returns true if either this CBV or rhs has a bit set unique to the other.

Definition at line 169 of file CoreBitVector.cpp.

{
    return !(*this == rhs);
}

operator&=()

bool SVF::CoreBitVector::operator&=

(

const CoreBitVector &

rhs

)

Put intersection of this CBV and rhs into this CBV. Returns true if CBV changed.

Definition at line 214 of file CoreBitVector.cpp.

{
    // The first bit this and rhs have in common is the greater of
    // their offsets if the CBV with the smaller offset can hold
    // the greater offset.
    u32_t greaterOffset = std::max(offset, rhs.offset);
 
    // If there is no overlap, then clear this CBV.
    if (!canHold(greaterOffset) || !rhs.canHold(greaterOffset))
    {
        bool changed = false;
        for (size_t i = 0; i < words.size(); ++i)
        {
            if (!changed) changed = words[i] != 0;
            words[i] = 0;
        }
 
        return changed;
    }
 
    bool changed = false;
    size_t thisIndex = indexForBit(greaterOffset);
    size_t rhsIndex = rhs.indexForBit(greaterOffset);
 
    // Clear everything before the overlapping part.
    for (size_t i = 0; i < thisIndex; ++i)
    {
        if (!changed) changed = words[i] != 0;
        words[i] = 0;
    }
 
    Word oldWord;
    for ( ; thisIndex < words.size() && rhsIndex < rhs.words.size(); ++thisIndex, ++rhsIndex)
    {
        if (!changed) oldWord = words[thisIndex];
        words[thisIndex] &= rhs.words[rhsIndex];
        if (!changed) changed = oldWord != words[thisIndex];
    }
 
    // Clear the remaining bits with no rhs analogue.
    for ( ; thisIndex < words.size(); ++thisIndex)
    {
        if (!changed && words[thisIndex] != 0) changed = true;
        words[thisIndex] = 0;
    }
 
    return changed;
}

operator-=()

bool SVF::CoreBitVector::operator-=

(

const CoreBitVector &

rhs

)

Remove set bits in rhs from this CBV. Returns true if CBV changed.

Definition at line 263 of file CoreBitVector.cpp.

{
    // Similar to |= in that we only iterate over rhs within this, but we
    // don't need to extend anything since nothing from rhs is being added.
    u32_t greaterOffset = std::max(offset, rhs.offset);
    // TODO: calling twice.
    // No overlap if either cannot hold the greater offset.
    if (!canHold(greaterOffset) || !rhs.canHold(greaterOffset)) return false;
 
    bool changed = false;
    size_t thisIndex = indexForBit(greaterOffset);
    size_t rhsIndex = rhs.indexForBit(greaterOffset);
    Word oldWord;
    for ( ; thisIndex < words.size() && rhsIndex < rhs.words.size(); ++thisIndex, ++rhsIndex)
    {
        if (!changed) oldWord = words[thisIndex];
        words[thisIndex] &= ~rhs.words[rhsIndex];
        if (!changed) changed = oldWord != words[thisIndex];
    }
 
    return changed;
}

operator=() [1/2]

CoreBitVector & SVF::CoreBitVector::operator=

(

const CoreBitVector &

rhs

)

Copy assignment.

Definition at line 36 of file CoreBitVector.cpp.

{
    this->offset = rhs.offset;
    this->words = rhs.words;
    return *this;
}

operator=() [2/2]

CoreBitVector & SVF::CoreBitVector::operator=

(

CoreBitVector &&

rhs

)

Move assignment.

Definition at line 43 of file CoreBitVector.cpp.

{
    this->offset = rhs.offset;
    this->words = std::move(rhs.words);
    return *this;
}

operator==()

bool SVF::CoreBitVector::operator==

(

const CoreBitVector &

rhs

)

const

Returns true if this CBV and rhs have the same bits set.

Definition at line 141 of file CoreBitVector.cpp.

{
    if (this == &rhs) return true;
 
    // TODO: maybe a simple equal offset, equal size path?
 
    size_t lhsSetIndex = nextSetIndex(0);
    size_t rhsSetIndex = rhs.nextSetIndex(0);
    // Iterate comparing only words with set bits, if there is ever a mismatch,
    // then the bit-vectors aren't equal.
    while (lhsSetIndex < words.size() && rhsSetIndex < rhs.words.size())
    {
        // If the first bit is not the same in the word or words are different,
        // then we have a mismatch.
        if (lhsSetIndex * WordSize + offset != rhsSetIndex * WordSize + rhs.offset
                || words[lhsSetIndex] != rhs.words[rhsSetIndex])
        {
            return false;
        }
 
        lhsSetIndex = nextSetIndex(lhsSetIndex + 1);
        rhsSetIndex = rhs.nextSetIndex(rhsSetIndex + 1);
    }
 
    // Make sure both got to the end at the same time.
    return lhsSetIndex >= words.size() && rhsSetIndex >= rhs.words.size();
}

operator|=()

bool SVF::CoreBitVector::operator|=

(

const CoreBitVector &

rhs

)

Put union of this CBV and rhs into this CBV. Returns true if CBV changed.

Definition at line 174 of file CoreBitVector.cpp.

{
    if (words.size() == 0)
    {
        *this = rhs;
        return words.size() != 0;
    }
 
    if (rhs.words.size() == 0) return false;
 
    if (this == &rhs) return false;
 
    // TODO: some redundancy in extendTo calls.
    if (finalBit() < rhs.finalBit()) extendForward(rhs.finalBit());
    if (offset > rhs.offset) extendBackward(rhs.offset);
 
    // Start counting this where rhs starts.
    const size_t thisIndex = indexForBit(rhs.offset);
    size_t rhsIndex = 0;
 
    // Only need to test against rhs's size since we extended this to hold rhs.
    Word *thisWords = &words[thisIndex];
    const Word *rhsWords = &rhs.words[rhsIndex];
    const size_t length = rhs.words.size();
    Word changed = 0;
 
    // Can start counting from 0 because we took the addresses of both
    // word vectors at the correct index.
    // #pragma omp simd
    for (size_t i = 0 ; i < length; ++i)
    {
        const Word oldWord = thisWords[i];
        // Is there anything in rhs not in *this?
        thisWords[i] = thisWords[i] | rhsWords[i];
        changed |= oldWord ^ thisWords[i];
    }
 
    return changed;
}

reset()

void SVF::CoreBitVector::reset

(

u32_t

bit

)

Resets bit in the CBV.

Definition at line 97 of file CoreBitVector.cpp.

{
    if (bit < offset || bit >= offset + words.size() * WordSize) return;
    Word &containingWord = words[(bit - offset) / WordSize];
    Word mask = ~((Word)0b1 << (bit % WordSize));
    containingWord &= mask;
}

set()

void SVF::CoreBitVector::set

(

u32_t

bit

)

Sets bit in the CBV.

Definition at line 88 of file CoreBitVector.cpp.

{
    extendTo(bit);
 
    Word &containingWord = words[(bit - offset) / WordSize];
    Word mask = (Word)0b1 << (bit % WordSize);
    containingWord |= mask;
}

test()

bool SVF::CoreBitVector::test

(

u32_t

bit

)

const

Returns true if bit is set in this CBV.

Definition at line 72 of file CoreBitVector.cpp.

{
    if (bit < offset || bit >= offset + words.size() * WordSize) return false;
    const Word &containingWord = words[(bit - offset) / WordSize];
    const Word mask = (Word)0b1 << (bit % WordSize);
    return mask & containingWord;
}

test_and_set()

bool SVF::CoreBitVector::test_and_set

(

u32_t

bit

)

Check if bit is set. If it is, returns false. Otherwise, sets bit and returns true.

Definition at line 80 of file CoreBitVector.cpp.

{
    // TODO: can be faster.
    if (test(bit)) return false;
    set(bit);
    return true;
}

Member Data Documentation

offset

u32_t SVF::CoreBitVector::offset

private

The first bit of the first word.

Definition at line 198 of file CoreBitVector.h.

words

std::vector<Word> SVF::CoreBitVector::words

private

Our actual bit vector.

Definition at line 200 of file CoreBitVector.h.

WordSize

const size_t SVF::CoreBitVector::WordSize = sizeof(Word) * CHAR_BIT

static

Definition at line 34 of file CoreBitVector.h.

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF/SVF/svf/include/Util/CoreBitVector.h
• /home/runner/work/SVF/SVF/svf/lib/Util/CoreBitVector.cpp