redis源码分析：链表实现
一、链表定义
链表在redis中的使用十分广泛，例如列表的底层实现之一就是链表，包括发布、订阅等等功能都是有用到链表的。redis中链表在adlist.h和adlist.c中实现，只用了300+行代码，十分简单。
redis中的链表是一个双向不循环的链表，两个核心的数据结构是listNode和list，其中listNode的定义如下：
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;listNode是链表节点定义，链表节点和平常用到差别不大，由一个数据域和两个分别指向前后节点的指针组成。
list的定义为：
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned int len;
} list;它和普通链表定义的不同点在于：除了包含首尾指针以及链表长度以外，链表的结构还包含了3个函数指针结构：
dup: 用于拷贝节点的函数。free: 用于释放节点的函数。match: 用于对比节点是否相等的函数。
链表的宏观结构：
二、链表操作
2.1 链表创建和释放
初始化的过程主要是创建链表对象，并初始化值：
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;
}释放链表：
void listRelease(list *list)
{
unsigned int len;
listNode *current, *next;
current = list->head;
len = list->len;
// 循环遍历链表
while(len--) {
next = current->next;
// 如果有自定义的free函数，先调用函数释放节点内部数据
if (list->free) list->free(current->value);
// 释放节点
zfree(current);
current = next;
}
// 释放链表
zfree(list);
}2.2 插入节点
插入节点提供了三个函数，分别是从头部插入、从尾部插入以及从指定位置插入。
头插法：
list *listAddNodeHead(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 = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
// 长度加1
list->len++;
return list;
}尾插法，和头插法基本一致：
ist *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;
}插入节点到指定位置：
/*
* 参数说明
* @list 链表对象
* @old_node 被插入的节点
* @value 新插入节点的数据域
* @after 是查到节点的后面还是前面
* @return 插入成功后返回传入的链表对象，否则返回NULL
*/
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
// 创建新节点并赋值
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
// 插入节点
if (after) {
// 插入到old_node节点后
node->prev = old_node;
node->next = old_node->next;
if (list->tail == old_node) {
list->tail = node;
}
} else {
// 插入到old_节点前
node->next = old_node;
node->prev = old_node->prev;
if (list->head == old_node) {
list->head = node;
}
}
// 修改前一个节点的next指向
if (node->prev != NULL) {
node->prev->next = node;
}
// 修改后一个节点的prev指向
if (node->next != NULL) {
node->next->prev = node;
}
// 链表长度加1
list->len++;
return list;
}2.3 删除节点
void listDelNode(list *list, listNode *node)
{
if (node->prev) // 删除的不是头结点，修改前一个节点的next指针
node->prev->next = node->next;
else // 删除的是头结点，更新head指向
list->head = node->next;
if (node->next)
node->next->prev = node->prev;
else // 删除的是尾结点，更新next指向
list->tail = node->prev;
// 存在节点的free函数，调用函数释放节点内部资源
if (list->free) list->free(node->value);
zfree(node);
list->len--;
}三、链表遍历
redis在实现链表的时候，给链表的遍历单独创建了一套结构和方法。其中遍历的结构是listIter，它包含了一个listNode *的指针域和遍历方向direction：
typedef struct listIter {
listNode *next;
int direction;
} listIter;direction的作用是标记遍历方向是从头部往尾部遍历还是从尾部往头部遍历，获取一个listIter的方法：
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; // 从头往尾遍历，iter指向头结点
else
iter->next = list->tail; // 从尾往头遍历，iter指向尾结点
iter->direction = direction;
return iter;
}配合listNode获取下一个节点的函数：
listNode *listNext(listIter *iter)
{
// 保存当前指针
listNode *current = iter->next;
//
if (current != NULL) {
if (iter->direction == AL_START_HEAD)
iter->next = current->next; // 赋值下一个节点到iter
else
iter->next = current->prev; // 赋值前一个节点到iter
}
return current;
}注意listNext函数只是获取当前iter指向的节点，并把iter指向下一个节点。为什么要把遍历操作单独抽离出来呢？
主要有以下几个目的：
- 外部遍历时不用重复编写遍历代码。前面已经说过，链表在redis很多场景都用到了，所有的结构共用一套遍历实现就可以了。
- 外部遍历的时候无需访问list的内部元素，充分做到了面向对象的理念。
四、其他
4.1 链表拷贝
list *listDup(list *orig)
{
list *copy;
listIter *iter;
listNode *node;
// 为新链表创建内存空间
if ((copy = listCreate()) == NULL)
return NULL;
// 初始化
copy->dup = orig->dup;
copy->free = orig->free;
copy->match = orig->match;
// 遍历
iter = listGetIterator(orig, AL_START_HEAD);
while((node = listNext(iter)) != NULL) {
void *value;
if (copy->dup) {
// 如果存在复制函数，使用自定的复制函数来复制每个节点
value = copy->dup(node->value);
if (value == NULL) {
// 复制失败，释放掉前面已经拷贝成功的节点，避免内存泄漏
listRelease(copy);
listReleaseIterator(iter);
return NULL;
}
} else
value = node->value;
// 新拷贝的节点插入到链表结尾
if (listAddNodeTail(copy, value) == NULL) {
listRelease(copy);
listReleaseIterator(iter);
return NULL;
}
}
listReleaseIterator(iter);
return copy;
}4.2 链表查找
listNode *listSearchKey(list *list, void *key)
{
listIter *iter;
listNode *node;
// 遍历链表
iter = listGetIterator(list, AL_START_HEAD);
while((node = listNext(iter)) != NULL) {
if (list->match) {
// 使用自定义的比较函数来比较每个节点和查找的key
if (list->match(node->value, key)) {
listReleaseIterator(iter);
return node;
}
} else {
// 使用默认的比较函数来比较节点和key
if (key == node->value) {
listReleaseIterator(iter);
return node;
}
}
}
listReleaseIterator(iter);
return NULL;
}4.3 返回指定位置上的元素
传入索引，返回对应位置上的元素，支持从尾部索引：
listNode *listIndex(list *list, int index) {
listNode *n;
if (index < 0) {
// index小于0，从尾部开始索引
index = (-index)-1;
n = list->tail;
while(index-- && n) n = n->prev;
} else {
// index大于0，从头部开始索引
n = list->head;
while(index-- && n) n = n->next;
}
return n;
}五、总结
收获很大，主要是两个地方感触很深：
- 链表的遍历
- 从尾部开始返回对应索引位置上面的元素
其实实现并不算难，只是实现的思路和想法很新颖，很值得学习！
