C&C++   发布时间:2022-04-01  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了C++跳表项目源码分析大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。

什么是跳表skiplist

一种基于链表list改造的数据结构,以空间换时间的方式加速链表的搜索。
具体定义这里不赘述,具体可看传送门:漫画小灰之跳表

本文主要赏析github上一个跳表项目的实现
传送门:一个使用C++编程实现的基于跳表的轻量级键值型数据库

项目中跳表实现都在一个头文件skipList.h中,main.cpp为使用示例。

skiplist源码分析

节点类定义

节点为key-value型,由于跳表为多层结构,数组forWARD用于存放每层中该节点的下一节点

class Node {
public:
    Node() {} 
    Node(K k, V v, int); 
    ~Node();
    K get_key() const;
    V get_value() const;
    void set_value(V);
    // Linear array to hold pointers to next node of different level
    //存放不同层中下一个节点的指针的线性表
    Node<K, V> **forWARD;
    int node_level;
private:
    K key;
    V value;
};

节点构造函数
level为该节点在跳表中有多少层,创建节点时随机分配

template<typename K, typENAME v> 
Node<K, V>::Node(const K k, const V v, int level) {
    this->key = k;
    this->value = v;
    this->node_level = level; 

    // level + 1, because array index is from 0 - level
    this->forWARD = new Node<K, V>*[level+1];
    
	// Fill forWARD array with 0(NULL) 
    memset(this->forWARD, 0, sizeof(Node<K, V>*)*(level+1));
};

跳表类定义

我们主要看创建节点、插入节点、搜索元素、删除元素这几个方法的实现。

// Class template for Skip list
template <typename K, typENAME v> 
class SkipList {

public: 
    SkipList(int);
    ~SkipList();
    int get_random_level();
    Node<K, V>* create_node(K, V, int);
    int insert_element(K, V);
    void display_list();
    bool search_element(K);
    void delete_element(K);
    void dump_file();
    void load_file();
    int size();

private:
    void get_key_value_from_string(const std::string& str, std::string* key, std::string* value);
    bool is_valid_String(const std::string& str);

private:    
    // Maximum level of the skip list 
	//最大层数
    int _max_level;

    // current level of skip list 
	//当前层数
    int _skip_list_level;

    // pointer to header node 
	//头节点
    Node<K, V> *_header;

    // file operator
    std::ofstream _file_writer;
    std::ifstream _file_reader;

    // skiplist current element count
    int _element_count;
};

构造函数
头节点的level为跳表的最大层数
项目中的析构函数应该是有内存泄漏的问题的,只detele了头节点

// construct skip list
template<typename K, typENAME v> 
SkipList<K, V>::SkipList(int max_level) {

    this->_max_level = max_level;
    this->_skip_list_level = 0;
    this->_element_count = 0;

    // create header node and initialize key and value to null
    K k;
    V v;
    this->_header = new Node<K, V>(k, v, _max_level);
};

创建节点

直接new一个node,返回指针

// create new node 
template<typename K, typENAME v>
Node<K, V>* SkipList<K, V>::create_node(const K k, const V v, int level) {
    Node<K, V> *n = new Node<K, V>(k, v, level);
    return n;
}

插入节点

如在以下跳表中插入key为50的节点:
                           +------------+
                           |  insert 50 |
                           +------------+
level 4     +-->1+                                                      100
                 |
                 |                      insert +----+
level 3         1+-------->10+---------------> | 50 |          70       100
                                               |    |
                                               |    |
level 2         1          10         30       | 50 |          70       100
                                               |    |
                                               |    |
level 1         1    4     10         30       | 50 |          70       100
                                               |    |
                                               |    |
level 0         1    4   9 10         30   40  | 50 |  60      70       100

需要在每层中找到插入的位置,即每层插入位置的上一个节点,该节点的key小于插入节点,下一节点的key大于插入节点。这里定义了一个数组update存放插入位置的上一个节点。

