PointsTo.h

Go to the documentation of this file.

//===- PointsTo.h -- Wrapper of set-like data structures  ------------//
 
/*
 * PointsTo.h
 *
 * Abstracts away data structures to be used as points-to sets.
 *
 *  Created on: Feb 01, 2021
 *      Author: Mohamad Barbar
 */
 
#ifndef POINTSTO_H_
#define POINTSTO_H_
 
#include <memory>
#include <vector>
 
#include "Util/GeneralType.h"
#include "Util/BitVector.h"
#include "Util/CoreBitVector.h"
#include "Util/SparseBitVector.h"
 
namespace SVF
{
 
class PointsTo
{
public:
    enum Type
    {
        SBV,
        CBV,
        BV,
    };
 
    class PointsToIterator;
    typedef PointsToIterator const_iterator;
    typedef const_iterator iterator;
 
    typedef std::shared_ptr<std::vector<NodeID>> MappingPtr;
 
public:
    PointsTo();
    PointsTo(const PointsTo &pt);
    PointsTo(PointsTo &&pt) noexcept ;
 
    ~PointsTo();
 
    PointsTo &operator=(const PointsTo &rhs);
 
    PointsTo &operator=(PointsTo &&rhs) noexcept ;
 
    bool empty() const;
 
    u32_t count() const;
 
    void clear();
 
    bool test(u32_t n) const;
 
    bool test_and_set(u32_t n);
 
    void set(u32_t n);
 
    void reset(u32_t n);
 
    bool contains(const PointsTo &rhs) const;
 
    bool intersects(const PointsTo &rhs) const;
 
    int find_first();
 
    bool operator==(const PointsTo &rhs) const;
 
    bool operator!=(const PointsTo &rhs) const;
 
    bool operator|=(const PointsTo &rhs);
    bool operator|=(const NodeBS &rhs);
 
    bool operator&=(const PointsTo &rhs);
 
    bool operator-=(const PointsTo &rhs);
 
    bool intersectWithComplement(const PointsTo &rhs);
 
    void intersectWithComplement(const PointsTo &lhs, const PointsTo &rhs);
 
    NodeBS toNodeBS() const;
 
    size_t hash() const;
 
    void checkAndRemap();
 
    const_iterator begin() const
    {
        return PointsToIterator(this);
    }
    const_iterator end() const
    {
        return PointsToIterator(this, true);
    }
 
    MappingPtr getNodeMapping() const;
 
    static MappingPtr getCurrentBestNodeMapping();
    static MappingPtr getCurrentBestReverseNodeMapping();
    static void setCurrentBestNodeMapping(MappingPtr newCurrentBestNodeMapping,
                                          MappingPtr newCurrentBestReverseNodeMapping);
 
private:
    NodeID getInternalNode(NodeID n) const;
 
    NodeID getExternalNode(NodeID n) const;
 
    bool metaSame(const PointsTo &pt) const;
 
private:
    static MappingPtr currentBestNodeMapping;
    static MappingPtr currentBestReverseNodeMapping;
 
    union
    {
        SparseBitVector<> sbv;
        CoreBitVector cbv;
        BitVector bv;
    };
 
    enum Type type;
    MappingPtr nodeMapping;
    MappingPtr reverseNodeMapping;
 
public:
    class PointsToIterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = u32_t;
        using difference_type = std::ptrdiff_t;
        using pointer = u32_t *;
        using reference = u32_t &;
 
        PointsToIterator() = delete;
        PointsToIterator(const PointsToIterator &pt);
        PointsToIterator(PointsToIterator &&pt) noexcept ;
 
        explicit PointsToIterator(const PointsTo *pt, bool end=false);
 
        PointsToIterator &operator=(const PointsToIterator &rhs);
        PointsToIterator &operator=(PointsToIterator &&rhs) noexcept ;
 
        const PointsToIterator &operator++();
 
        const PointsToIterator operator++(int);
 
        u32_t operator*() const;
 
        bool operator==(const PointsToIterator &rhs) const;
 
        bool operator!=(const PointsToIterator &rhs) const;
 
    private:
        bool atEnd() const;
 
    private:
        const PointsTo *pt;
        union
        {
            SparseBitVector<>::iterator sbvIt;
            CoreBitVector::iterator cbvIt;
            BitVector::iterator bvIt;
        };
    };
};
 
PointsTo operator|(const PointsTo &lhs, const PointsTo &rhs);
 
PointsTo operator&(const PointsTo &lhs, const PointsTo &rhs);
 
PointsTo operator-(const PointsTo &lhs, const PointsTo &rhs);
 
} // End namespace SVF
 
template <>
struct std::hash<SVF::PointsTo>
{
    size_t operator()(const SVF::PointsTo &pt) const
    {
        return pt.hash();
    }
};
 
 
#endif  // POINTSTO_H_