nanxing_stl/lib/extend/skiplist.h

#include"../basic/nanxing_operator_check.h"
#include<cstdlib>
#include<cstring> 
#include<exception>
#include<random>
#include<shared_mutex>
#include <variant>
#include<chrono>
#include<iostream>

namespace nanxing_extend
{
    //限定为侵入式链表结构，因为这样方便空间的控制，可以直接在节点类中析构全部的空间
    static int count=0;
    //错误处理机制
    class nextpoint_new:std::exception             //skip_node分配空间失败的时候
    {
        const char* what() const noexcept
        {
            return "malloc next_node point falure";
        }
    };

    class newNode_error:std::exception             //申请新的空间的时候
    {
        const char* what() const noexcept
        {
            return "malloc new node error";
        }
    };

    class random_error:std::exception             //申请预设随机数空间的时候
    {
        const char* what() const noexcept
        {
            return "malloc random space error";
        }
    };

    enum class Skip_result          //跳表操作的结果           
    {
        successufl,
        
    #ifdef SKIP_MAX_SIZE
        full,
    #endif
    #ifdef SKIP_MAX_SIZE
        too_small,
    #endif
        falure,
        exit,
        empty,

    };

    //注意这里的V只能是非指针类型，即侵入式数据结构因为这样的内存是可控的
    template<typename K,typename V>
    struct skip_node
    {
        static_assert(NANXING_BASIC_OPERATOR_(K,compare),"the type of K is error");
        static_assert(NANXING_BASIC_OPERATOR_(V,compare),"the type of V is error");
        static_assert(NANXING_OPERATOR_FORBIDEN_(V,point),"the type of V cannot be point");              //限定为侵入式数据结构
        skip_node<K,V>** next_node; 
        V value;
        K key;
    private:
        
        int level;
    public:
        skip_node(){};
        skip_node(K _key,V _value,int _level):key(_key),value(_value),level(_level){};
        void init_next(int level)
        {
            try
            {
                next_node=::new skip_node<K,V>*[level];
            }
            catch(std::bad_alloc){        //捕获内存分配错误
                throw nextpoint_new();       //重新抛出一个定制的更详细的类型用以明确错误的具体位置
            }
            std::memset(next_node,0,sizeof(skip_node<K,V>*)*level);
        }
        K get_key(){ return key; }
        ~skip_node()
        {
            delete[] this->next_node;              //将申请的next指针存储空间完全释放
        }
    };

    template<typename K,typename V>
    class skipList
    {
        static_assert(NANXING_BASIC_OPERATOR_(K,compare),"the type of K is error");
        static_assert(NANXING_BASIC_OPERATOR_(V,compare),"the type of V is error");
        static_assert(NANXING_OPERATOR_FORBIDEN_(V,point),"the type of V cannot be point");              //限定为侵入式数据结构
    private:
        using Node=skip_node<K,V>;
        using ptr=Node*;
        using Nptr=Node**;
        //由于C++的便利性我们考虑使用带头节点的跳表(C++允许对数据不进行初始化(默认构造函数))
    #ifdef NANXING_THREAD_
        std::shared_mutex RW_lock;           //读写锁
    #endif
        Nptr head;                      //头节点
        int max_level;                 //最大高度
        int* random_level=nullptr;             //如果启用随机数表这个就非空，反之为nullptr
        //当不启用随机数表，使用rand()构造随机数，启用的时候用mt19773构造随机数
        int current_level;              //跳表当前高度
        int current_size;               //跳表当前尺寸
        //这里出于一个考虑，当跳表单纯作为小数据内存数据库，单表大小限制是没有意义的
        //但是像level_db这样作为KV数据库的缓存的时候，就需要限制大小进行落盘
    #ifdef SKIP_MAX_SIZE
        int max_size;                   //跳表允许的最大尺寸
    #endif
    public:

