文章目录
- 前言
- 一、链表简介
- 二、链表实现
- 1.链表节点实现
- 2.链表实现
- 3.链表迭代器实现
- 4.链表API
- 总结
前言
本文对Redis的底层数据结构链表做了简要介绍，涉及的文件是adlist.h和adlist.c。
一、链表简介
链表是一种非常常用的数据结构，在很多高级语言中都有实现。Redis 使用的 C 语言并没有内置这种数据结构， 所以 Redis 构建了自己的链表实现。 链表在 Redis 中的应用非常广泛， 比如列表键的底层实现之一就是链表： 当一个列表键包含了数量比较多的元素， 又或者列表中包含的元素都是比较长的字符串时， Redis 就会使用链表作为列表键的底层实现。 除了链表键之外， 发布与订阅、慢查询、监视器等功能也用到了链表， Redis 服务器本身还使用链表来保存多个客户端的状态信息， 以及使用链表来构建客户端输出缓冲区（output buffer），后续的部分文章将陆续对这些链表应用进行介绍。
二、链表实现
1.链表节点实现
在adlist.h中定义了listNode结构代表链表节点，如下所示：
代码语言：javascript复制/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;可以看出链表节点是双向的，并且通过void *指针可以存各种类型的值，通过节点的prev和next指针我们就可以连接出一个双向链表如下图所示：
2.链表实现
虽然可以直接用节点来构造双向链表，但是实际链表实现时还会再定义一个链表结构。如下所示：
代码语言：javascript复制/*
* 双端链表结构
*/
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;可以看出通过定义list结构体，就可以常数时间内获得链表头尾节点以及链表长度，这些都是只用链表节点来表示链表时不具备的。 此外list中还定义了节点值的复制、释放和对比函数，dup 函数用于复制链表节点所保存的值；free 函数用于释放链表节点所保存的值；match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。通过这些函数的定义使得链表的特性更加的复杂多样。
3.链表迭代器实现
Redis为了便于访问链表元素，还定义了链表的迭代器代码如下：
代码语言：javascript复制/* Directions for iterators
*
* 迭代器进行迭代的方向
*/
// 从表头向表尾进行迭代
#define AL_START_HEAD 0
// 从表尾到表头进行迭代
#define AL_START_TAIL 1
/*
* 双端链表迭代器
*/
typedef struct listIter {
// 当前迭代到的节点
listNode *next;
// 迭代的方向
int direction;
} listIter;可以看出list的迭代器可以支持两个方向的遍历。
4.链表API
选取了部分链表API进行剖析。创建一个空链表的代码如下所示：
代码语言：javascript复制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;
}在指定节点之前或者之后插入节点的代码如下所示：
代码语言：javascript复制/*
* 创建一个包含值 value 的新节点，并将它插入到 old_node 的之前或之后
*
* 如果 after 为 0 ，将新节点插入到 old_node 之前。
* 如果 after 为 1 ，将新节点插入到 old_node 之后。
*
* T = O(1)
*/
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) {
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;
}创建和释放一个迭代器的代码如下所示：
代码语言：javascript复制/*
* 为给定链表创建一个迭代器，
* 之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点
*
* direction 参数决定了迭代器的迭代方向：
* AL_START_HEAD ：从表头向表尾迭代
* AL_START_TAIL ：从表尾想表头迭代
*
* T = O(1)
*/
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;
else
iter->next = list->tail;
// 记录迭代方向
iter->direction = direction;
return iter;
}
/* Release the iterator memory */
/*
* 释放迭代器
*
* T = O(1)
*/
void listReleaseIterator(listIter *iter) {
zfree(iter);
}链表中查找指定元素函数如下所示：
代码语言：javascript复制/*
* 查找链表 list 中值和 key 匹配的节点。
*
* 对比操作由链表的 match 函数负责进行，
* 如果没有设置 match 函数，
* 那么直接通过对比值的指针来决定是否匹配。
*
* 如果匹配成功，那么第一个匹配的节点会被返回。
* 如果没有匹配任何节点，那么返回 NULL 。
*
* T = O(N)
*/
listNode *listSearchKey(list *list, void *key)
{
listIter *iter;
listNode *node;
// 迭代整个链表
iter = listGetIterator(list, AL_START_HEAD);
while((node = listNext(iter)) != NULL) {
// 对比
if (list->match) {
if (list->match(node->value, key)) {
listReleaseIterator(iter);
// 找到
return node;
}
} else {
if (key == node->value) {
listReleaseIterator(iter);
// 找到
return node;
}
}
}
listReleaseIterator(iter);
// 未找到
return NULL;
}总结
本文对Redis的链表结构进行了简单介绍，如有不当之处，请指正。
