Static Value-Flow Analysis
Public Types | Public Member Functions | Private Member Functions | Private Attributes | Friends | List of all members
SVF::SparseBitVectorElement< ElementSize > Struct Template Reference

#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. More...
 
int find_last () const
 find_last - Returns the index of the last set bit. More...
 
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.

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

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) {}

Member Function Documentation

◆ count()

template<unsigned ElementSize = 128>
size_type SVF::SparseBitVectorElement< ElementSize >::count ( void  ) const
inline

Definition at line 348 of file SparseBitVector.h.

349  {
350  unsigned NumBits = 0;
351  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
352  NumBits += countPopulation(Bits[i]);
353  return NumBits;
354  }
SVF::countPopulation
unsigned countPopulation(T Value)
Definition: SparseBitVector.h:239
SVF::SparseBitVectorElement::Bits
BitWord Bits[BITWORDS_PER_ELEMENT]
Definition: SparseBitVector.h:279

◆ empty()

template<unsigned ElementSize = 128>
bool SVF::SparseBitVectorElement< ElementSize >::empty ( void  ) const
inline

Definition at line 314 of file SparseBitVector.h.

315  {
316  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
317  if (Bits[i])
318  return false;
319  return true;
320  }

◆ 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.

358  {
359  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
360  if (Bits[i] != 0)
361  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
362  assert(false && "SBV: find_first: SBV cannot be empty");
363  abort();
364  }
SVF::countTrailingZeros
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Definition: SparseBitVector.h:119

◆ 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.

368  {
369  for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I)
370  {
371  unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
372  if (Bits[Idx] != 0)
373  return Idx * BITWORD_SIZE + BITWORD_SIZE -
374  countLeadingZeros(Bits[Idx]) - 1;
375  }
376  assert(false && "SBV: find_last: SBV cannot be empty");
377  abort();
378  }
SVF::countLeadingZeros
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Definition: SparseBitVector.h:211

◆ 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.

383  {
384  if (Curr >= BITS_PER_ELEMENT)
385  return -1;
386 
387  unsigned WordPos = Curr / BITWORD_SIZE;
388  unsigned BitPos = Curr % BITWORD_SIZE;
389  BitWord Copy = Bits[WordPos];
390  assert(WordPos <= BITWORDS_PER_ELEMENT
391  && "Word Position outside of element");
392 
393  // Mask off previous bits.
394  Copy &= ~0UL << BitPos;
395 
396  if (Copy != 0)
397  return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
398 
399  // Check subsequent words.
400  for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
401  if (Bits[i] != 0)
402  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
403  return -1;
404  }

◆ index()

template<unsigned ElementSize = 128>
unsigned SVF::SparseBitVectorElement< ElementSize >::index ( ) const
inline

Definition at line 309 of file SparseBitVector.h.

310  {
311  return ElementIndex;
312  }

◆ intersects()

template<unsigned ElementSize = 128>
bool SVF::SparseBitVectorElement< ElementSize >::intersects ( const SparseBitVectorElement< ElementSize > &  RHS) const
inline

Definition at line 422 of file SparseBitVector.h.

423  {
424  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
425  {
426  if (RHS.Bits[i] & Bits[i])
427  return true;
428  }
429  return false;
430  }

◆ 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.

436  {
437  bool changed = false;
438  bool allzero = true;
439 
440  BecameZero = false;
441  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
442  {
443  BitWord old = changed ? 0 : Bits[i];
444 
445  Bits[i] &= RHS.Bits[i];
446  if (Bits[i] != 0)
447  allzero = false;
448 
449  if (!changed && old != Bits[i])
450  changed = true;
451  }
452  BecameZero = allzero;
453  return changed;
454  }

◆ 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.

461  {
462  bool changed = false;
463  bool allzero = true;
464 
465  BecameZero = false;
466  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
467  {
468  BitWord old = changed ? 0 : Bits[i];
469 
470  Bits[i] &= ~RHS.Bits[i];
471  if (Bits[i] != 0)
472  allzero = false;
473 
474  if (!changed && old != Bits[i])
475  changed = true;
476  }
477  BecameZero = allzero;
478  return changed;
479  }

◆ 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.

486  {
487  bool allzero = true;
488 
489  BecameZero = false;
490  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
491  {
492  Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
493  if (Bits[i] != 0)
494  allzero = false;
495  }
496  BecameZero = allzero;
497  }

◆ operator!=()

template<unsigned ElementSize = 128>
bool SVF::SparseBitVectorElement< ElementSize >::operator!= ( const SparseBitVectorElement< ElementSize > &  RHS) const
inline

Definition at line 297 of file SparseBitVector.h.

298  {
299  return !(*this == RHS);
300  }

◆ operator==()

template<unsigned ElementSize = 128>
bool SVF::SparseBitVectorElement< ElementSize >::operator== ( const SparseBitVectorElement< ElementSize > &  RHS) const
inline

Definition at line 287 of file SparseBitVector.h.

288  {
289  if (ElementIndex != RHS.ElementIndex)
290  return false;
291  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
292  if (Bits[i] != RHS.Bits[i])
293  return false;
294  return true;
295  }

◆ reset()

template<unsigned ElementSize = 128>
void SVF::SparseBitVectorElement< ElementSize >::reset ( unsigned  Idx)
inline

Definition at line 338 of file SparseBitVector.h.

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

◆ set()

template<unsigned ElementSize = 128>
void SVF::SparseBitVectorElement< ElementSize >::set ( unsigned  Idx)
inline

Definition at line 322 of file SparseBitVector.h.

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

◆ test()

template<unsigned ElementSize = 128>
bool SVF::SparseBitVectorElement< ElementSize >::test ( unsigned  Idx) const
inline

Definition at line 343 of file SparseBitVector.h.

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

◆ 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.

328  {
329  bool old = test(Idx);
330  if (!old)
331  {
332  set(Idx);
333  return true;
334  }
335  return false;
336  }
SVF::SparseBitVectorElement::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:343

◆ unionWith()

template<unsigned ElementSize = 128>
bool SVF::SparseBitVectorElement< ElementSize >::unionWith ( const SparseBitVectorElement< ElementSize > &  RHS)
inline

Definition at line 407 of file SparseBitVector.h.

408  {
409  bool changed = false;
410  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
411  {
412  BitWord old = changed ? 0 : Bits[i];
413 
414  Bits[i] |= RHS.Bits[i];
415  if (!changed && old != Bits[i])
416  changed = true;
417  }
418  return changed;
419  }

◆ word()

template<unsigned ElementSize = 128>
BitWord SVF::SparseBitVectorElement< ElementSize >::word ( unsigned  Idx) const
inline

Definition at line 303 of file SparseBitVector.h.

304  {
305  assert(Idx < BITWORDS_PER_ELEMENT);
306  return Bits[Idx];
307  }

Friends And Related Function 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.

◆ 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:
Generated by doxygen 1.9.1