首頁  >  文章  >  資料庫  >  Redis中的雙端鍊錶實現

Redis中的雙端鍊錶實現

尚
轉載
2020-04-03 09:40:232163瀏覽

Redis中的雙端鍊錶實現

adlist作為Redis中的雙端鍊錶,在Redis中被廣泛的應用到了很多地方,比如slowlog的存儲,主從複製中報錯客戶端,list數據結構的實現等等,很多都與此相關,所以也是非常重要的一個資料結構。

一)、Redis中雙端鍊錶的資料結構

(建議:redis影片教學

雙端鍊錶(以下程式碼定義在src/adlist.h):

typedef struct list {
    listNode *head;    //指向链表的第一个节点
    listNode *tail;    //指向链表的最后一个节点
    //复制链表节点时候的回调函数,由于链表节点可以任意类型的数据,不同类型操作不同,故而用回调函数去特殊处理
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);     //释放链表节点内存时候的回调函数,理由同上
    int (*match)(void *ptr, void *key);    //比较链表节点值的回调函数,用于自定义比较,理由同上
    unsigned long len;  //当前列表节点数量
} list;

雙端鍊錶的節點(以下程式碼定義在src/adlist.h):

typedef struct listNode {
    struct listNode *prev;   //当前节点的上一个节点
    struct listNode *next;   //当前节点的下一个节点
    void *value;     //当前节点存储的值,可以任意类型
} listNode;

Redis中的雙端鍊錶實現

list 透過head和tail兩個指標分別指向鍊錶的頭尾兩端,使得遍歷鍊錶可以從正反兩個順序進行遍歷,而listNode 的void *value,則可以保存任意數據,並可以通過dup,free,match來自定義如何處理listNode的值。

二、雙端鍊錶的簡單操作

建立鍊錶(以下程式碼定義在src/adlist.c):

list *listCreate(void)
{
    struct list *list;    //初始化链表
    
    //为链表分配内存
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    //为空链表设置初始值
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

追加到鍊錶結尾(以下程式碼定義在src/adlist.c):

list *listAddNodeTail(list *list, void *value)
{
    listNode *node;    //初始化node节点

    //为新的node节点分配内存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //为node节点设置值
    node->value = value;
    
    if (list->len == 0) {
        //如果空链表则 将头尾指向 新节点 并后继前驱节点设置为NULL
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //否则将节点的前驱节点设置为原来的尾部节点
        node->prev = list->tail;
        //由于追加到尾部,后继节点为NULL
        node->next = NULL;
        //之前的尾部节点的后继节点设置为新增的节点
        list->tail->next = node;
        //将列表的尾部节点指针指向新增的节点
        list->tail = node;
    }
    //增加链表长度
    list->len++;
    return list;
}

遍歷鍊錶:

常用的遍歷鍊錶有兩種方式,一個是根據鍊錶長度透過while循環去手動遍歷,還有一種是用Redis雙端鍊錶提供的迭代器來遍歷。

手動遍歷(以下程式碼定義在 src/adlist.c 中的 記憶體釋放函數):

void listRelease(list *list)
{
    unsigned long len;
    //current表示当前遍历的游标指针,next表示下次遍历的游标指针(next作为临时变量用于保存下一个节点)
    listNode *current, *next;
    //将current指向头部节点
    current = list->head;
    //计算长度(其实就是 listLength(list))
    len = list->len;
    //通过长度递减的方式进行遍历,便利到长度为0的时候,遍历结束
    while(len--) {
        //保存下次循环的节点指针
        next = current->next;
        //释放掉当前节点,如果设置释放节点的回调函数,则执行用户自定义的函数
        if (list->free) list->free(current->value);
        zfree(current);
        //将游标指向下个节点
        current = next;
    }
    zfree(list);
}

迭代器方式遍歷請見下文。

三)、雙端鍊錶的迭代器

Redis 為了方便對鍊錶的迭代,對鍊錶進行了迭代器的封裝,迭代器結構如下(以下程式碼定義在src/adlist .h):

typedef struct listIter {
    listNode *next;    //迭代器指向的下一个节点
    //迭代方向,由于双端链表保存了head和tail的值,所以可以进行两个方向的迭代
    //AL_START_HEAD表示从头向后遍历,AL_START_TAIL表示从尾部向前遍历
    int direction;
} listIter;

 迭代器使用實例:

//l表示list结构,n表示listNode结构,listNode的值保存的是sds字符串
//创建迭代器对象
iter = listGetIterator(l, AL_START_HEAD);
//循环获取下一个需要遍历的节点
while ((n = listNext(iter))) {
    //输出返回的节点n的value值
    printf("Node Value: %s\n", listNodeValue(n));
}

更多redis知識請關注redis入門教學欄位。

以上是Redis中的雙端鍊錶實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:oschina.net。如有侵權,請聯絡admin@php.cn刪除