redis 5.0.7 源码阅读——双向链表

redis中动态字符串sds相关的文件为:adlist.h与adlist.c

一、数据结构

redis里定义的双向链表,与普通双向链表大致相同

单个节点:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

链表:

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;

链表以函数指针的方式,实现了复制、销毁与比较的方法的多态。

迭代器:

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

迭代器中有个成员变量direction,用于表示当前遍历的方向。

大致结构:

/*
+-------------------+        +----------------> +--------------+ <-------+
|listNode *head     |--------+                  |listNode *prev|-->NULL  |
+-------------------+                           +--------------+         |
|listNode *tail     |--------+                  |listNode *next|----+    |
+-------------------+        |                  +--------------+    |    |
|void *(*dup)(...)  |        |                  |void *value   |    |    |
+-------------------+        |                  +--------------+    |    |
|void (*free)(...)  |        |                                      |    |
+-------------------+        |                                      |    |
|int (*match)(...)  |        |                                      |    |
+-------------------+        +----------------> +--------------+ <--+    |
|unsigned long len  |                           |listNode *prev|---------+
+-------------------+                           +--------------+
                                                |listNode *next|-->NULL
                                                +--------------+
                                                |void *value   |
                                                +--------------+    
*/

二、创建

redis中创建一个初始双向链表比较简单,只要分配好内存,并给成员变量赋初值就可以了

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

redis中提供了头插法、尾插法以及指定位置插入节点三种方式向链表中添加节点,与普通双向链表无异,此处不做详细叙述。

三、销毁

因链表中每个节点的value可能指向堆空间,故不能直接把list结构体free,这样会造成内存泄露。需要先将每个节点的value释放,才可以free结构体

清空所有节点:

void listEmpty(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        //若指定了销毁的函数,则使用指定的函数进行销毁value
        if (list->free) list->free(current->value);
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
}

销毁链表:

void listRelease(list *list)
{
    listEmpty(list);
    zfree(list);
}

同样,redis的链表提供了与普通链表相同的删除单个节点的操作,此处也不做叙述。

四、迭代器操作

redis中提供了获取迭代器的接口

listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

以AL_START_HEAD为例,生成好的迭代器结构如下:

/*
+-------------------+    +---> +--------------+ <-------+----+
|listNode *head     |----+     |listNode *prev|-->NULL  |    |  
+-------------------+          +--------------+         |    |  +--------------+
|listNode *tail     |----+     |listNode *next|----+    |    +--|listNode *next|
+-------------------+    |     +--------------+    |    |       +--------------+
|void *(*dup)(...)  |    |     |void *value   |    |    |       |int direction |
+-------------------+    |     +--------------+    |    |       +--------------+
|void (*free)(...)  |    |                         |    |
+-------------------+    |                         |    |
|int (*match)(...)  |    |                         |    |
+-------------------+    +---> +--------------+ <--+    |
|unsigned long len  |          |listNode *prev|---------+
+-------------------+          +--------------+
                               |listNode *next|-->NULL
                               +--------------+
                               |void *value   |
                               +--------------+    
*/

迭代器的next方法:

listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next;
        else
            iter->next = current->prev;
    }
    return current;
}

调用一次之后的结构:

/*
+-------------------+    +---> +--------------+ <-------+
|listNode *head     |----+     |listNode *prev|-->NULL  |      
+-------------------+          +--------------+         |       +--------------+
|listNode *tail     |----+     |listNode *next|----+    |    +--|listNode *next|
+-------------------+    |     +--------------+    |    |    |  +--------------+
|void *(*dup)(...)  |    |     |void *value   |    |    |    |  |int direction |
+-------------------+    |     +--------------+    |    |    |  +--------------+
|void (*free)(...)  |    |                         |    |    |
+-------------------+    |                         |    |    |
|int (*match)(...)  |    |                         |    |    |
+-------------------+    +---> +--------------+ <--+----|----+    
|unsigned long len  |          |listNode *prev|---------+
+-------------------+          +--------------+
                               |listNode *next|-->NULL
                               +--------------+
                               |void *value   |
                               +--------------+    
*/

再次调用:

/*
+-------------------+    +---> +--------------+ <-------+
|listNode *head     |----+     |listNode *prev|-->NULL  |      
+-------------------+          +--------------+         |       +--------------+
|listNode *tail     |----+     |listNode *next|----+    |    +--|listNode *next|
+-------------------+    |     +--------------+    |    |    |  +--------------+
|void *(*dup)(...)  |    |     |void *value   |    |    |    |  |int direction |
+-------------------+    |     +--------------+    |    |    |  +--------------+
|void (*free)(...)  |    |                         |    |    |
+-------------------+    |                         |    |    |
|int (*match)(...)  |    |                         |    |    |
+-------------------+    +---> +--------------+ <--+    |    +-->NULL    
|unsigned long len  |          |listNode *prev|---------+
+-------------------+          +--------------+
                               |listNode *next|-->NULL
                               +--------------+
                               |void *value   |
                               +--------------+    
*/

调用next函数的返回值为调用之前的listNode首地址

五、其它操作

redis的双向链表还提供了其它操作。其中,查找指定的key与复制整个list依赖于迭代器的使用,并使用到自定义的比较/复制方法。

除此之外,还提供了类似随机读取的方式,其内部实现为遍历,且“越界”时返回NULL。同时,它支持index为负数,表示从尾开始。类似旋转的操作,把尾节点移至原头节点之前,成为新的头节点。当然,还有拼接两个链表的操作。

redis 5.0.7 下载链接

http://download.redis.io/releases/redis-5.0.7.tar.gz

源码阅读顺序参考:

https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst

相关推荐