nanxing_stl/lib/extend/filter.h

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<exception>
#include<cstdint>
#include"../basic/nanxing_operator_check.h"

namespace nanxing_extend
{
    //这是个意外，本来是想工厂类和不同的过滤器划分到不同文件的，但是由于贯彻head_only,还没想出来怎么组织文件，只能丢在一起了
    //同时也是一个控制类，即这个类本身带有控制功能，只允许一次产生持有唯一的filter
    //如果不对产生的类进行管控，最后的结果很可能是完全无法处理，因为C++中内存分配方式过于多样，malloc，new，new[],数组。。。。乱七八糟，最后类内生成的空间完全无法析构，因为根本不知道类内怎么实现的
    //当然也可以通过返回智能指针的方式进行管控，但是没有选择那么做的原因在于过滤器本身不会大量存在
    //一个程序中最多一到两个过滤器
    //但是但是相信我不会有God class
    template<typename K>
    class FilterPolicy
    {
        static_assert(NANXING_BASIC_OPERATOR_(K,compare),"the type of key cannot compare");
    private:
        FilterPolicy& operator=(FilterPolicy const&)=delete;
        FilterPolicy(FilterPolicy const&)=delete;       
        FilterPolicy* producter=nullptr;                        //用于管控生成的类
    public:
        //限制当主动生成一个工厂类后，不管怎么赋值，最后只有一个工厂
        //move-only    
        FilterPolicy(){}
        FilterPolicy(FilterPolicy&&){}

        virtual void policy_print(){}                //输出对应的计算公式 
    
    #ifdef NANXING_DEBUG_
        virtual void parameter_print(){}     //输出过滤器的参数 
    #endif          
        virtual void insert(K key)noexcept{}                              //当向数据库插入数据后对过滤器进行调整      
        
        [[nodiscard]] 
        //cppcheck还不能识别C++17引入的属性
        virtual bool check(K key)noexcept{}
        //两个工厂函数用于生成不同的过滤器    
        FilterPolicy* creat_Bloomfilter(int N,float P);
        FilterPolicy* creat_Cuckoofilter();  
        virtual void init_filter(){}    //初始化过滤器

           

    #ifdef NANXING_DEBUG_
        virtual auto get_k()->uint64_t{}

        virtual auto get_m()->uint64_t{}
    #endif
        virtual ~FilterPolicy(){
            if(producter!=nullptr)
            {
                delete producter;
            }
        };
    };

    //bloomfilter
    template<typename K>
    class bloomfilter:public FilterPolicy<K>
    {
        static_assert(NANXING_BASIC_OPERATOR_(K,compare),"the type of key cannot compare");
    private:
        //这里使用线性混合同余来构造哈希函数，因为线性混合同余的随机性和运算效率的平衡比较好
        constexpr static const int hash_prime_number1[10]={52223,52237,79939,19937,8243,24133,12647,13147,62459,94547};                //给出10个大素数作为哈希函数的素数种子
        constexpr static const int hash_prime_number2[10]={94399,94421,94427,94433,94439,94441,94447,94463,94477,94483};             //哈希函数的置偏值
        struct param{
            float P;          //概率参数
            int k=0;             //哈希函数个数
            uint64_t n;             //n数据长度
            uint64_t m=0;              //bloomfilter长度
            param(float _p,uint64_t _n):P(_p),n(_n){}
        };
    private:
        char* bitarray;               //bloomfilter的核心数据结构,一个比特数组
        param parameter;
        
    protected:
        bloomfilter()=delete;
        bloomfilter(bloomfilter&)=delete;
        bloomfilter& operator=(bloomfilter)=delete;           //不允许复制构造
        void caculater()noexcept                              //计算bloomfilter的参数
        {
            this->parameter.m=static_cast<uint64_t>(-(parameter.n*std::log(parameter.P)/0.48045301));        //这两个数字分别是ln2和(ln2)^2,位公式中的常数
            this->parameter.k=static_cast<uint64_t>(0.693147*(parameter.m/parameter.n)+1);

        }
        int hash_function(int i,K data)                              //i代表第i个哈希函数,返回在bloomfilter中的位置
        {
            return ((static_cast<int>(data))*(this->hash_prime_number1[i])+(this->hash_prime_number2[i]))%(this->parameter.m);
        }
    public:
        bloomfilter(float _p,uint64_t _n):bitarray(nullptr),parameter(_p,_n){}