template<typename K, typENAME v>
int SkipList<K, V>::insert_element(const K key, const V value) {
    
    mtx.lock();
    Node<K, V> *current = this->_header;

    // create update array and initialize it 
    // update is array which put node that the node->forWARD[i] should be operated later
    //update[i]是第i层中key最后一个比插入key小的node*
    Node<K, V> *update[_max_level+1];
    memset(update, 0, sizeof(Node<K, V>*)*(_max_level+1));  

    // start form highest level of skip list 
    //从最高层搜索填补update
    for(int i = _skip_list_level; i >= 0; i--) {
        while(current->forWARD[i] != NULL && current->forWARD[i]->get_key() < key) {
            current = current->forWARD[i]; 
        }
        update[i] = current;
    }

    //在上图示例中,如插入key 50, 在每层中,得到它的上一节点的key依次为40,30,30,10,1

    // reached level 0 and forWARD pointer to right node, which is desired to insert key.
    //第0层, current->forWARD[0]为应该插入的位置
    current = current->forWARD[0];

    // if current node have key equal to searched key, we get it
    //该key已存在,解锁后直接返回
    if (current != NULL && current->get_key() == key) {
        std::cout << "key: " << key << ", exists" << std::endl;
        mtx.unlock();
        return 1;
    }

    // if current is NULL that means we have reached to end of the level 
    //current为空,表示到达了该层的末尾
    // if current's key is not equal to key that means we have to insert node between update[0] and current node 
    //不为空则要在update[0]和current之间插入
    if (current == NULL || current->get_key() != key ) {
        
        // Generate a random level for node
        //随机层数
        int random_level = get_random_level();

        // If random level is greater thar skip list's current level, initialize update value with pointer to header
        //随机层数比当前的层数高时,比当前层高的层前一节点就是_header
        if (random_level > _skip_list_level) {
            for (int i = _skip_list_level+1; i < random_level+1; i++) {
                update[i] = _header;
            }
            _skip_list_level = random_level;
        }

        // create new node with random level generated 
        //创建节点
        Node<K, V>* inserted_node = create_node(key, value, random_level);
        
        // insert node 
        // 插入节点
        //1、对每一层,插入节点的下一节点为update[i]的下一节点
        //2、update[i]的下一节点更新为插入节点
        for (int i = 0; i <= random_level; i++) {
            inserted_node->forWARD[i] = update[i]->forWARD[i];
            update[i]->forWARD[i] = inserted_node;
        }
        std::cout << "successfully inserted key:" << key << ", value:" << value << std::endl;
        _element_count ++;  //增加节点数
    }
    mtx.unlock();
    return 0;
}

搜索节点

                           +------------+
                           |  SELEct 60 |
                           +------------+
level 4     +-->1+                                                      100
                 |
                 |
level 3         1+-------->10+------------------>50+           70       100
                                                   |
                                                   |
level 2         1          10         30         50|           70       100
                                                   |
                                                   |
level 1         1    4     10         30         50|           70       100
                                                   |
                                                   |
level 0         1    4   9 10         30   40    50+-->60      70       100

从顶层的header开始,从上而下,从左到右,依次遍历每层的节点key,直到第0层。

template<typename K, typENAME v> 
bool SkipList<K, V>::search_element(K key) {

    std::cout << "search_element-----------------" << std::endl;
    Node<K, V> *current = _header;

    // start from highest level of skip list
    for (int i = _skip_list_level; i >= 0; i--) {
        while (current->forWARD[i] && current->forWARD[i]->get_key() < key) {
            current = current->forWARD[i];
        }
    }

    //reached level 0 and advance pointer to right node, which we search
    current = current->forWARD[0];

    // if current node have key equal to searched key, we get it
	//key存在则找到目标元素
    if (current and current->get_key() == key) {
        std::cout << "Found key: " << key << ", value: " << current->get_value() << std::endl;
        return true;
    }

    std::cout << "Not Found Key:" << key << std::endl;
    return false;
}

删除节点

同理,先找到每层中该节点位置的前一节点
若某层中该key存在,前一节点的下一节点指向该元素的下一节点。

// delete element from skip list 
template<typename K, typENAME v> 
void SkipList<K, V>::delete_element(K key) {

    mtx.lock();
    Node<K, V> *current = this->_header; 
    Node<K, V> *update[_max_level+1];
    memset(update, 0, sizeof(Node<K, V>*)*(_max_level+1));

    // start from highest level of skip list
    for (int i = _skip_list_level; i >= 0; i--) {
        while (current->forWARD[i] !=NULL && current->forWARD[i]->get_key() < key) {
            current = current->forWARD[i];
        }
        update[i] = current;
    }

    current = current->forWARD[0];
    //找到该节点
    if (current != NULL && current->get_key() == key) {
       
        // start for loWest level and delete the current node of each level
        for (int i = 0; i <= _skip_list_level; i++) {

            // if at level i, next node is not target node, break the loop.
            //如果该层没有该节点,跳过
            if (update[i]->forWARD[i] != current) 
                break;

            update[i]->forWARD[i] = current->forWARD[i];
        }

        // Remove levels which have no elements
        //如果删除节点后该层没有元素,则调整当前的层数
        while (_skip_list_level > 0 && _header->forWARD[_skip_list_level] == 0) {
            _skip_list_level --; 
        }

        std::cout << "successfully deleted key "<< key << std::endl;
        _element_count --;
		delete current;  //这句我自己加的,源码中没有,难道节点只new不delete吗?
    }
    mtx.unlock();
    return;
}

大佬总结

以上是大佬教程为你收集整理的C++跳表项目源码分析全部内容,希望文章能够帮你解决C++跳表项目源码分析所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。
标签: