链表是很常用的数据结构, 大多数高级语言都有内置的实现. 因为C并没有提供链表的实现, 所以Redis就自已实现了链表. 如果有上过数据结构与算法或者看过其他语言对链表的实现, 那么这一部份理解起来就超级easy. 可以参考 java 的 LinkedList 的实现.

redis 关于链表的实现主要在 adlist.h 和 adlist.c 两个文件

1 adlist.h 源码解析

1.1 链表结构体 list

//链表结构体
typedef struct list {
    //链表首节点
    listNode *head;
    //链表尾节点
    listNode *tail;
    //结构体的函数相当于多态, 由具体的对象提供对应的函数实现
    //链表复制指定节点的value的值, 值如果是结构体, 则需要对应的函数来拷贝
    void *(*dup)(void *ptr);
    //链表释放指定节点的value的内存的函数, 值如果是结构体, 则需要对应的函数释放内存
    void (*free)(void *ptr);
    //值的比较函数, 相当于 java 的equals, 用于比较结构体是否相等
    int (*match)(void *ptr, void *key);
    //链表长度
    unsigned long len;
} list;

• 链表结构体中主要有首节点指针 head , 尾节点指针 tail , 三个函数指针和链表长度 len , 首尾节点主要是为了方便向后和向前遍历, 链表长度主要是为了获取节点的数量的时间复杂度为O(1).
• 链表结构体中还有三个函数指针, 主要是用于对 listNode 中的 value 进行复制, 释放内存和比较是否相等. 这三个函数指针有点像多态, 根据value是不同的值, 从而使用不同实现的函数.
• 为什么节点需要三个函数指针呢 ? 当 value 指针是结构体时, 就不能直接判断, 复制和释放内存, 需要根据具体的结构体来做定制化.

1.2 链表节点的结构体 listNode

//链表节点的结构体
typedef struct listNode {
    //前一个节点的引用
    struct listNode *prev;
    //下一个节点的引用
    struct listNode *next;
    //当前节点的值, 相当于 Object 类型
    void *value;
} listNode;

• value是Void *指针, 相当于java的Object, 可以存任何类型的值或结构
• 链表节点通过prev指针指向上一个节点, 通过next指针指向下一个节点, 从而将所有节点连在一起, 如下图:

image.png

1.3 链表迭代器结构体 listIter

//链表迭代器
typedef struct listIter {
    //当前遍历节点
    listNode *next;
    //迭代方向, 可以向前或者向后
    int direction;
} listIter;

//前面开始遍历
#define AL_START_HEAD 0
//后面开始遍历
#define AL_START_TAIL 1

• next 可以理解为当前遍历的节点, 也可以理解为下一个节点, 因为调用 listNext() 方法就是获取next的值
• direction 表示迭代方向, 主要两个值, AL_START_HEAD 表示从 head 节点向后遍历, AL_START_TAIL 表示从 tail 节点向前遍历

1.4 链表头文件相关的函数声明

/* Functions implemented as macros */
//获取链表长度
#define listLength(l) ((l)->len)
//获取链表第一个节点
#define listFirst(l) ((l)->head)
//获取链表最后一个节点
#define listLast(l) ((l)->tail)
//获取链表前一个节点
#define listPrevNode(n) ((n)->prev)
//获取链表后一个节点
#define listNextNode(n) ((n)->next)
//获取链表节点的值
#define listNodeValue(n) ((n)->value)

//设置链表的复制函数
#define listSetDupMethod(l,m) ((l)->dup = (m))
//设置链表结构体的释放函数
#define listSetFreeMethod(l,m) ((l)->free = (m))
//设置链表结构体的匹配函数
#define listSetMatchMethod(l,m) ((l)->match = (m))

//获取链表的复制函数
#define listGetDupMethod(l) ((l)->dup)
//获取链表的释放函数
#define listGetFreeMethod(l) ((l)->free)
//获取链表的匹配函数
#define listGetMatchMethod(l) ((l)->match)

/* Prototypes */
//链表创建函数
list *listCreate(void);
//链表释放
void listRelease(list *list);
//清空链表
void listEmpty(list *list);
//添加节点到头部
list *listAddNodeHead(list *list, void *value);
//添加节点到尾部
list *listAddNodeTail(list *list, void *value);

//根据节点指定位置插入新节点
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
//删除指定节点
void listDelNode(list *list, listNode *node);
//获取节点迭代器
listIter *listGetIterator(list *list, int direction);
//获取迭代器下一个节点
listNode *listNext(listIter *iter);
//释放迭代器
void listReleaseIterator(listIter *iter);
//复制链表
list *listDup(list *orig);
//根据 key 值查找节点
listNode *listSearchKey(list *list, void *key);
//根据索引获取节点
listNode *listIndex(list *list, long index);
//设置迭代器, 指定链表从head开始遍历
void listRewind(list *list, listIter *li);
//设置迭代器, 指定链表从tail开始遍历
void listRewindTail(list *list, listIter *li);
//将链表尾节点变头节点
void listRotateTailToHead(list *list);
//将链表头节点变尾节点
void listRotateHeadToTail(list *list);
//将链表o拼接到链表l后面
void listJoin(list *l, list *o);

2 adlist.c 源码解析

2.1 创建空链表函数 listCreate

//创建空链表
list *listCreate(void)
{
    //声明链表
    struct list *list;

    //分配链表内存
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    //初始化首节点与尾节点都为空
    list->head = list->tail = NULL;
    //设置长度为 0
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

• 分配链表内存, 然后将所有指针初始化为 NULL, 链表长度初始为 0

2.2 清空链表节点函数 listEmpty

//清空链表元素, 不回收链表对象的内存
void listEmpty(list *list)
{
    //链表当前长度
    unsigned long len;
    //current 当前遍历指针
    //next 下一个节点的指针
    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;
    }
    //首节点和尾节点置 NULL
    list->head = list->tail = NULL;
    //长度设置为 0
    list->len = 0;
}

• 根据链表长度, 遍历链表对节点进行释放内存直到链表为空
• 这个函数相当于删除所有节点

2.3 释放链表内存函数 listRelease

//释放链表内存
void listRelease(list *list)
{
    //清空链表
    listEmpty(list);
    //释放链表内存
    zfree(list);
}

• 先清空节点, 然后释放链表内存

2.4 添加节点到链表头 listAddNodeHead

//添加节点到头部
list *listAddNodeHead(list *list, void *value)
{
    //节点指针
    listNode *node;

    //分配节点内存, 分配不了则直接返回 NULL
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //设置节点的值
    node->value = value;
    //如果链表长度为0 , 则表示链表为空, 直接指定首节点和尾节点
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //设置当前节点为首节点, 并且加入链表中
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    //链表长度加 1
    list->len++;
    //返回链表
    return list;
}

2.5 添加节点到链表尾

//添加节点到链表尾
list *listAddNodeTail(list *list, void *value)
{
    //声明节点
    listNode *node;

    //分配节点内存, 分配不成功, 则返回 NULL
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //设置节点的值
    node->value = value;
    //如果链表为空
    if (list->len == 0) {
        //初始化链表首节点和尾节点都为当前节点
        list->head = list->tail = node;
        //当前节点的前一个节点和后一个节点都为 NULL
        node->prev = node->next = NULL;
    } else {
        //链表不为空
        //设置原尾节点为当前节点的前一个节点
        node->prev = list->tail;
        //设置尾节点为 NULL
        node->next = NULL;
        //链表原尾节点的下一个节点为当前节点
        list->tail->next = node;
        //更新链表的为节点为当前节点
        list->tail = node;
    }
    //节点长度加 1
    list->len++;
    //返回链表指针
    return list;
}

2.6 根据原有节点指定位置插入新节点 listInsertNode

