#include <SparseBitVector.h>

Public Types
enum	{ BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT , BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE , BITS_PER_ELEMENT = ElementSize }

using	BitWord = unsigned long

using	size_type = unsigned

Public Member Functions
	SparseBitVectorElement (unsigned Idx)

bool	operator== (const SparseBitVectorElement &RHS) const

bool	operator!= (const SparseBitVectorElement &RHS) const

BitWord	word (unsigned Idx) const

unsigned	index () const

bool	empty () const

void	set (unsigned Idx)

bool	test_and_set (unsigned Idx)

void	reset (unsigned Idx)

bool	test (unsigned Idx) const

size_type	count () const

int	find_first () const
	find_first - Returns the index of the first set bit.

int	find_last () const
	find_last - Returns the index of the last set bit.

int	find_next (unsigned Curr) const

bool	unionWith (const SparseBitVectorElement &RHS)

bool	intersects (const SparseBitVectorElement &RHS) const

bool	intersectWith (const SparseBitVectorElement &RHS, bool &BecameZero)

bool	intersectWithComplement (const SparseBitVectorElement &RHS, bool &BecameZero)

void	intersectWithComplement (const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)

Private Member Functions
	SparseBitVectorElement ()=default

Private Attributes
unsigned	ElementIndex = 0

BitWord	Bits [BITWORDS_PER_ELEMENT] = {0}

Friends
class	SVFIRWriter

class	SVFIRReader

Detailed Description

template<unsigned ElementSize = 128>
struct SVF::SparseBitVectorElement< ElementSize >

SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that have non-zero bits set. In order to make this fast for the most common cases, SparseBitVector is implemented as a linked list of SparseBitVectorElements. We maintain a pointer to the last SparseBitVectorElement accessed (in the form of a list iterator), in order to make multiple in-order test/set constant time after the first one is executed. Note that using vectors to store SparseBitVectorElement's does not work out very well because it causes insertion in the middle to take enormous amounts of time with a large amount of bits. Other structures that have better worst cases for insertion in the middle (various balanced trees, etc) do not perform as well in practice as a linked list with this iterator kept up to date. They are also significantly more memory intensive.

Definition at line 259 of file SparseBitVector.h.

Member Typedef Documentation

◆ BitWord

template<unsigned ElementSize = 128>

using SVF::SparseBitVectorElement< ElementSize >::BitWord = unsigned long

Definition at line 265 of file SparseBitVector.h.

◆ size_type

template<unsigned ElementSize = 128>

using SVF::SparseBitVectorElement< ElementSize >::size_type = unsigned

Definition at line 266 of file SparseBitVector.h.

Member Enumeration Documentation

◆ anonymous enum

template<unsigned ElementSize = 128>

anonymous enum

Enumerator
BITWORD_SIZE
BITWORDS_PER_ELEMENT
BITS_PER_ELEMENT

Definition at line 267 of file SparseBitVector.h.

    {
        BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
        // N.B. (+ BITWORD_SIZE - 1) is to round up, to ensure we can have
        // sufficient bits to represent *at least* ElementSize bits.
        BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
        BITS_PER_ELEMENT = ElementSize
    };

Constructor & Destructor Documentation

◆ SparseBitVectorElement() [1/2]

template<unsigned ElementSize = 128>

SVF::SparseBitVectorElement< ElementSize >::SparseBitVectorElement ( )

privatedefault

◆ SparseBitVectorElement() [2/2]

template<unsigned ElementSize = 128>

SVF::SparseBitVectorElement< ElementSize >::SparseBitVectorElement ( unsigned Idx )

inlineexplicit

Definition at line 284 of file SparseBitVector.h.

284: ElementIndex(Idx) {}

SVF::SparseBitVectorElement::ElementIndex

unsigned ElementIndex

Definition SparseBitVector.h:278

Member Function Documentation

◆ count()

template<unsigned ElementSize = 128>

size_type SVF::SparseBitVectorElement< ElementSize >::count ( ) const

inline

Definition at line 348 of file SparseBitVector.h.

    {
        unsigned NumBits = 0;
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
            NumBits += countPopulation(Bits[i]);
        return NumBits;
    }

