Static Value-Flow Analysis
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Friends | List of all members
SVF::SparseBitVector< ElementSize > Class Template Reference

#include <SparseBitVector.h>

Classes

class  SparseBitVectorIterator
 

Public Types

using iterator = SparseBitVectorIterator
 

Public Member Functions

 SparseBitVector ()
 
 SparseBitVector (const SparseBitVector &RHS)
 
 SparseBitVector (SparseBitVector &&RHS) noexcept
 
void clear ()
 
SparseBitVectoroperator= (const SparseBitVector &RHS)
 
SparseBitVectoroperator= (SparseBitVector &&RHS)
 
bool test (unsigned Idx) const
 
void reset (unsigned Idx)
 
void set (unsigned Idx)
 
bool test_and_set (unsigned Idx)
 
bool operator!= (const SparseBitVector &RHS) const
 
bool operator== (const SparseBitVector &RHS) const
 
bool operator|= (const SparseBitVector &RHS)
 
bool operator&= (const SparseBitVector &RHS)
 
bool intersectWithComplement (const SparseBitVector &RHS)
 
bool intersectWithComplement (const SparseBitVector< ElementSize > *RHS) const
 
void intersectWithComplement (const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)
 
void intersectWithComplement (const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
 
bool intersects (const SparseBitVector< ElementSize > *RHS) const
 
bool intersects (const SparseBitVector< ElementSize > &RHS) const
 
bool contains (const SparseBitVector< ElementSize > &RHS) const
 
int find_first () const
 
int find_last () const
 
bool empty () const
 
unsigned count () const
 
iterator begin () const
 
iterator end () const
 

Private Types

enum  { BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE }
 
using ElementList = std::list< SparseBitVectorElement< ElementSize > >
 
using ElementListIter = typename ElementList::iterator
 
using ElementListConstIter = typename ElementList::const_iterator
 

Private Member Functions

ElementListIter FindLowerBoundImpl (unsigned ElementIndex) const
 
ElementListConstIter FindLowerBoundConst (unsigned ElementIndex) const
 
ElementListIter FindLowerBound (unsigned ElementIndex)
 

Private Attributes

ElementList Elements
 
ElementListIter CurrElementIter
 

Friends

class SVFIRWriter
 
class SVFIRReader
 

Detailed Description

template<unsigned ElementSize = 128>
class SVF::SparseBitVector< ElementSize >

Definition at line 501 of file SparseBitVector.h.

Member Typedef Documentation

◆ ElementList

template<unsigned ElementSize = 128>
using SVF::SparseBitVector< ElementSize >::ElementList = std::list<SparseBitVectorElement<ElementSize> >
private

Definition at line 506 of file SparseBitVector.h.

◆ ElementListConstIter

template<unsigned ElementSize = 128>
using SVF::SparseBitVector< ElementSize >::ElementListConstIter = typename ElementList::const_iterator
private

Definition at line 508 of file SparseBitVector.h.

◆ ElementListIter

template<unsigned ElementSize = 128>
using SVF::SparseBitVector< ElementSize >::ElementListIter = typename ElementList::iterator
private

Definition at line 507 of file SparseBitVector.h.

◆ iterator

template<unsigned ElementSize = 128>
using SVF::SparseBitVector< ElementSize >::iterator = SparseBitVectorIterator

Definition at line 717 of file SparseBitVector.h.

Member Enumeration Documentation

◆ anonymous enum

template<unsigned ElementSize = 128>
anonymous enum
private
Enumerator
BITWORD_SIZE 

Definition at line 509 of file SparseBitVector.h.

Constructor & Destructor Documentation

◆ SparseBitVector() [1/3]

template<unsigned ElementSize = 128>
SVF::SparseBitVector< ElementSize >::SparseBitVector ( )
inline

Definition at line 719 of file SparseBitVector.h.

719: Elements(), CurrElementIter(Elements.begin()) {}
ElementListIter CurrElementIter

◆ SparseBitVector() [2/3]

template<unsigned ElementSize = 128>
SVF::SparseBitVector< ElementSize >::SparseBitVector ( const SparseBitVector< ElementSize > &  RHS)
inline

Definition at line 721 of file SparseBitVector.h.

722 : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}

◆ SparseBitVector() [3/3]

template<unsigned ElementSize = 128>
SVF::SparseBitVector< ElementSize >::SparseBitVector ( SparseBitVector< ElementSize > &&  RHS)
inlinenoexcept

Definition at line 723 of file SparseBitVector.h.

724 : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}

Member Function Documentation

◆ begin()

template<unsigned ElementSize = 128>
iterator SVF::SparseBitVector< ElementSize >::begin ( ) const
inline

Definition at line 1157 of file SparseBitVector.h.

1158 {
1159 return iterator(this);
1160 }
SparseBitVectorIterator iterator

◆ clear()

template<unsigned ElementSize = 128>
void SVF::SparseBitVector< ElementSize >::clear ( )
inline

Definition at line 727 of file SparseBitVector.h.

728 {
729 Elements.clear();
730 }

◆ contains()

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

Definition at line 1115 of file SparseBitVector.h.

1116 {
1117 SparseBitVector<ElementSize> Result(*this);
1118 Result &= RHS;
1119 return (Result == RHS);
1120 }

◆ count()

template<unsigned ElementSize = 128>
unsigned SVF::SparseBitVector< ElementSize >::count ( ) const
inline

Definition at line 1146 of file SparseBitVector.h.

1147 {
1148 unsigned BitCount = 0;
1149 for (ElementListConstIter Iter = Elements.begin();
1150 Iter != Elements.end();
1151 ++Iter)
1152 BitCount += Iter->count();
1153
1154 return BitCount;
1155 }
typename ElementList::const_iterator ElementListConstIter

◆ empty()

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

Definition at line 1141 of file SparseBitVector.h.

1142 {
1143 return Elements.empty();
1144 }

◆ end()

template<unsigned ElementSize = 128>
iterator SVF::SparseBitVector< ElementSize >::end ( ) const
inline

Definition at line 1162 of file SparseBitVector.h.

1163 {
1164 return iterator(this, true);
1165 }

◆ find_first()

template<unsigned ElementSize = 128>
int SVF::SparseBitVector< ElementSize >::find_first ( ) const
inline

Definition at line 1123 of file SparseBitVector.h.

1124 {
1125 if (Elements.empty())
1126 return -1;
1127 const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
1128 return (First.index() * ElementSize) + First.find_first();
1129 }

◆ find_last()

template<unsigned ElementSize = 128>
int SVF::SparseBitVector< ElementSize >::find_last ( ) const
inline

Definition at line 1132 of file SparseBitVector.h.

1133 {
1134 if (Elements.empty())
1135 return -1;
1136 const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
1137 return (Last.index() * ElementSize) + Last.find_last();
1138 }

◆ FindLowerBound()

template<unsigned ElementSize = 128>
ElementListIter SVF::SparseBitVector< ElementSize >::FindLowerBound ( unsigned  ElementIndex)
inlineprivate

Definition at line 571 of file SparseBitVector.h.

572 {
573 return FindLowerBoundImpl(ElementIndex);
574 }
ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const

◆ FindLowerBoundConst()

template<unsigned ElementSize = 128>
ElementListConstIter SVF::SparseBitVector< ElementSize >::FindLowerBoundConst ( unsigned  ElementIndex) const
inlineprivate

Definition at line 567 of file SparseBitVector.h.

568 {
569 return FindLowerBoundImpl(ElementIndex);
570 }

◆ FindLowerBoundImpl()

template<unsigned ElementSize = 128>
ElementListIter SVF::SparseBitVector< ElementSize >::FindLowerBoundImpl ( unsigned  ElementIndex) const
inlineprivate

Definition at line 522 of file SparseBitVector.h.