        void init_filter()override{
        LOOP:
            caculater();
        LOOP1:
            try{
                bitarray=new char[static_cast<uint64_t>(parameter.m/8)+1];           //构建数组
            }
            catch(std::bad_alloc)
            {
                char tmp_input;
                std::cerr<<"May not have enough memory to use"<<std::endl;
                std::cerr<<"if you want to try again,please input r"<<std::endl;
                std::cerr<<"if you want to exit please input e"<<std::endl;
                std::cerr<<"if you want to use less bloomfilter with higher error rates,please input p"<<std::endl;
                std::cin>>tmp_input;
                switch(tmp_input)
                {
                    case 'r':
                        goto LOOP1;
                        break;
                    case 'e':
                        std::terminate();
                        break;
                    case 'p':
                        std::cerr<<"please input the new P by float"<<std::endl;
                        std::cin>>this->parameter.P;
                        goto LOOP;
                        break;
                }
            }
            std::memset(bitarray,0,sizeof(char)*static_cast<u_int64_t>(parameter.m/8)+1);   //初始化
        }
 
        void policy_print()override                  //打印出使用的公式
        {
            std::cout<<"m=-((nlnP)/((ln2)^2))"<<"//m为bloomfilter的长度"<<std::endl;
            std::cout<<"k=ln2*(m/n)"<<"//k为所需的哈希函数的个数"<<std::endl;
        }

        void insert(K key)noexcept override
        {
            if(this->parameter.k==0)
            {
                std::cerr<<"the filter never init,and the filter is useless."<<std::endl;
                return;
            }
            for(int i=0;i<this->parameter.k;i++)
            {
                int tmp=this->hash_function(i,key);
                uint64_t filter_u=static_cast<uint64_t>(tmp/8);
                int move=tmp%8;
                this->bitarray[filter_u]=this->bitarray[filter_u]|('1'<<(7-move));
            }
        }

        [[nodiscard]]bool check(K key)noexcept override
        {
            if(this->parameter.k==0)
            {
                std::cerr<<"the filter never init,and the filter is useless."<<std::endl;
                return false;
            }
            for(int i=0;i<this->parameter.k;i++)  
            {
                int tmp=this->hash_function(i,key);
                uint64_t filter_u=static_cast<uint64_t>(tmp/8);
                int move=tmp%8;
                if((this->bitarray[filter_u]&('1'<<(7-move)))==0)        //若对应位为0
                {
                    return false;
                }
            }
            return true;
        }
    #ifdef NANXING_DEBUG_
        void parameter_print()override
        {
            std::cout<<"(m,n,k,p) = "<<"("<<this->parameter.m<<","<<parameter.n<<","<<parameter.k<<","<<parameter.P<<")";
        }

        
        auto get_k()->uint64_t override
        {
            return this->parameter.k;
        }

        auto get_m()->uint64_t override
        {
            return this->parameter.m;
        }
    #endif
        virtual ~bloomfilter()
        {
            if(bitarray!=nullptr)
            {
                delete[] bitarray;
            }
        }  
    };

    //布谷鸟过滤器
    template<typename K>
    class Cuckoofilter:public FilterPolicy<K>
    {
        static_assert(NANXING_BASIC_OPERATOR_(K,compare),"the type of key cannot compare");
    };

    template<typename K>
    FilterPolicy<K>* FilterPolicy<K>::creat_Bloomfilter(int N,float P)
    {
        if(producter!=nullptr)
        {
            delete producter;
        }
        producter=new bloomfilter<K>(P,N);
        return producter;
    }

    template<typename K>
    FilterPolicy<K>* FilterPolicy<K>::creat_Cuckoofilter()
    {
        if(producter!=nullptr)
        {
            delete producter;
        }
        producter=new Cuckoofilter<K>;
        return producter;
    }
}