简介

redis 源码版本：3.05.04

如有理解不对的地方，欢迎各位指出，大家共同交流和学习。

源码学习

结构定义

链表作为一种常用的数据结构，提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。
链表节点结构：

//双向链表
typedef struct listNode {  
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的具体值
    void *value;
} listNode;

示意图如下所示：
在这里插入图片描述

为什么listNode结构就可以组成一个双向链表，为什么还要有list结构那？

因为，新增的dup、free、match、len四个字段可以用来实现多态链表所需的数据类型，使用list结构来持有链表的话，操作起来更方便。
链表迭代器结构：

typedef struct listIter {
    listNode *next;
    int direction;//向前  next=list->tail  向后  next=list->head
} listIter;

链表结构：

typedef struct list {
    //头节点
    listNode *head;
    //尾节点
    listNode *tail;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void (*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *ptr, void *key);
    //节点的个数
    PORT_ULONG len;
} list;

示意图如下所示：
在这里插入图片描述
redis就是采用这种结构。

创建链表函数

/*
创建链表
 */
list *listCreate(void)
{
    struct list *list;  //list指的是结构体

    if ((list = zmalloc(sizeof(*list))) == NULL)//分配内存空间，返回null，分配失败直接返回
        return NULL;
    list->head = list->tail = NULL;   //此时没有任何节点，头节点为null
    list->len = 0;          
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

释放链表函数

在进行节点空间释放时，先将下一个节点的指针保存到next变量中，然后释放当前节点空间，然后，再将next变量中下一个节点的指针赋值给当前节点。

/* 
释放链表
*/
void listRelease(list *list)
{
    PORT_ULONG len;
    listNode *current, *next;

    current = list->head;   //起始时，指向这个链表的头
    len = list->len;
    while(len--) {
        next = current->next;//获取当前节点的下一个节点的指针
        if (list->free) list->free(current->value);   //释放内存
        zfree(current);   //释放当前节点空间
        current = next;   //下一个继续
    }
    zfree(list);   //最后释放list空间
}

新增节点到表头函数

/*
增加节点到表头
思路:分原链表为空和非空两种情况进行新增
*/
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;  //先创建一个node新增节点

    if ((node = zmalloc(sizeof(*node))) == NULL)//分配内存
        return NULL;
    node->value = value;   //将新增的值，赋值给node节点
    if (list->len == 0) {  //当链表中没有节点时
        list->head = list->tail = node;    //原链表的头节点和尾节点都指向这个节点
        node->prev = node->next = NULL;    //链表的前置节点和后置节点都为空，置为null
    } else {              //当链表中有节点时
        node->prev = NULL;         //链表的前置节点置为空
        node->next = list->head;   //链表的后置节点指向链表的头节点
        list->head->prev = node;   //原链表的头节点的前置节点指向新增的node节点
        list->head = node;         //改变原链表头节点指针，重新指向node节点
    }
    list->len++;     //链表的长度加1
    return list;    //返回当前链表
}

例：在由3-》4-》-》5组成的链表的表头中，新增一个值为7的节点
在这里插入图片描述

新增节点到表尾函数

/*
增加节点到表尾
与增加节点到表头相似
*/
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {		//当链表中没有节点时，与listAddNodeHead处理一样
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {   					//当链表中有节点时，
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;  //原来的尾节点的next指针指向node节点
        list->tail = node;        //改变原链表尾节点指针，重新指向node节点
    }
    list->len++;
    return list;
}