523 {
524
525 // We cache a non-const iterator so we're forced to resort to const_cast to
526 // get the begin/end in the case where 'this' is const. To avoid duplication
527 // of code with the only difference being whether the const cast is present
528 // 'this' is always const in this particular function and we sort out the
529 // difference in FindLowerBound and FindLowerBoundConst.
531 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
533 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
534
535 if (Elements.empty())
536 {
538 return CurrElementIter;
539 }
540
541 // Make sure our current iterator is valid.
542 if (CurrElementIter == End)
544
545 // Search from our current iterator, either backwards or forwards,
546 // depending on what element we are looking for.
548 if (CurrElementIter->index() == ElementIndex)
549 {
550 return ElementIter;
551 }
552 else if (CurrElementIter->index() > ElementIndex)
553 {
554 while (ElementIter != Begin
555 && ElementIter->index() > ElementIndex)
556 --ElementIter;
557 }
558 else
559 {
560 while (ElementIter != End &&
561 ElementIter->index() < ElementIndex)
562 ++ElementIter;
563 }
565 return ElementIter;
566 }
typename ElementList::iterator ElementListIter

◆ intersects() [1/2]

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

Definition at line 1079 of file SparseBitVector.h.

1080 {
1082 ElementListConstIter Iter2 = RHS.Elements.begin();
1083
1084 // Check if both bitmaps are empty.
1085 if (Elements.empty() && RHS.Elements.empty())
1086 return false;
1087
1088 // Loop through, intersecting stopping when we hit bits in common.
1089 while (Iter2 != RHS.Elements.end())
1090 {
1091 if (Iter1 == Elements.end())
1092 return false;
1093
1094 if (Iter1->index() > Iter2->index())
1095 {
1096 ++Iter2;
1097 }
1098 else if (Iter1->index() == Iter2->index())
1099 {
1100 if (Iter1->intersects(*Iter2))
1101 return true;
1102 ++Iter1;
1103 ++Iter2;
1104 }
1105 else
1106 {
1107 ++Iter1;
1108 }
1109 }
1110 return false;
1111 }

◆ intersects() [2/2]

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

Definition at line 1073 of file SparseBitVector.h.

1074 {
1075 return intersects(*RHS);
1076 }
bool intersects(const SparseBitVector< ElementSize > *RHS) const

◆ intersectWithComplement() [1/4]

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

Definition at line 947 of file SparseBitVector.h.

948 {
949 if (this == &RHS)
950 {
951 if (!empty())
952 {
953 clear();
954 return true;
955 }
956 return false;
957 }
958
959 bool changed = false;
961 ElementListConstIter Iter2 = RHS.Elements.begin();
962
963 // If either our bitmap or RHS is empty, we are done
964 if (Elements.empty() || RHS.Elements.empty())
965 return false;
966
967 // Loop through, intersecting as we go, erasing elements when necessary.
968 while (Iter2 != RHS.Elements.end())
969 {
970 if (Iter1 == Elements.end())
971 {
972 CurrElementIter = Elements.begin();
973 return changed;
974 }
975
976 if (Iter1->index() > Iter2->index())
977 {
978 ++Iter2;
979 }
980 else if (Iter1->index() == Iter2->index())
981 {
982 bool BecameZero;
983 changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
984 if (BecameZero)
985 {
987 ++Iter1;
988 Elements.erase(IterTmp);
989 }
990 else
991 {
992 ++Iter1;
993 }
994 ++Iter2;
995 }
996 else
997 {
998 ++Iter1;
999 }
1000 }
1001 CurrElementIter = Elements.begin();
1002 return changed;
1003 }

◆ intersectWithComplement() [2/4]

template<unsigned ElementSize = 128>
void SVF::SparseBitVector< ElementSize >::intersectWithComplement ( const SparseBitVector< ElementSize > &  RHS1,
const SparseBitVector< ElementSize > &  RHS2 
)
inline

Definition at line 1012 of file SparseBitVector.h.

