nanxing_stl/lib/others/skiplist.h

//stl之外的东西

#ifndef _SKIPLISTS_H_
#define _SKIPLISTS_H_
#include<ostream>
#include<cstdlib>
#include<type_traits>
#include<shared_mutex>
#include<mutex>
#include<cstring>
#include<random>
#include<chrono>
#include<optional>
#include"../nanxing_memory.h"

namespace nanxing
{
    template<typename K,typename V=int>           
    struct SkiplistNode
    {

    
    private:
        K key;            
        V Value;

    public:
     using deep_point=SkiplistNode**;
        explicit SkiplistNode(){}
        SkiplistNode(K _k,V _v,int _deep):key(_k),Value(_v),deep_level(_deep)      //这里有个问题，即V只能是一个可复制或者可移动的类型
        {
            forward=  new SkiplistNode*[deep_level+1];   //构造一个存储对应的数据的指针（分配空间就好了没必要调用构造函数）
            std::memset(forward,0,sizeof(SkiplistNode*)*(deep_level+1));      //全部初始化为0
        }
        ~SkiplistNode()
        {
   
            delete[] forward;     
        }

        [[nodiscard]]
        V get_value()const{return Value;};

        [[nodiscard]]       //没事不要乱取值，否则会影响性能，返回值不用取来干嘛
        K get_key()const{return key;}

        void set_value(V _v){Value=_v;}

        [[nodiscard]]
        V reset_value(V _v){Value=_v;}
        
        deep_point forward;                //指向下一层数据的指针数组的指针
        int deep_level;

    };

    template<typename K,typename V,typename alloc=nanxing::allocator<SkiplistNode<K,V>>>      //使用自定义构造器
    class Skiplists
    {
    public:
    using Node=SkiplistNode<K,V>;
        Skiplists(int _max_level):Creater(),max_level(_max_level){ 
            current_level=0;
            Node_count=0;
            K key;
            V value;
            head=(this->Creater.allocate(sizeof(SkiplistNode<K,V>)));
            Creater.construct(head,key,value,_max_level);

            for(int i=0;i<10000;i++)
            {
                random_map[i]=get_random();
            }
        }

        [[nodiscard]]
        SkiplistNode<K,V>* creat_node(K key,V value,int level)             //如果返回值被忽略会发生内存泄露
        {
            SkiplistNode<K,V>* tmp=static_cast<SkiplistNode<K,V>*>(Creater.allocate(sizeof(SkiplistNode<K,V>(key,value,level)))) ;          
            Creater.construct(tmp,key,value,level);                                   //进行内存分配
            return tmp;
        }

        int List_size(){return {Node_count};}

        [[nodiscard]]
        int insert_Node(K key,V value)             //插入节点
        {
        #ifdef _THREAD_                             //考虑到很多时候是用单线程异步所以用锁反而会拖累速度，所以条件编译单线程不加锁
            std::unique_lock<std::shared_mutex>lk{RWmutex};                        //这里用的是写锁
        #endif
            Node* tmp=this->head;
            Node* updata[max_level]={0};                     //用于记录每一层的路径（首先初始化为全nullptr）
            
            for(int i= current_level;i>=0;i--)                          //从最顶层开始向下查找                    
            {
                while(tmp->forward[i]!=nullptr&&tmp->forward[i]->get_key()<key)        //寻找插入点（这里的i代表在同一层）
                {                                                                       //head节点是一个没有值的全空节点，用于标识头部，因此插入的所有节点都在head之后
                                                                                        //因此查找的起始点是head->forward
                    tmp=tmp->forward[i];                                     //这里需要参考skiplist的论文
                                                                            //这里递归向下的愿意是一个在i层出现的节点一定会出现在n层(n<i)
                                                                            //即只需要从这个节点开始先后查找即可
                }
                updata[i]=tmp;             //用于记录每一层插入的位置
            }

            tmp=tmp->forward[0];          //查看最底层
            if(tmp!=nullptr&&tmp->get_key()==key)
            {

                return 2;                  //代表点已经存在
            }
            else      //{tmp==nullptr|| tmp->get_key()!=key}
            {
                int _node_level=random_map[random_point%10000];     //打表，但是最离谱的是rand()比这边打表还快

                random_point++;      //这个如果没有就退化为单链表


                

                if(_node_level>current_level)
                {
                    for(int i=_node_level+1;i>=current_level+1;i--)
                    {
                        updata[i]=head;
                    }
                    current_level=_node_level;
                }

                Node* _insert=creat_node(key,value,_node_level);

                for(int i=0;i<=_node_level;i++)
                {
                    _insert->forward[i]=updata[i]->forward[i];
                    updata[i]->forward[i]=_insert;
                }
                Node_count++;

                return 1;                     //插入成功
            }
            
        
            return -1;                      //插入失败
        }

