仿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;
}