1014 {
1015 if (this == &RHS1)
1016 {
1018 return;
1019 }
1020 else if (this == &RHS2)
1021 {
1024 return;
1025 }
1026
1027 Elements.clear();
1028 CurrElementIter = Elements.begin();
1029 ElementListConstIter Iter1 = RHS1.Elements.begin();
1030 ElementListConstIter Iter2 = RHS2.Elements.begin();
1031
1032 // If RHS1 is empty, we are done
1033 // If RHS2 is empty, we still have to copy RHS1
1034 if (RHS1.Elements.empty())
1035 return;
1036
1037 // Loop through, intersecting as we go, erasing elements when necessary.
1038 while (Iter2 != RHS2.Elements.end())
1039 {
1040 if (Iter1 == RHS1.Elements.end())
1041 return;
1042
1043 if (Iter1->index() > Iter2->index())
1044 {
1045 ++Iter2;
1046 }
1047 else if (Iter1->index() == Iter2->index())
1048 {
1049 bool BecameZero = false;
1050 Elements.emplace_back(Iter1->index());
1051 Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
1052 if (BecameZero)
1053 Elements.pop_back();
1054 ++Iter1;
1055 ++Iter2;
1056 }
1057 else
1058 {
1059 Elements.push_back(*Iter1++);
1060 }
1061 }
1062
1063 // copy the remaining elements
1064 std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
1065 }
bool intersectWithComplement(const SparseBitVector &RHS)

◆ intersectWithComplement() [3/4]

template<unsigned ElementSize = 128>
bool SVF::SparseBitVector< ElementSize >::intersectWithComplement ( const SparseBitVector< ElementSize > *  RHS) const
inline

Definition at line 1005 of file SparseBitVector.h.

1006 {
1008 }

◆ intersectWithComplement() [4/4]

template<unsigned ElementSize = 128>
void SVF::SparseBitVector< ElementSize >::intersectWithComplement ( const SparseBitVector< ElementSize > *  RHS1,
const SparseBitVector< ElementSize > *  RHS2 
)
inline

Definition at line 1067 of file SparseBitVector.h.

1069 {
1071 }

◆ operator!=()

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

Definition at line 829 of file SparseBitVector.h.

830 {
831 return !(*this == RHS);
832 }

◆ operator&=()

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

Definition at line 886 of file SparseBitVector.h.

887 {
888 if (this == &RHS)
889 return false;
890
891 bool changed = false;
893 ElementListConstIter Iter2 = RHS.Elements.begin();
894
895 // Check if both bitmaps are empty.
896 if (Elements.empty() && RHS.Elements.empty())
897 return false;
898
899 // Loop through, intersecting as we go, erasing elements when necessary.
900 while (Iter2 != RHS.Elements.end())
901 {
902 if (Iter1 == Elements.end())
903 {
904 CurrElementIter = Elements.begin();
905 return changed;
906 }
907
908 if (Iter1->index() > Iter2->index())
909 {
910 ++Iter2;
911 }
912 else if (Iter1->index() == Iter2->index())
913 {
914 bool BecameZero;
915 changed |= Iter1->intersectWith(*Iter2, BecameZero);
916 if (BecameZero)
917 {
919 ++Iter1;
920 Elements.erase(IterTmp);
921 }
922 else
923 {
924 ++Iter1;
925 }
926 ++Iter2;
927 }
928 else
929 {
931 ++Iter1;
932 Elements.erase(IterTmp);
933 changed = true;
934 }
935 }
936 if (Iter1 != Elements.end())
937 {
938 Elements.erase(Iter1, Elements.end());
939 changed = true;
940 }
941 CurrElementIter = Elements.begin();
942 return changed;
943 }

◆ operator=() [1/2]

Definition at line 733 of file SparseBitVector.h.

734 {
735 if (this == &RHS)
736 return *this;
737
738 Elements = RHS.Elements;
739 CurrElementIter = Elements.begin();
740 return *this;
741 }

◆ operator=() [2/2]

template<unsigned ElementSize = 128>
SparseBitVector & SVF::SparseBitVector< ElementSize >::operator= ( SparseBitVector< ElementSize > &&  RHS)
inline

Definition at line 742 of file SparseBitVector.h.

743 {
744 Elements = std::move(RHS.Elements);
745 CurrElementIter = Elements.begin();
746 return *this;
747 }

◆ operator==()

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

Definition at line 834 of file SparseBitVector.h.

835 {
837 ElementListConstIter Iter2 = RHS.Elements.begin();
838
839 for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
840 ++Iter1, ++Iter2)
841 {
842 if (*Iter1 != *Iter2)
843 return false;
844 }
845 return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
846 }

◆ operator|=()

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