◆ empty()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::empty ( ) const

inline

Definition at line 314 of file SparseBitVector.h.

    {
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
            if (Bits[i])
                return false;
        return true;
    }

◆ find_first()

template<unsigned ElementSize = 128>

int SVF::SparseBitVectorElement< ElementSize >::find_first ( ) const

inline

find_first - Returns the index of the first set bit.

Definition at line 357 of file SparseBitVector.h.

    {
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
            if (Bits[i] != 0)
                return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
        assert(false && "SBV: find_first: SBV cannot be empty");
        abort();
    }

◆ find_last()

template<unsigned ElementSize = 128>

int SVF::SparseBitVectorElement< ElementSize >::find_last ( ) const

inline

find_last - Returns the index of the last set bit.

Definition at line 367 of file SparseBitVector.h.

    {
        for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I)
        {
            unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
            if (Bits[Idx] != 0)
                return Idx * BITWORD_SIZE + BITWORD_SIZE -
                       countLeadingZeros(Bits[Idx]) - 1;
        }
        assert(false && "SBV: find_last: SBV cannot be empty");
        abort();
    }

◆ find_next()

template<unsigned ElementSize = 128>

int SVF::SparseBitVectorElement< ElementSize >::find_next ( unsigned Curr ) const

inline

find_next - Returns the index of the next set bit starting from the "Curr" bit. Returns -1 if the next set bit is not found.

Definition at line 382 of file SparseBitVector.h.

    {
        if (Curr >= BITS_PER_ELEMENT)
            return -1;
 
        unsigned WordPos = Curr / BITWORD_SIZE;
        unsigned BitPos = Curr % BITWORD_SIZE;
        BitWord Copy = Bits[WordPos];
        assert(WordPos <= BITWORDS_PER_ELEMENT
               && "Word Position outside of element");
 
        // Mask off previous bits.
        Copy &= ~0UL << BitPos;
 
        if (Copy != 0)
            return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
 
        // Check subsequent words.
        for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
            if (Bits[i] != 0)
                return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
        return -1;
    }

◆ index()

template<unsigned ElementSize = 128>

unsigned SVF::SparseBitVectorElement< ElementSize >::index ( ) const

inline

Definition at line 309 of file SparseBitVector.h.

    {
        return ElementIndex;
    }

◆ intersects()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::intersects ( const SparseBitVectorElement< ElementSize > & RHS ) const

inline

Definition at line 422 of file SparseBitVector.h.

    {
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
        {
            if (RHS.Bits[i] & Bits[i])
                return true;
        }
        return false;
    }

◆ intersectWith()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::intersectWith	(	const SparseBitVectorElement< ElementSize > &	RHS,
		bool &	BecameZero
	)

inline

Definition at line 434 of file SparseBitVector.h.

    {
        bool changed = false;
        bool allzero = true;
 
        BecameZero = false;
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
        {
            BitWord old = changed ? 0 : Bits[i];
 
            Bits[i] &= RHS.Bits[i];
            if (Bits[i] != 0)
                allzero = false;
 
            if (!changed && old != Bits[i])
                changed = true;
        }
        BecameZero = allzero;
        return changed;
    }

◆ intersectWithComplement() [1/2]

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::intersectWithComplement	(	const SparseBitVectorElement< ElementSize > &	RHS,
		bool &	BecameZero
	)

inline

Definition at line 459 of file SparseBitVector.h.

    {
        bool changed = false;
        bool allzero = true;
 
        BecameZero = false;
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
        {
            BitWord old = changed ? 0 : Bits[i];
 
            Bits[i] &= ~RHS.Bits[i];
            if (Bits[i] != 0)
                allzero = false;
 
            if (!changed && old != Bits[i])
                changed = true;
        }
        BecameZero = allzero;
        return changed;
    }

◆ intersectWithComplement() [2/2]

template<unsigned ElementSize = 128>

void SVF::SparseBitVectorElement< ElementSize >::intersectWithComplement	(	const SparseBitVectorElement< ElementSize > &	RHS1,
		const SparseBitVectorElement< ElementSize > &	RHS2,
		bool &	BecameZero
	)