//根据原有节点指定位置插入新节点
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    //声明新的节点
    listNode *node;

    //新节点分配内存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //设置新节点的值
    node->value = value;
    //如果插入old_node的后面
    if (after) {
        //新节点的上一个节点设置为旧节点
        node->prev = old_node;
        //新节点的下一个节点设置为旧节点的下一个节点
        node->next = old_node->next;
        //如果旧节点是尾节点
        if (list->tail == old_node) {
            //重置当前节点为尾节点
            list->tail = node;
        }
    } else {
        //如果插入old_node的前面
        //新节点的下一个节点为旧节点
        node->next = old_node;
        //新节点的前一个节点为旧节点的前一个节点
        node->prev = old_node->prev;
        //如果旧节点为首节点
        if (list->head == old_node) {
            //更新链表首节点为新的节点
            list->head = node;
        }
    }
    //更新前面节点的下一个节点为 当前节点
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    //更新后面节点的上一个节点为 当前节点
    if (node->next != NULL) {
        node->next->prev = node;
    }
    //增加链表长度
    list->len++;
    //返回
    return list;
}

2.7 删除节点 listDelNode

//删除节点, 主要是各种链表操作哈
void listDelNode(list *list, listNode *node)
{
    //如果当前节点的前一个节点不为 NULL
    if (node->prev)
        //设置前一个节点的下一个节点为当前节点的下一个节点
        node->prev->next = node->next;
    else
        //要删除的节点为首节点, 直接将head设置为下一个节点
        list->head = node->next;
    //如果要删除的节点的下一个节点不为 NULL
    if (node->next)
        //将要删除节点的下一个节点的前一个节点, 重置为当前节点的前一个节点
        node->next->prev = node->prev;
    else
        //要删除的节点是尾节点, 设置前一个节点为尾节点
        list->tail = node->prev;
    //如果free函数存在, 释放节点value的内存
    if (list->free) list->free(node->value);
    //释放节点内存
    zfree(node);
    //链表长度减 1
    list->len--;
}

2.8 获取链表迭代器指针 listGetIterator

//获取链表迭代器指针
listIter *listGetIterator(list *list, int direction)
{
    //声明迭代器
    listIter *iter;

    //分配迭代器内存
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    //如果是前面开始遍历
    if (direction == AL_START_HEAD)
        //遍历节点从head开始
        iter->next = list->head;
    else
        //从后面开始遍历
        iter->next = list->tail;
    //设置遍历方向
    iter->direction = direction;
    //返回指针
    return iter;
}

2.9 释放迭代器对象内存 listReleaseIterator

//释放迭代器对象
void listReleaseIterator(listIter *iter) {
    zfree(iter);
}

2.10 设置迭代器

//设置迭代器, 指定链表从head开始遍历
void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

//设置迭代器, 指定链表从 tail 开始遍历
void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

2.11 获取迭代器下一个节点 listNext

//获取迭代器下一个节点
listNode *listNext(listIter *iter)
{
    //获取下一个节点
    listNode *current = iter->next;

    //下一个节点不为 NULL
    if (current != NULL) {
        //如果是从头开始遍历
        if (iter->direction == AL_START_HEAD)
            //遍历节点更新为下一个节点
            iter->next = current->next;
        else
            //从尾部开始遍历, 遍历节点更新为上一个节点
            iter->next = current->prev;
    }
    //返回当前节点
    return current;
}

2.12 复制链表 listDup