Definition at line 849 of file SparseBitVector.h.

850 {
851 if (this == &RHS)
852 return false;
853
854 bool changed = false;
856 ElementListConstIter Iter2 = RHS.Elements.begin();
857
858 // If RHS is empty, we are done
859 if (RHS.Elements.empty())
860 return false;
861
862 while (Iter2 != RHS.Elements.end())
863 {
864 if (Iter1 == Elements.end() || Iter1->index() > Iter2->index())
865 {
866 Elements.insert(Iter1, *Iter2);
867 ++Iter2;
868 changed = true;
869 }
870 else if (Iter1->index() == Iter2->index())
871 {
872 changed |= Iter1->unionWith(*Iter2);
873 ++Iter1;
874 ++Iter2;
875 }
876 else
877 {
878 ++Iter1;
879 }
880 }
881 CurrElementIter = Elements.begin();
882 return changed;
883 }

◆ reset()

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

Definition at line 766 of file SparseBitVector.h.

767 {
768 if (Elements.empty())
769 return;
770
771 unsigned ElementIndex = Idx / ElementSize;
773
774 // If we can't find an element that is supposed to contain this bit, there
775 // is nothing more to do.
776 if (ElementIter == Elements.end() ||
777 ElementIter->index() != ElementIndex)
778 return;
779 ElementIter->reset(Idx % ElementSize);
780
781 // When the element is zeroed out, delete it.
782 if (ElementIter->empty())
783 {
785 Elements.erase(ElementIter);
786 }
787 }
ElementListIter FindLowerBound(unsigned ElementIndex)

◆ set()

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

Definition at line 789 of file SparseBitVector.h.

790 {
791 unsigned ElementIndex = Idx / ElementSize;
793 if (Elements.empty())
794 {
795 ElementIter = Elements.emplace(Elements.end(), ElementIndex);
796 }
797 else
798 {
799 ElementIter = FindLowerBound(ElementIndex);
800
801 if (ElementIter == Elements.end() ||
802 ElementIter->index() != ElementIndex)
803 {
804 // We may have hit the beginning of our SparseBitVector, in which case,
805 // we may need to insert right after this element, which requires moving
806 // the current iterator forward one, because insert does insert before.
807 if (ElementIter != Elements.end() &&
808 ElementIter->index() < ElementIndex)
809 ++ElementIter;
810 ElementIter = Elements.emplace(ElementIter, ElementIndex);
811 }
812 }
814
816 }

◆ test()

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

Definition at line 750 of file SparseBitVector.h.

751 {
752 if (Elements.empty())
753 return false;
754
755 unsigned ElementIndex = Idx / ElementSize;
757
758 // If we can't find an element that is supposed to contain this bit, there
759 // is nothing more to do.
760 if (ElementIter == Elements.end() ||
761 ElementIter->index() != ElementIndex)
762 return false;
763 return ElementIter->test(Idx % ElementSize);
764 }
ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const

◆ test_and_set()

template<unsigned ElementSize = 128>
bool SVF::SparseBitVector< ElementSize >::test_and_set ( unsigned  Idx)
inline

Definition at line 818 of file SparseBitVector.h.

819 {
820 bool old = test(Idx);
821 if (!old)
822 {
823 set(Idx);
824 return true;
825 }
826 return false;
827 }
bool test(unsigned Idx) const
void set(unsigned Idx)

Friends And Related Symbol Documentation

◆ SVFIRReader

template<unsigned ElementSize = 128>
friend class SVFIRReader
friend

Definition at line 504 of file SparseBitVector.h.

◆ SVFIRWriter

template<unsigned ElementSize = 128>
friend class SVFIRWriter
friend

Definition at line 503 of file SparseBitVector.h.

Member Data Documentation

◆ CurrElementIter

template<unsigned ElementSize = 128>
ElementListIter SVF::SparseBitVector< ElementSize >::CurrElementIter
mutableprivate

Definition at line 518 of file SparseBitVector.h.

◆ Elements

template<unsigned ElementSize = 128>
ElementList SVF::SparseBitVector< ElementSize >::Elements
private

Definition at line 514 of file SparseBitVector.h.


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