inline

Definition at line 483 of file SparseBitVector.h.

    {
        bool allzero = true;
 
        BecameZero = false;
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
        {
            Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
            if (Bits[i] != 0)
                allzero = false;
        }
        BecameZero = allzero;
    }

◆ operator!=()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::operator!= ( const SparseBitVectorElement< ElementSize > & RHS ) const

inline

Definition at line 297 of file SparseBitVector.h.

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

◆ operator==()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::operator== ( const SparseBitVectorElement< ElementSize > & RHS ) const

inline

Definition at line 287 of file SparseBitVector.h.

    {
        if (ElementIndex != RHS.ElementIndex)
            return false;
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
            if (Bits[i] != RHS.Bits[i])
                return false;
        return true;
    }

◆ reset()

template<unsigned ElementSize = 128>

void SVF::SparseBitVectorElement< ElementSize >::reset ( unsigned Idx )

inline

Definition at line 338 of file SparseBitVector.h.

    {
        Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
    }

◆ set()

template<unsigned ElementSize = 128>

void SVF::SparseBitVectorElement< ElementSize >::set ( unsigned Idx )

inline

Definition at line 322 of file SparseBitVector.h.

    {
        Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
    }

◆ test()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::test ( unsigned Idx ) const

inline

Definition at line 343 of file SparseBitVector.h.

    {
        return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
    }

◆ test_and_set()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::test_and_set ( unsigned Idx )

inline

Definition at line 327 of file SparseBitVector.h.

    {
        bool old = test(Idx);
        if (!old)
        {
            set(Idx);
            return true;
        }
        return false;
    }

◆ unionWith()

template<unsigned ElementSize = 128>

bool SVF::SparseBitVectorElement< ElementSize >::unionWith ( const SparseBitVectorElement< ElementSize > & RHS )

inline

Definition at line 407 of file SparseBitVector.h.

    {
        bool changed = false;
        for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
        {
            BitWord old = changed ? 0 : Bits[i];
 
            Bits[i] |= RHS.Bits[i];
            if (!changed && old != Bits[i])
                changed = true;
        }
        return changed;
    }

◆ word()

template<unsigned ElementSize = 128>

BitWord SVF::SparseBitVectorElement< ElementSize >::word ( unsigned Idx ) const

inline

Definition at line 303 of file SparseBitVector.h.

    {
        assert(Idx < BITWORDS_PER_ELEMENT);
        return Bits[Idx];
    }

Friends And Related Symbol Documentation

◆ SVFIRReader

template<unsigned ElementSize = 128>

friend class SVFIRReader

friend

Definition at line 262 of file SparseBitVector.h.

◆ SVFIRWriter

template<unsigned ElementSize = 128>

friend class SVFIRWriter

friend

Definition at line 261 of file SparseBitVector.h.

Member Data Documentation

◆ Bits

template<unsigned ElementSize = 128>

BitWord SVF::SparseBitVectorElement< ElementSize >::Bits[BITWORDS_PER_ELEMENT] = {0}

private

Definition at line 279 of file SparseBitVector.h.

279{0};

◆ ElementIndex

template<unsigned ElementSize = 128>

unsigned SVF::SparseBitVectorElement< ElementSize >::ElementIndex = 0

private

Definition at line 278 of file SparseBitVector.h.

The documentation for this struct was generated from the following file:

/home/runner/work/SVF/SVF/svf/include/Util/SparseBitVector.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ BitWord

◆ size_type

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ SparseBitVectorElement() [1/2]

◆ SparseBitVectorElement() [2/2]

Member Function Documentation

◆ count()

◆ empty()

◆ find_first()

◆ find_last()

◆ find_next()

◆ index()

◆ intersects()

◆ intersectWith()

◆ intersectWithComplement() [1/2]

◆ intersectWithComplement() [2/2]

◆ operator!=()

◆ operator==()

◆ reset()

◆ set()

◆ test()

◆ test_and_set()

◆ unionWith()

◆ word()

Friends And Related Symbol Documentation

◆ SVFIRReader

◆ SVFIRWriter

Member Data Documentation

◆ Bits

◆ ElementIndex