        int insert_Node(SkiplistNode<K,V>* _insert)
        {
        #ifdef _THREAD_                             //考虑到很多时候是用单线程异步所以用锁反而会拖累速度，所以条件编译单线程不加锁
            RWmutex.lock();                        //这里用的是写锁
        #endif
            K key=_insert->get_key();
            Node* tmp=this->head;
            Node* updata[max_level]={0};                     //用于记录每一层的路径（首先初始化为全nullptr）
            
            for(int i= current_level;i>=0;i--)                          //从最顶层开始向下查找                    
            {
                while(tmp->forward[i]!=nullptr&&tmp->forward[i]->get_key()<key)        //寻找插入点（这里的i代表在同一层）
                {
                    tmp=tmp->forward[i];                                     //这里需要参考skiplist的论文
                }
                updata[i]=tmp;             //用于记录每一层插入的位置
            }

            tmp=tmp->forward[0];          //查看最底层
            if(tmp!=nullptr&&tmp->get_key()==key)             //这里做一个截断判定，如果是空指针不会判定第二个条件
            {
        #ifdef _THREAD_
            RWmutex.unlock();
        #endif
                return 2;                  //代表点已经存在
            }
            else      //{tmp==nullptr|| tmp->get_key()!=key}
            {
                int _node_level=_insert->deep_level;

                if(_node_level>current_level)
                {
                    for(int i=_node_level+1;i>current_level+1;i--)
                    {
                        updata[i]=head;
                    }
                }

                for(int i=0;i<=_node_level;i++)
                {
                    _insert->forward[i]=updata[i]->forward[i];
                    updata[i]->forward[i]=_insert;
                }
                Node_count++;
        #ifdef _THREAD_
            RWmutex.unlock();
        #endif
                return 1;                     //插入成功
            }
        #ifdef _THREAD_
            RWmutex.unlock();
        #endif
            return -1;                      //插入失败

        #ifdef _THREAD_
            RWmutex.unlock();
        #endif
        }

        bool search_Node(K key)                   //查找值是否存在
        {
        #ifdef _THREAD_                             //考虑到很多时候是用单线程异步所以用锁反而会拖累速度，所以条件编译单线程不加锁
            RWmutex.lock_shared();                        //这里用的是读锁
        #endif
            using Node=SkiplistNode<K,V>;
            Node* tmp=head;
            for(int i=current_level;i>=0;i--)             //逐层查找
            {
                while(tmp->forward[i]!=nullptr&&tmp->forward[i]->get_key()<key)
                {
                    tmp=tmp->forward[i];
                }
            }
            tmp=tmp->forward[0];
            if(tmp!=nullptr&&tmp->get_key()==key)
            {
                return true;
            }
            else
            {
                return false;
            }

        #ifdef _THREAD_                             //考虑到很多时候是用单线程异步所以用锁反而会拖累速度，所以条件编译单线程不加锁
            RWmutex.unlock_shared();                        //这里用的是读锁
        #endif
        }

