跳跃表C++实现
仿Redis实现
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
#pragma once
#include "gntype.h"
#include <vector>
#include "utility.h"
static const uint32 MAX_LEVEL = 64;
static const double SKIPLIST_P = 0.25;
struct SkipListNode;
struct SkipListLevel
{
SkipListLevel(uint32 span, SkipListNode *forward) :nSpan(span), forwardNode(forward) {};
SkipListNode *forwardNode = nullptr;
uint32 nSpan = 0;
};
struct SkipListNode
{
uint64 nScore = 0;
uint64 nNodeId = 0;
SkipListNode *backwardNode = nullptr;
std::vector<SkipListLevel> level;
};
class SkipList
{
public:
SkipList();
~SkipList();
void InitSkipList();
bool IsExist(const uint64 key);
bool IsExist(const uint64& key, const uint64& value);
bool SearchNode(const uint64& key, std::vector<uint64>& vecRes);
bool DeleteNodeByKey(const uint64& key,const uint64 value);
void InsertNode(const uint64& key, const uint64& value);
SkipListNode* CreateNode(const uint32 level, const uint64& key, const uint64& value);
bool UpdateNode(const uint64& nNewkey, const uint64& nOldkey, const uint64& value);
void GetTopK(const uint32 nCount, std::vector<uint64>& vecRes);
uint32 GetRankByKey(const uint64& key, const uint64& value);
uint32 GetRandomLevel();
void Free();
private:
SkipListNode *headNode, *tailNode;
uint32 m_nLength;
uint32 m_nLevel;
void DeleteNode(SkipListNode * node, SkipListNode **update);
};
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227
#include "skip_list.h"
SkipList::SkipList()
{
}
SkipList::~SkipList()
{
}
SkipListNode* SkipList::CreateNode(const uint32 level, const uint64& key, const uint64& value)
{
SkipListNode* newNode = new SkipListNode;//factory
newNode->nScore = key;
newNode->nNodeId = value;
for (uint32 index = 0; index != level; ++index)
{
SkipListLevel newLevel(0, nullptr);
newNode->level.push_back(newLevel);
}
newNode->backwardNode = nullptr;
return newNode;
}
void SkipList::InitSkipList()
{
m_nLevel = 1;
m_nLength = 0;
headNode = CreateNode(MAX_LEVEL, 0, 0);
tailNode = nullptr;
}
void SkipList::InsertNode(const uint64& key, const uint64& value)
{
SkipListNode *update[MAX_LEVEL], *x;
unsigned int rank[MAX_LEVEL];
uint32 i, level;
x = headNode;
for (i = (m_nLevel - 1); i >= 0; i--) {
/* store rank that is crossed to reach the insert position */
rank[i] = (i == (m_nLevel - 1)) ? 0 : rank[i + 1];
while ((x->level.size() - 1) < i && x->level[i].forwardNode &&
(x->level[i].forwardNode->nScore < key ||
(x->level[i].forwardNode->nScore == key &&
x->level[i].forwardNode->nNodeId < value)))
{
rank[i] += x->level[i].nSpan;
x = x->level[i].forwardNode;
}
update[i] = x;
}
level = GetRandomLevel();
if (level > m_nLevel) {
for (i = m_nLevel; i < level; i++) {
rank[i] = 0;
update[i] = headNode;
update[i]->level[i].nSpan = m_nLength;
}
m_nLevel = level;
}
x = CreateNode(level, key, value);
for (i = 0; i < level; i++) {
x->level[i].forwardNode = update[i]->level[i].forwardNode;
update[i]->level[i].forwardNode = x;
x->level[i].nSpan = update[i]->level[i].nSpan - (rank[0] - rank[i]);
update[i]->level[i].nSpan = (rank[0] - rank[i]) + 1;
}
for (i = level; i < m_nLevel; i++) {
update[i]->level[i].nSpan++;
}
x->backwardNode = (update[0] == headNode) ? nullptr : update[0];
if (x->level[0].forwardNode)
x->level[0].forwardNode->backwardNode = x;
else
tailNode = x;
m_nLength++;
}
bool SkipList::IsExist(const uint64 key)
{
return true;
}
bool SkipList::IsExist(const uint64& key, const uint64& value)
{
return true;
}
bool SkipList::SearchNode(const uint64& key, std::vector<uint64>& vecRes)
{
return true;
}
bool SkipList::DeleteNodeByKey(const uint64& key, const uint64 value)
{
SkipListNode *update[MAX_LEVEL], *x;
int i;
x = headNode;
for (i = m_nLevel - 1; i >= 0; i--) {
while ((x->level.size() - 1) < i && x->level[i].forwardNode &&
(x->level[i].forwardNode->nScore < key ||
(x->level[i].forwardNode->nScore == key &&
x->level[i].forwardNode->nNodeId < value)))
{
x = x->level[i].forwardNode;
}
update[i] = x;
}
x = x->level[0].forwardNode;
if (x && key == x->nScore && value == x->nNodeId) {
DeleteNode(x, update);
delete x; //factory
return true;
}
return false;
}
bool SkipList::UpdateNode(const uint64& nNewkey, const uint64& nOldkey, const uint64& value)
{
SkipListNode *update[MAX_LEVEL], *x;
int i;
x = headNode;
for (i = m_nLevel - 1; i >= 0; i--) {
while ((x->level.size() - 1) < i && x->level[i].forwardNode &&
(x->level[i].forwardNode->nScore < nOldkey ||
(x->level[i].forwardNode->nScore == nOldkey &&
x->level[i].forwardNode->nNodeId < value)))
{
x = x->level[i].forwardNode;
}
update[i] = x;
}
x = x->level[0].forwardNode;
bool bExist = x && nOldkey == x->nScore && value == x->nNodeId;
if (bExist = false)
{
return false;
}
if ((x->backwardNode == nullptr || x->backwardNode->nScore < nNewkey) &&
(x->level[0].forwardNode == nullptr || x->level[0].forwardNode->nScore > nNewkey))
{
x->nScore = nNewkey;
return true;
}
DeleteNode(x, update);
InsertNode(nNewkey, value);
delete x;//factory
return true;
}
void SkipList::GetTopK(const uint32 nCount, std::vector<uint64>& vecRes)
{
}
uint32 SkipList::GetRankByKey(const uint64& key, const uint64& value)
{
SkipListNode *x;
unsigned long rank = 0;
int i;
x = headNode;
for (i = m_nLevel - 1; i >= 0; i--) {
while ((x->level.size() - 1) < i && x->level[i].forwardNode &&
(x->level[i].forwardNode->nScore < key ||
(x->level[i].forwardNode->nScore == key &&
x->level[i].forwardNode->nNodeId < value)))
{
rank += x->level[i].nSpan;
x = x->level[i].forwardNode;
}
if (x && x->nNodeId == value) {
return rank;
}
}
return INT_MAX;
}
void SkipList::Free()
{
}
void SkipList::DeleteNode(SkipListNode * node, SkipListNode **update)
{
int i;
for (i = 0; i < m_nLevel; i++) {
if (update[i]->level[i].forwardNode == node) {
update[i]->level[i].nSpan += node->level[i].nSpan - 1;
update[i]->level[i].forwardNode = node->level[i].forwardNode;
}
else {
update[i]->level[i].nSpan -= 1;
}
}
if (node->level[0].forwardNode) {
node->level[0].forwardNode->backwardNode = node->backwardNode;
}
else {
tailNode = node->backwardNode;
}
while (m_nLevel > 1 && headNode->level[m_nLevel - 1].forwardNode == nullptr)
m_nLevel--;
m_nLength--;
}
uint32 SkipList::GetRandomLevel()
{
uint32 level = 1;
while ((Storm::GetRand(1, 0xFFFF) & 0xFFFF) < (SKIPLIST_P * 0xFFFF))
level += 1;
return (level < MAX_LEVEL) ? level : MAX_LEVEL;
}