//复制链表
list *listDup(list *orig)
{
    //声明复制的链表
    list *copy;
    //声明迭代器
    listIter iter;
    //
    listNode *node;

    //创建空链表, 为 NULL, 则直接返回 NULL
    if ((copy = listCreate()) == NULL)
        return NULL;
    //继承原链表的相关函数
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    //设置迭代器从头开始遍历
    listRewind(orig, &iter);
    //获取下一个节点
    while((node = listNext(&iter)) != NULL) {
        //值指针
        void *value;

        //如果有复制value的函数
        if (copy->dup) {
            //用函数拷贝值
            value = copy->dup(node->value);
            //如果为空, 则释放要拷贝的链表并且返回 NULL
            if (value == NULL) {
                listRelease(copy);
                return NULL;
            }
        } else
            //没有拷贝函数, 则直接获取值
            value = node->value;
        //添加值添加到copy链表的尾部, 内存分配失败则释放copy链表的内存并返回NULL
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            return NULL;
        }
    }
    //返回拷贝的链表
    return copy;
}

2.13 根据key查节点 listSearchKey

//根据key查节点
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;
            }
        }
    }
    //没找到, 则返回 NULL
    return NULL;
}

2.14 获取指定下标的节点 listIndex

//获取指定下标的节点
listNode *listIndex(list *list, long index) {
    listNode *n;

    //如果 index 小于 0 , 则从后面遍历
    if (index < 0) {
        //取正数
        index = (-index)-1;
        //获取初始节点
        n = list->tail;
        //逐个索引迭代
        while(index-- && n) n = n->prev;
    } else {
        //从前面遍历
        n = list->head;
        //逐个索引迭代
        while(index-- && n) n = n->next;
    }
    //返回节点
    return n;
}

2.15 头尾节点互换

//将链表尾节点变头节点
void listRotateTailToHead(list *list) {
    //长度小于等于一个节点, 不处理
    if (listLength(list) <= 1) return;

    /* Detach current tail */
    //获取链表尾节点
    listNode *tail = list->tail;
    //重置尾节点为上一个节点
    list->tail = tail->prev;
    //重置新的尾节点的下一个节点为NULL
    list->tail->next = NULL;
    /* Move it as head */
    //设置head的前一个节点为 tail
    list->head->prev = tail;
    //设置 tail 前一个节点为 NULL
    tail->prev = NULL;
    //更新 tail 的下一个节点为链表的 head
    tail->next = list->head;
    //重置 head 节点为 tail
    list->head = tail;
}

/* Rotate the list removing the head node and inserting it to the tail. */
//将头节点变尾节点, 代码基本同 listRotateTailToHead 一致
void listRotateHeadToTail(list *list) {
    if (listLength(list) <= 1) return;

    listNode *head = list->head;
    /* Detach current head */
    list->head = head->next;
    list->head->prev = NULL;
    /* Move it as tail */
    list->tail->next = head;
    head->next = NULL;
    head->prev = list->tail;
    list->tail = head;
}

2.16 将链表o拼接到链表l后面

//将链表o拼接到链表l后面
void listJoin(list *l, list *o) {
    //如果要合并的链表长度为 0, 则不处理
    if (o->len == 0) return;

    //设置 o 的头节点的前节点为 l 的尾节点
    o->head->prev = l->tail;

    //如果l的尾节点不为NULL
    if (l->tail)
        //设置 l 的尾节点的下一个节点为 o 的头节点
        l->tail->next = o->head;
    else
        //如果l的尾节点为NULL, 则直接用o的首节点作用l的首节点
        l->head = o->head;

    //更新 l 的尾节点
    l->tail = o->tail;
    //更新l链表的长度
    l->len += o->len;

    /* Setup other as an empty list. */
    //清空o链表
    o->head = o->tail = NULL;
    o->len = 0;
}

3 小结

链表超级简单, 实现上也跟java的LinkedList 差不多.

微信文章链表: https://mp.weixin.qq.com/s?__biz=MzI3NDAxNTAzMw==&mid=2247483721&idx=1&sn=e4d7c32ec51cf67824e5fda961c47d55&chksm=eb1b371fdc6cbe09222d867900b6a1d8022380046c94ce292ddc7929615c55538d3454ba3d68&token=697250728&lang=zh_CN#rd

个人微信: wolfleong

微信公众号: wolfleong