        std::optional<V> get_value_from_key(K key)       //通过键返回值
        {
        #ifdef _THREAD_                             //考虑到很多时候是用单线程异步所以用锁反而会拖累速度，所以条件编译单线程不加锁
            RWmutex.lock_shared();                        //这里用的是读锁
        #endif
            using Node=SkiplistNode<K,V>;
            std::optional<V> opt;
            Node* tmp=head;
            for(int i=current_level;i>=0;i--)             //逐层查找
            {
                while(tmp->forward[i]!=nullptr&&tmp->forward[i]->get_key()<key)
                {
                    tmp=tmp->forward[i];
                }
            }
            tmp=tmp->forward[0];
            if(tmp!=nullptr&&tmp->get_key()==key)
            {
                opt=tmp->get_value();
            }
            else
            {
                opt = std::nullopt; 
            }
            return opt; 
        #ifdef _THREAD_                             //考虑到很多时候是用单线程异步所以用锁反而会拖累速度，所以条件编译单线程不加锁
            RWmutex.unlock_shared();                        //这里用的是读（共享）锁
        #endif
        }

        int delete_Node(K key)
        {
        #ifdef _THREAD_                             //考虑到很多时候是用单线程异步所以用锁反而会拖累速度，所以条件编译单线程不加锁
            RWmutex.lock();                        //这里用的是写锁
        #endif

            using Node=SkiplistNode<K,V>;
            Node* updata[current_level]={nullptr};           //由于是删除，用current_level就好了
            
            Node* tmp=head;
            for(int i=current_level;i>=0;i++)
            {
                while(tmp->forward[i]!=nullptr&&tmp->forward[i]->get_key()<key)
                {
                    tmp=tmp->forward[i];
                }
                updata[i]=tmp;
            }

            tmp=tmp->forward[0];
            if(tmp!=nullptr&&tmp->get_key()==key)            //判断第一层的这个点是否为需要删除的点
            {
                Node* deletes=tmp;
                for(int i=0;i<current_level;i++)                   //从下往上修改对应的指针
                {
                    if(updata[i]->forward[i]!=key)                 //到某一层这个指针指向的不是需要删除的节点的时候停止（跳表中任意的节点只会出现在第0-k层）
                    {
                        break;
                    }
                    updata->forward[i]=tmp->forward[i];
                }
                Creater.destory(deletes);                   //调用析构函数
                Creater.deallocate(deletes);                //释放空间

                return 1;                                 //删除成功
            }
            else
            {
                return 0;                                 //没有需要删除的节点
            }
            return -1;                                     //删除失败
   
        #ifdef _THREAD_
            RWmutex.unlock();
        #endif
        }

        void Print_basic()
        {
            using Node=SkiplistNode<K,V>;
            Node* tmp=head;
            if(tmp->forward[0]!=nullptr)
            {
                tmp =tmp ->forward[0];
                std::cout<<"("<<tmp->get_key()<<","<<tmp->get_value()<<")";
            }
            while(tmp->forward[0]!=nullptr)
            {
                tmp=tmp->forward[0];
                std::cout<<"->"<<"("<<tmp->get_key()<<","<<tmp->get_value()<<")";
                
            }
            std::cout<<std::endl;

        }
private:
        int get_random()                           //生成随机数，用于创建对应的数据的层数
        {
            // 通过<chrono>库获取当前的高精度时间点  
            auto now = std::chrono::system_clock::now();  
            // 将时间点转换为自纪元（通常是1970年1月1日）以来的纳秒数  
            auto duration_since_epoch = now.time_since_epoch();  
            // 将纳秒数转换为无符号长整型，用作随机数生成的种子  
            unsigned long seed = std::chrono::duration_cast<std::chrono::nanoseconds>(duration_since_epoch).count();  
        
            // 创建一个随机数引擎，这里使用的是Mersenne Twister引擎  
            std::mt19937 rng(seed);  
        
            // 定义一个均匀分布的整数范围
            std::uniform_int_distribution<int> dist(0, max_level);  
        
            //生成一个随机数  
            return dist(rng); 
            //return (rand()%max_level);
             
        }
    private:
        int max_level;

        int current_level;                        //当前的深度

    #ifdef _THREAD_                               //不是多线程没有必要 
        std::shared_mutex RWmutex;                      //读写锁
    #endif
        alloc Creater;                                 //构造器实例

        SkiplistNode<K,V>* head;                               //跳表的起点

        int Node_count;                                   //总结点数  

        int random_map[10000]={0};                       //随机数表

        int random_point=0;                              //指示当前访问的随机数的位置
    };
}

#endif