nanxing_stl/STL/extend/skiplist.h

#include"basical/type_checking.h"
#include<cstdlib>
#include<cstring> 
#include<exception>
#include<random>
#include<shared_mutex>
#include <variant>

namespace nanxing_extend
{
    //错误处理机制
    class nextpoint_new:std::exception             //skip_node分配空间失败的时候
    {
        const char* what() const noexcept
        {
            return "malloc next_node point fault";
        }
    };

    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
        fault,
        exit

    };

    //注意这里的V只能是要么是能直接深拷贝的类型，要么是指向堆上数据的指针类型
    template<typename K,typename V>
    struct skip_node
    {
        static_assert(nanxing_extend::compare_admit<K>value);
        static_assert(nanxing_extend::compare_admit<V>value);
        skip_node<K,V>** next_node; 
        V value;
    private:
        K key;
        int level;
    public:
        skip_node(){};
        skip_node(K _key,V _value,int _level):key(_key),value(_value),level(_level){};
        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; }
    };

    template<typename K,typename V>
    class skipList
    {
        static_assert(nanxing_extend::compare_admit<K>value);
        static_assert(nanxing_extend::compare_admit<V>value);
    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;
        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;
                middle->init_next(max_level);
                head=::new (Node*)[max_level];
                for(auto& i in head)                
                {
                    i=middle;
                }
            }
            catch(std::bad_alloc)
            {
                throw newNode_error();        //重新抛出更详细的错误类型
            }
        }
        #elif
        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

        [[nodiscard]]                            //这个返回值最好不要忽略否则很有可能会出现内存泄漏
        auto insert(K _key,V _value)->std::variant<Skip_result,V>              //如果相同的时候我们考虑将value返回因为value很可能会是一个指针，需要手动清空内存
        {
        #ifdef NANXING_THREAD_
            std::lock_guard<std::shared_mutex> lock(RW_lock);             
        #endif
        std::variant<Skip_result,V> sk;
        #ifdef SKIP_MAX_SIZE
            if(current_size==max_size)
            {
                return sk=Skip_result::full;
            }
        #endif
            int rand_level=0;
            ptr updata[max_level]={nullptr};          //用于更新的数组
            int level=current_level-1;
            ptr point=head[level];
            
            ptr new_node;
            for(int i=level;i>=0;i--)
            {
                for(;;)
                {
                    if(point->next_node[level]==nullptr)
                    {
                        updata[level]=point;
                        break;
                    }
                    else if(point->next_node[level]->key>=_key)
                    {
                        if(point->next_node[level]->key==_key)
                        {
                            sk=std::move(point->next_node[level]->value);          //这个值已经不需要了，直接移动
                            point->next_node[level]->value=_value;
                            return sk;
                        }
                        else
                        {
                            updata[level]=point;
                            break;
                        }
                        else{
                            point=point->head[level];              //更新point指针
                        }
                    }
                }
                [[likely]]
                if(random_level!=nullptr)
                {
                    rand_level=random_level[current_size%1024];
                    new_node=new skip_node(_key,_value,rand_level);
                }
                [[unlikely]]
                else
                {
                    rand_level=std::rand(chrono::system_clock::now().time_since_epoch().count())%(1+max_level);
                    new_node=new skip_node(_key,_value,rand_level);
                }
                ptr tmp=nullptr;
                
                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;
        }

        [[nodiscard]]                    
        auto search(K _key)->std::variant<Skip_result,V>  noexcept       //不涉及任何内存分配相关任务，因此是异常安全的
        {
        #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(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::fault;
        }
                
        void init_skip()                 //直接生成随机数表
        {
        #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();
            }
            std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
            for(auto& i :random_level)
            {
                i=(rnd()%max_level)+1;
            }

        }
    };

    #ifdef SKIP_MAX_SIZE
    [[nodicard]]
        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
}