#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
//当不启用随机数表，使用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]]
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;
}
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;
}
#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
};
}