    #ifndef SKIP_MAX_SIZE
        skipList(int _max_level):max_level(_max_level),random_level(nullptr)
        {
            try
            {
                Node* middle=::new skip_node<K,V>;
                middle->init_next(max_level);
                head=::new  Node*[max_level];
                for(int i=0;i<max_level;i++)                
                {
                    head[i]=middle;
                }
            }
            catch(std::bad_alloc)
            {
                throw newNode_error();        //重新抛出更详细的错误类型
            }
            if(max_level==0){                //如果将高度设置为0直接调用terminate打断整个程序执行
                std::cerr<<"the level of skiplist cannot set zero"<<std::endl;
                std::terminate();
            }
        }
    #else
        skipList(int _max_level,int _max_size):max_size(_max_size),max_level(_max_level),random_level(nullptr)
        {
            try
            {
                Node* middle=::new skip_node;
                middle->init_next(max_level);
                head=::new (Node*)[max_level];
                for(auto& i in head)                
                {
                    i=middle;
                }
            }
            catch(std::bad_alloc)
            {
                throw newNode_error();
            }
        }
    #endif              

    #ifdef _RANDOM_LIST_
        void create_random_list()                 //直接生成随机数表
        {
        #ifdef NANXING_THREAD_
            std::lock_guard<std::shared_mutex> lock(RW_lock);             
        #endif
            if(random_level!=nullptr)
            {
                return;
            }            
            try{
                random_level=::new int[1024];                     //刚好是一页的大小（4KB）
            }
            catch(std::bad_alloc)
            {
                throw random_error();
                return;
            }
            std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
            for(int i=0;i<1024;i++)
            {
                random_level[i]=(rnd()%max_level)+1;
            }
        }
    #endif
         
        auto insert(K _key,V _value)->std::variant<Skip_result,V>              //如果相同的时候我们考虑将value返回，由于限制为侵入式链表因此实际上不会内存泄露
        {
        #ifdef NANXING_THREAD_
            std::lock_guard<std::shared_mutex> lock(RW_lock);             
        #endif
        
        #ifdef SKIP_MAX_SIZE
            if(current_size==max_size)
            {
                return sk=Skip_result::full;
            }
        #endif
            int rand_level=0;
            ptr* updata=new ptr[max_level];          //用于更新的数组
            for(int i=0;i<max_level;i++)
            {
                updata[i]=nullptr;
            }
            ptr point=head[max_level-1];
            
            ptr new_node;
            std::variant<Skip_result,V> sk;
            for(int i=max_level-1;i>=0;i--)
            {
                for(;;)
                {
                    if(point->next_node[i]==nullptr)
                    {
                        updata[i]=point;
                        break;
                    }
                    else if(point->next_node[i]->key>=_key)
                    {
                        if(point->next_node[i]->key==_key)
                        {
                            sk=std::move(point->next_node[i]->value);          //这个值已经不需要了，直接移动
                            point->next_node[i]->value=_value;
                            return sk;
                        }
                        else
                        {
                            updata[i]=point;
                            break;
                        }
                    }
                    else{
                        point=point->next_node[i];              //更新point指针
                    }
                }
            }
            [[likely]]
            //cppcheck还不能识别C++17引入的属性
            if(random_level!=nullptr)
            {
                rand_level=random_level[current_size%1024];
            }
            else
            {
                rand_level=rand()%max_level;
            }
            ptr tmp=nullptr;
            new_node=new skip_node(_key,_value,rand_level);
            new_node->init_next(rand_level);
            for(int i=0;i<rand_level;i++)
            {
                tmp=updata[i]->next_node[i];
                updata[i]->next_node[i]=new_node;
                new_node->next_node[i]=tmp;
            }
            if(rand_level>current_level)
            {
                current_level=rand_level;
            }
            current_size++;
            sk=Skip_result::successufl;
            return sk;
        }

