Redis 数据结构 双向链表(linkedlist)
(1) 双向链表是什么
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
双向链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
(2) 为什么要用双向链表
数组需要申请一块连续的内存空间，在数据量比较大并且频繁插入数据时空间复杂度较高，对性能影响较大。
而链表在插入数据时，时间复杂度、空间复杂度都比较小。
(3) 双向链表怎么实现
简单实现
(4) Redis里的双向链表
(5) 源码解析
源码：https://github.com/redis/redis/blob/6.0/src/adlist.c
(5.1) 结构定义
// file: src/adlist.h
/*
* 双向链表
*/
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;// file: src/adlist.h
/*
* 链表节点
*/
typedef struct listNode {
struct listNode *prev; // 前驱
struct listNode *next; // 后继
void *value; // 值
} listNode; listNode 带有 prev 和 next 两个指针，因此可以双向遍历：从头到尾，从尾到头。
listNode 的value的类型是 *void ，说明这个双向链表对节点所保存的值的类型没有限制。
(5.2) 新建双向链表
/*
* 创建一个链表
*
* 创建的列表可以用listRelease()释放，
* 但是每个节点的私有值需要用户在调用listRelease()之前释放，
* 或者使用listSetFreeMethod设置释放方法。
*
* 失败时返回NULL。否则指向新列表的指针。
*/
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;
}(5.3) 链表头部添加节点-listAddNodeHead
/*
* 添加新节点到链表的头部，包含指定的"值"指针作为值
*
* 出错时，返回 NULL 并且不执行任何操作（即列表保持不变）。
* 成功时，返回传递给函数的“列表”指针。
*
* @param *list
* @param *value
*/
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;
}
// 更新链表长度
list->len++;
return list;
}(5.4) 链表尾部添加节点-listAddNodeTail
/*
* 添加新节点到链表的尾部，包含指定的"值"指针作为值
*
* 出错时，返回 NULL 并且不执行任何操作（即列表保持不变）。
* 成功时，返回传递给函数的“列表”指针。
*
* @param *list
* @param *value
*/
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
// 创建链表节点
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
// 赋值
node->value = value;
//
if (list->len == 0) { // 链表长度为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;
}(5.5) 链表添加节点-listInsertNode
/*
* 插入节点
*
* @param *list 链表
* @param *old_node 老节点
* @param *value 要设置的值
* @param after 在第几个节点后
*/
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) { // after > 0
// 设置节点的前驱
node->prev = old_node;
// 设置节点的后继
node->next = old_node->next;
if (list->tail == old_node) {
// 更新尾结点
list->tail = node;
}
} else {
// 设置节点的后继
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;
}(5.6) 链表删除节点-listDelNode
/*
* 从指定列表中删除指定节点。
* 由调用者释放节点的私有值。
*
* 这个函数不能失败 This function can't fail.
*/
void listDelNode(list *list, listNode *node)
{
// 处理节点前驱
if (node->prev) // 节点前驱不为空
// 断链 把前一个节点的后继直接指向节点的后继，相当于把当前节点删除了
node->prev->next = node->next;
else // 节点前驱为空，也就是头节点
// 头结点直接指向当前节点的后继，相当于把头结点删除了
list->head = node->next;
// 处理节点后继
if (node->next) // 节点后继不为空
// 断链 把下一个节点的前驱直接指向当前节点的前驱，相当于把当前节点删除了
node->next->prev = node->prev;
else // 节点后继为空，也就是node是尾结点
// 尾节点直接指向当前节点的前驱，相当于把尾结点删除了
list->tail = node->prev;
// 释放节点值的内存
if (list->free) list->free(node->value);
// 释放节点内存
zfree(node);
// 更新节点长度
list->len--;
}(5.7) 链表查找-listSearchKey
/*
* 在列表中搜索与给定key匹配的节点。
* 使用通过 listSetMatchMethod() 设置的“匹配”方法执行匹配。
* 如果没有设置'match'方法，则直接将每个节点的'value'指针与'key'指针进行比较。
*
* 成功时返回第一个匹配的节点指针（搜索从头开始）。
* 如果不存在匹配的节点，则返回 NULL。
*/
listNode *listSearchKey(list *list, void *key)
{
listIter iter;
listNode *node;
// 迭代器&iter 相当于游标 curr
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;
}
}
}
return NULL;
}/*
* 在列表私有迭代器结构中创建一个迭代器
*/
void listRewind(list *list, listIter *li) {
li->next = list->head;
li->direction = AL_START_HEAD;
}/* Return the next element of an iterator.
* It's valid to remove the currently returned element using
* listDelNode(), but not to remove other elements.
*
* The function returns a pointer to the next element of the list,
* or NULL if there are no more elements, so the classical usage
* pattern is:
*
* iter = listGetIterator(list,<direction>);
* while ((node = listNext(iter)) != NULL) {
* doSomethingWith(listNodeValue(node));
* }
*
* */
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;
}// file: server.c
/*
* 初始化server配置
*/
void initServer(void) {
// 创建双向链表
server.pubsub_patterns = listCreate();
// 双向链表设置 match方法
listSetMatchMethod(server.pubsub_patterns,listMatchPubsubPattern);
}// file: src/pubsub.c
int listMatchPubsubPattern(void *a, void *b) {
pubsubPattern *pa = a, *pb = b;
return (pa->client == pb->client) &&
(equalStringObjects(pa->pattern,pb->pattern));
}// file: src/
/* Equal string objects return 1 if the two objects are the same from the
* point of view of a string comparison, otherwise 0 is returned. Note that
* this function is faster then checking for (compareStringObject(a,b) == 0)
* because it can perform some more optimization.
*/
int equalStringObjects(robj *a, robj *b) {
// 判断编码
if (a->encoding == OBJ_ENCODING_INT &&
b->encoding == OBJ_ENCODING_INT){ // 都是整数
// 如果两个字符串都是整数只需要检查存储的整数是否相等
return a->ptr == b->ptr;
} else {
// 对比字符串对象
return compareStringObjects(a,b) == 0;
}
}(5.8) 链表释放-listRelease
/*
* 释放整个链表
*
* 这个函数不能失败
*/
void listRelease(list *list)
{
// 释放链表里所有节点的值及节点
listEmpty(list);
// 释放链表的内存
zfree(list);
}/*
* 移除所有的元素 而 不销毁链表本身
*/
void listEmpty(list *list)
{
unsigned long 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;
}
// 更新头节点 尾节点
list->head = list->tail = NULL;
list->len = 0;
}参考资料
[1] Redis设计与实现-双端链表
[2] Redis源码剖析与实战 -
[3] Redis源码-adlist.c-github