Static Value-Flow Analysis
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | 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
 

Detailed Description

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

Definition at line 499 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 502 of file SparseBitVector.h.

◆ ElementListConstIter

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

Definition at line 504 of file SparseBitVector.h.

◆ ElementListIter

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

Definition at line 503 of file SparseBitVector.h.

◆ iterator

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

Definition at line 713 of file SparseBitVector.h.

Member Enumeration Documentation

◆ anonymous enum

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

Definition at line 505 of file SparseBitVector.h.

Constructor & Destructor Documentation

◆ SparseBitVector() [1/3]

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

Definition at line 715 of file SparseBitVector.h.

715: 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 717 of file SparseBitVector.h.

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

◆ SparseBitVector() [3/3]

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

Definition at line 719 of file SparseBitVector.h.

720 : 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 1153 of file SparseBitVector.h.

1154 {
1155 return iterator(this);
1156 }
SparseBitVectorIterator iterator

◆ clear()

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

Definition at line 723 of file SparseBitVector.h.

724 {
725 Elements.clear();
726 }

◆ contains()

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

Definition at line 1111 of file SparseBitVector.h.

1112 {
1113 SparseBitVector<ElementSize> Result(*this);
1114 Result &= RHS;
1115 return (Result == RHS);
1116 }

◆ count()

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

Definition at line 1142 of file SparseBitVector.h.

1143 {
1144 unsigned BitCount = 0;
1145 for (ElementListConstIter Iter = Elements.begin();
1146 Iter != Elements.end();
1147 ++Iter)
1148 BitCount += Iter->count();
1149
1150 return BitCount;
1151 }
typename ElementList::const_iterator ElementListConstIter

◆ empty()

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

Definition at line 1137 of file SparseBitVector.h.

1138 {
1139 return Elements.empty();
1140 }

◆ end()

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

Definition at line 1158 of file SparseBitVector.h.

1159 {
1160 return iterator(this, true);
1161 }

◆ find_first()

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

Definition at line 1119 of file SparseBitVector.h.

1120 {
1121 if (Elements.empty())
1122 return -1;
1123 const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
1124 return (First.index() * ElementSize) + First.find_first();
1125 }

◆ find_last()

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

Definition at line 1128 of file SparseBitVector.h.

1129 {
1130 if (Elements.empty())
1131 return -1;
1132 const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
1133 return (Last.index() * ElementSize) + Last.find_last();
1134 }

◆ FindLowerBound()

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

Definition at line 567 of file SparseBitVector.h.

568 {
569 return FindLowerBoundImpl(ElementIndex);
570 }
ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const

◆ FindLowerBoundConst()

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

Definition at line 563 of file SparseBitVector.h.

564 {
565 return FindLowerBoundImpl(ElementIndex);
566 }

◆ FindLowerBoundImpl()

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

Definition at line 518 of file SparseBitVector.h.

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

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

◆ intersects() [2/2]

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

Definition at line 1069 of file SparseBitVector.h.

1070 {
1071 return intersects(*RHS);
1072 }
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 943 of file SparseBitVector.h.

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

◆ intersectWithComplement() [2/4]

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

Definition at line 1008 of file SparseBitVector.h.

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

1002 {
1004 }

◆ intersectWithComplement() [4/4]

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

Definition at line 1063 of file SparseBitVector.h.

1065 {
1067 }

◆ operator!=()

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

Definition at line 825 of file SparseBitVector.h.

826 {
827 return !(*this == RHS);
828 }

◆ operator&=()

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

Definition at line 882 of file SparseBitVector.h.

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

◆ operator=() [1/2]

Definition at line 729 of file SparseBitVector.h.

730 {
731 if (this == &RHS)
732 return *this;
733
734 Elements = RHS.Elements;
735 CurrElementIter = Elements.begin();
736 return *this;
737 }

◆ operator=() [2/2]

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

Definition at line 738 of file SparseBitVector.h.

739 {
740 Elements = std::move(RHS.Elements);
741 CurrElementIter = Elements.begin();
742 return *this;
743 }

◆ operator==()

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

Definition at line 830 of file SparseBitVector.h.

831 {
833 ElementListConstIter Iter2 = RHS.Elements.begin();
834
835 for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
836 ++Iter1, ++Iter2)
837 {
838 if (*Iter1 != *Iter2)
839 return false;
840 }
841 return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
842 }

◆ operator|=()

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

Definition at line 845 of file SparseBitVector.h.

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

◆ reset()

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

Definition at line 762 of file SparseBitVector.h.

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

◆ set()

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

Definition at line 785 of file SparseBitVector.h.

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

◆ test()

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

Definition at line 746 of file SparseBitVector.h.

747 {
748 if (Elements.empty())
749 return false;
750
751 unsigned ElementIndex = Idx / ElementSize;
753
754 // If we can't find an element that is supposed to contain this bit, there
755 // is nothing more to do.
756 if (ElementIter == Elements.end() ||
757 ElementIter->index() != ElementIndex)
758 return false;
759 return ElementIter->test(Idx % ElementSize);
760 }
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 814 of file SparseBitVector.h.

815 {
816 bool old = test(Idx);
817 if (!old)
818 {
819 set(Idx);
820 return true;
821 }
822 return false;
823 }
bool test(unsigned Idx) const
void set(unsigned Idx)

Member Data Documentation

◆ CurrElementIter

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

Definition at line 514 of file SparseBitVector.h.

◆ Elements

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

Definition at line 510 of file SparseBitVector.h.


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