        auto Delete_node(K _key) noexcept ->std::variant<Skip_result,V>            //由于使用侵入式数据结构，因此当节点空间析构的时候对应的数据也会完全析构
        {
            std::variant<Skip_result,V> sk;
            if(current_size==0)
            {
                std::cerr<<"The skiplist is empty"<<std::endl;
                return sk=Skip_result::empty;
            }
            else
            {
                ptr updata[max_level]={nullptr};          //用于更新的数组
                ptr point=head[max_level-1];
                ptr tmp;
                for(int i=max_level-1;i>=0;i--)
                {
                    for(;;)
                    {
                        if(point->next_node[i]==nullptr)
                        {
                            break;
                        }
                        else if(point->next_node[i]->key>=_key)
                        {
                            if(point->next_node[i]->key==_key)
                            {
                                updata[i]=point;
                            }
                            else{
                                break;
                            }

                        }
                        else{
                            point=point->next_node[i];              //更新point指针
                        }
                    }
                }         
                if(updata[0]!=nullptr)
                {
                    tmp=updata[0]->next_node[0];          //需要被删除的数据结构
                    int i=0;
                    while(i<max_level-1&&updata[i]!=0)
                    {
                        updata[i]->next_node[i]=tmp->next_node[i];
                        i++;
                    }
                    delete tmp;
                    sk=Skip_result::successufl;
                    return sk;
                }
            }
            sk=Skip_result::falure;
            return sk;
        }

        [[nodiscard]]                    
        auto search(K _key) noexcept ->std::variant<Skip_result,V>{       //不涉及任何内存分配相关任务，因此是异常安全的
        #ifdef NANXING_THREAD_
            std::shared_lock<std::shared_mutex> lock(RW_lock);             
        #endif        
            std::variant<Skip_result,V> sk;
            ptr tmp=head[current_level-1];
            int tmp_level=current_level-1;
            for(int i=tmp_level;i>=0;i--)
            {
                while(tmp->next_node[tmp_level]!=nullptr)
                {
                    if(tmp->next_node[tmp_level]->key>=_key)
                    {
                        if(tmp->next_node[tmp_level]->key==_key)
                        {
                            return sk=Skip_result::exit;
                        }
                        else{
                            break;            //跳出开始下一层循环
                        }
                    }
                    else{
                        tmp=tmp->next_node[tmp_level];
                    }
                }
            }
            return sk=Skip_result::falure;
        }
                
    #ifdef NANXING_DEBUG_
        void Print()noexcept
        {
            ptr tmp=head[0]->next_node[0];
            while(tmp!=nullptr&&tmp->next_node[0]!=nullptr)         //这里用了截断的技巧，即第一个条件不成立就不会触发第二个条件运行
            {
                std::cout<<"("<<tmp->get_key()<<","<<tmp->value<<")"<<"->";
                tmp=tmp->next_node[0];
                count++;
            }
            if(tmp!=nullptr)
            {
                std::cout<<"("<<tmp->get_key()<<","<<tmp->value<<")"<<std::endl;
                count++;
            }
            std::cout<<"count ="<<count<<std::endl;
        }
    #endif

    #ifdef SKIP_MAX_SIZE
        [[nodicard]]
        inline auto change_size(int _max_size)->std::variant<Skip_result,V> noexcept
        {
            std::variant<
            if(_max_size>this->max_size)
            {
                this->max_size=_max_size;
                tmp=Skip_result::successufl;
                return tmp;
            }
            else
            {
                tmp=Skip_result::too_samll;
                return tmp;
            }
        } 
    #endif

    #ifdef _NANXING_TEST_
        inline void insert_check()
        {
            ptr tmp=head[0]->next_node[0];
            K tmp_key;
            if(tmp==nullptr)
            {
                std::cerr<<"the skiplist is empty"<<std::endl;
                std::terminate();
            }
            else
            {
                tmp_key=head[0]->next_node[0]->key;
            }
            tmp=tmp->next_node[0];
            while(tmp->next_node[0]!=nullptr)
            {
                if(tmp->next_node[0]->key<tmp_key)
                {
                    std::cerr<<"THE skiplist insert error"<<std::endl;
                    std::terminate();
                }
                tmp_key=tmp->key;
                tmp=tmp->next_node[0];
            }
            std::cout<<"insert successful"<<std::endl;
        }
    #endif  
    };
}