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

◆ ElementListConstIter

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

Definition at line 506 of file SparseBitVector.h.

◆ ElementListIter

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

Definition at line 505 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 507 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 1159 of file SparseBitVector.h.

1160 {
1161 return iterator(this);
1162 }
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 1117 of file SparseBitVector.h.

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

◆ count()

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

Definition at line 1148 of file SparseBitVector.h.

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

◆ empty()

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

Definition at line 1143 of file SparseBitVector.h.

1144 {
1145 return Elements.empty();
1146 }

◆ end()

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

Definition at line 1164 of file SparseBitVector.h.

1165 {
1166 return iterator(this, true);
1167 }

◆ find_first()

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

Definition at line 1125 of file SparseBitVector.h.

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

◆ find_last()

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

Definition at line 1134 of file SparseBitVector.h.

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

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

521 {
522
523 // We cache a non-const iterator so we're forced to resort to const_cast to
524 // get the begin/end in the case where 'this' is const. To avoid duplication
525 // of code with the only difference being whether the const cast is present
526 // 'this' is always const in this particular function and we sort out the
527 // difference in FindLowerBound and FindLowerBoundConst.
529 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
531 const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
532
533 if (Elements.empty())
534 {
536 return CurrElementIter;
537 }
538
539 // Make sure our current iterator is valid.
540 if (CurrElementIter == End)
541 {
543 }
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 1081 of file SparseBitVector.h.

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

◆ intersects() [2/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 {
1077 return intersects(*RHS);
1078 }
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 949 of file SparseBitVector.h.

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

◆ intersectWithComplement() [2/4]

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

Definition at line 1014 of file SparseBitVector.h.

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

1008 {
1010 }

◆ intersectWithComplement() [4/4]

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

Definition at line 1069 of file SparseBitVector.h.

1071 {
1073 }

◆ operator!=()

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

Definition at line 831 of file SparseBitVector.h.

832 {
833 return !(*this == RHS);
834 }

◆ operator&=()

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

Definition at line 888 of file SparseBitVector.h.

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

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

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

◆ operator|=()

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

Definition at line 851 of file SparseBitVector.h.

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

◆ reset()

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

Definition at line 768 of file SparseBitVector.h.

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

◆ set()

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

Definition at line 791 of file SparseBitVector.h.

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

◆ 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 {
763 return false;
764 }
765 return ElementIter->test(Idx % ElementSize);
766 }
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 820 of file SparseBitVector.h.

821 {
822 bool old = test(Idx);
823 if (!old)
824 {
825 set(Idx);
826 return true;
827 }
828 return false;
829 }
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 516 of file SparseBitVector.h.

◆ Elements

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

Definition at line 512 of file SparseBitVector.h.


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