CoreBitVector.h

Go to the documentation of this file.

//===- CoreBitVector.h -- Dynamically sized bit vector data structure ------------//
 
/*
 * CoreBitVector.h
 *
 * Contiguous bit vector which resizes as required by common operations.
 *
 *  Created on: Jan 31, 2021
 *      Author: Mohamad Barbar
 */
 
#ifndef COREBITVECTOR_H_
#define COREBITVECTOR_H_
 
#include <assert.h>
#include <vector>
 
#include "SVFIR/SVFType.h"
 
namespace SVF
{
 
class CoreBitVector
{
public:
    typedef unsigned long long Word;
    static const size_t WordSize;
 
    class CoreBitVectorIterator;
    typedef CoreBitVectorIterator const_iterator;
    typedef const_iterator iterator;
 
public:
    CoreBitVector(void);
 
    CoreBitVector(size_t n);
 
    CoreBitVector(const CoreBitVector &cbv);
 
    CoreBitVector(CoreBitVector &&cbv);
 
    CoreBitVector &operator=(const CoreBitVector &rhs);
 
    CoreBitVector &operator=(CoreBitVector &&rhs);
 
    bool empty(void) const;
 
    u32_t count(void) const;
 
    void clear(void);
 
    bool test(u32_t bit) const;
 
    bool test_and_set(u32_t bit);
 
    void set(u32_t bit);
 
    void reset(u32_t bit);
 
    bool contains(const CoreBitVector &rhs) const;
 
    bool intersects(const CoreBitVector &rhs) const;
 
    bool operator==(const CoreBitVector &rhs) const;
 
    bool operator!=(const CoreBitVector &rhs) const;
 
    bool operator|=(const CoreBitVector &rhs);
 
    bool operator&=(const CoreBitVector &rhs);
 
    bool operator-=(const CoreBitVector &rhs);
 
    bool intersectWithComplement(const CoreBitVector &rhs);
 
    void intersectWithComplement(const CoreBitVector &lhs, const CoreBitVector &rhs);
 
    size_t hash(void) const;
 
    const_iterator begin(void) const;
    const_iterator end(void) const;
 
private:
    void extendBackward(u32_t bit);
 
    void extendForward(u32_t bit);
 
    void extendTo(u32_t bit);
 
    size_t indexForBit(u32_t bit) const;
 
    bool canHold(u32_t bit) const;
 
    u32_t finalBit(void) const;
 
    u32_t firstCommonBit(const CoreBitVector &rhs) const;
 
    size_t nextSetIndex(const size_t start) const;
 
public:
    class CoreBitVectorIterator
    {
    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 &;
 
        CoreBitVectorIterator(void) = delete;
 
        CoreBitVectorIterator(const CoreBitVector *cbv, bool end=false);
 
        CoreBitVectorIterator(const CoreBitVectorIterator &cbv) = default;
        CoreBitVectorIterator(CoreBitVectorIterator &&cbv) = default;
 
        CoreBitVectorIterator &operator=(const CoreBitVectorIterator &cbv) = default;
        CoreBitVectorIterator &operator=(CoreBitVectorIterator &&cbv) = default;
 
        const CoreBitVectorIterator &operator++(void);
 
        const CoreBitVectorIterator operator++(int);
 
        u32_t operator*(void) const;
 
        bool operator==(const CoreBitVectorIterator &rhs) const;
 
        bool operator!=(const CoreBitVectorIterator &rhs) const;
 
    private:
        bool atEnd(void) const;
 
    private:
        const CoreBitVector *cbv;
        std::vector<Word>::const_iterator wordIt;
        u32_t bit;
    };
 
private:
    u32_t offset;
    std::vector<Word> words;
};
 
template <>
struct Hash<CoreBitVector>
{
    size_t operator()(const CoreBitVector &cbv) const
    {
        return cbv.hash();
    }
};
 
} // End namespace SVF
 
#endif  // COREBITVECTOR_H_