Redis源码分析（adlist）

时间：2024-09-09 17:03:44

源码版本：redis-4.0.1
源码位置：

  • adlist.h : listNode、list数据结构定义。
  • adlist.c：函数功能实现。

一、adlist简介

Redis中的链表叫adlist（A generic doubly linked list implementation 一个通用的双端链表实现）,和普通单链表相比，它的方向可以向前或者向后，这是由于数据结构中定义了next和prev两个指针决定的，下面看下它的数据结构实现。

二、数据结构定义

typedef struct listNode {

    struct listNode *next;         //next指针，指向下一个元素

    struct listNode *prev;         //prev指针，指向上一个元素

    void *value;                   //void *类型的数据域

} listNode;

typedef struct list {

    struct listNode *head;               //head指针指向链表头部

    struct listNode *tail;               //tail指针指向链表尾部

    void *(*dup)(void *ptr);             //自定义的复制函数，如果不定义，默认策略的复制操作会让原链表和新链表共享同一个数据域

    void (*free)(void *ptr);             //自定义free操作

    int (*match)(void *ptr, void *key);  //search操作的时候比较两个value是否相等，默认策略是比较两个指针的值

    unsigned long len;                   //记录链表的长度，获取长度操作可以O(1)返回

} list;

三、创建、头插、查找、反转输出、复制、拼接

老规矩，我们还是以一个例子来分析源码，这个例子中会设计到adlist的创建、头插、查找、反转输出、复制、拼接这些操作，例子的代码如下所示：

int keyMatch(void *ptr, void *key) {

    return strcmp(ptr, key) == 0 ? 1 : 0;

}

void printList(list *li) {

    printf("li size is %d, elements:", listLength(li));

    listIter iter;

    listNode *node;

    listRewind(li, &iter);

    while ((node = listNext(&iter)) != NULL) {

        printf("%s ", (char*)node->value);

    }

    printf("\n");

}

int main(int argc, char **argv)

{

    char b[][10] = {"believe", "it", "or", "not"};

    listIter iter;

    listNode *node;

    list *li = listCreate();

    for (int i = 0; i < sizeof(b)/sizeof(*b); ++i) {

        listAddNodeHead(li, b[i]);

    }

    printList(li);

    printf("\nSearch a key :\n");

    listSetMatchMethod(li, keyMatch);

    listNode *ln = listSearchKey(li, "believe");

    if (ln != NULL) {

        printf("find key is :%s\n", (char*)ln->value);

    } else {

        printf("not found\n");

    }

    printf("\nReverse output the list :\n");

    printf("li size is %d, elements:", listLength(li));

    listRewindTail(li, &iter);

    while ((node = listNext(&iter)) != NULL) {

        printf("%s ", (char*)node->value);

    }

    printf("\n");

    printf("\nduplicate a new list :\n");

    list *lidup = listDup(li);

    printList(lidup);

    printf("\nConnect two linked lists :\n");

    listJoin(li, lidup);

    printList(li);

    listRelease(li);

    return 0;

}

Out >

li size is 4, elements:not or it believe 

Search a key :

find key is :believe

Reverse output the list :

li size is 4, elements:believe it or not 

duplicate a new list :

li size is 4, elements:not or it believe 

Connect two linked lists :

li size is 8, elements:not or it believe not or it believe
  • 创建

list *li = listCreate(); 创建了一个list，并且返回了指针，代码如下所示：

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;

}
  • 头插

listAddNodeHead(li, b[i]);然后将预先定义好的数组元素依次头插入了list，与之对应的还有一个尾插的函数listAddNodeTail()，我们先看下头插listAddNodeHead()的代码：

list *listAddNodeTail(list *list, void *value)

{

    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)

        return NULL;

    node->value = value;

    if (list->len == 0) {

        list->head = list->tail = node;

        node->prev = node->next = NULL;

    } else {

        node->prev = list->tail;

        node->next = NULL;

        list->tail->next = node;

        list->tail = node;

    }

    list->len++;

    return list;

}

函数首先申请了一个listNode节点，然后用list->len == 0判断了是不是首节点，然后根据不同的策略交换指针，将元素头插入链表，将长度增加，循环插入所有元素之后链表目前情况如下图所示:

Redis源码分析（adlist）

  • 查找

listNode *ln = listSearchKey(li, "believe");可以查找第二个参数指定的字符串，默认的匹配原则是比较指针是否相等，但是可以自定义match函数，因为我们的例子中需要比较字符串，我自定义了keyMatch函数如下所示：

match函数的声明是：int (*match)(void *ptr, void *key); 

int keyMatch(void *ptr, void *key) {

    return strcmp(ptr, key) == 0 ? 1 : 0;

}

listSetMatchMethod(li, keyMatch);可以指定match函数，下面我们看下listSearchKey()函数的实现：

listNode *listSearchKey(list *list, void *key)

{

    listIter iter;

    listNode *node;

    listRewind(list, &iter);

    while((node = listNext(&iter)) != NULL) {

        if (list->match) {

            if (list->match(node->value, key)) {   //如果用户自定义了比较函数，就直接使用

                return node;

            }

        } else {

            if (key == node->value) {             //默认的比较策略是比较指针

                return node;

            }

        }

    }
  • 翻转

因为adlist是双端链表，所以翻转操作十分简单，我们直接将迭代器初始化成从链表尾部开始遍历就完成了翻转操作。

listRewindTail(li, &iter);    //将迭代器从尾部迭代
  • 复制

list *lidup = listDup(li);会创建一条新的链表返回给用户，但是需要注意默认的复制策略，如果用户不自定义dup()函数，默认返回的复制链表和原始链表共用相同的数据节点，这样对于一个节点修改会导致原始链表发生变化。如下所示：

list *lidup = listDup(li);                      //使用默认的复制操作

strncpy(listIndex(lidup, 0)->value, "abc", 3);  //修改复制返回的链表的值

printList(lidup);

printList(li);

Out >

li size is 4, elements:abc or it believe

li size is 4, elements:abc or it believe     //可以看到原始链表也受了影响，not 修改为了 abc

但是如果自定义dup函数，不再使得复制之后的链表和原始链表公用节点就可以避免这个问题:

void *strDup(void *ptr) {

    return sdsnew(ptr);

}

listSetDupMethod(li, strDup);                //设置自定义的dup函数

list *lidup = listDup(li);

strncpy(listIndex(lidup, 0)->value, "abc", 3);

printList(lidup);

printList(li);

Out >

li size is 4, elements:abc or it believe

li size is 4, elements:not or it believe    //还是原始的值没有变化
  • 拼接

listJoin(li, lidup);可以将两个链表做连接操作：

void listJoin(list *l, list *o) {

    if (o->head)

        o->head->prev = l->tail;      //将第二个链表链在第一个链表后边

    if (l->tail)

        l->tail->next = o->head;

    else

        l->head = o->head;

    l->tail = o->tail;

    l->len += o->len;

    /* Setup other as an empty list. */

    o->head = o->tail = NULL;

    o->len = 0;

}
  • 释放

listRelease(li);函数负责释放链表，首先会调用listEmpty()函数释放掉所有listNode,最后再释放掉list本身的空间。

四、总结

adlist的实现相对来说较简单，我们上面分析了它的创建、插入、查找、反转等操作，基本上熟悉了API和底层数据结构的原理，但是由于链表新增节点时候（无论头插尾插）每次都是申请新的空间，所以比较容易造成内存碎片。这方面想想有无办法优化。

[完]

相关文章