#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}

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 263 of file SparseBitVector.h.

◆ size_type

template<unsigned ElementSize = 128>

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

Definition at line 264 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 265 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 282 of file SparseBitVector.h.

282: ElementIndex(Idx) {}

SVF::SparseBitVectorElement::ElementIndex

unsigned ElementIndex

Definition SparseBitVector.h:276

Member Function Documentation

◆ count()

template<unsigned ElementSize = 128>

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

inline

Definition at line 346 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 312 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 355 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 365 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 380 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 307 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 420 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 432 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 457 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 481 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 295 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 285 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 336 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 320 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 341 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 325 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 405 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 301 of file SparseBitVector.h.

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

Member Data Documentation

◆ Bits

template<unsigned ElementSize = 128>

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

private

Definition at line 277 of file SparseBitVector.h.

277{0};

◆ ElementIndex

template<unsigned ElementSize = 128>

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

private

Definition at line 276 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

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()

Member Data Documentation

◆ Bits

◆ ElementIndex