
- 本文对Redis源码的学习是基于5.0.2版本.
前言
Redis实现的链表的数据结构为双端链表.
List --- (源文件adlist.h/adlist.c)
List的结构体如下 :
# 结点 listNode
typedef struct listNode {
// 指向上一结点指针
struct listNode *prev;
// 指向下一结点指针
struct listNode *next;
// 保存的value值
void *value;
} listNode;
# 迭代器结构体 listIter 通过这个迭代器可以选择从Header遍历或者Tail遍历
typedef struct listIter {
// 指针指向下一结点
listNode *next;
// 方向 : Header 或者 Tail
int direction;
} listIter;
# 链表结构体 : list
typedef struct list {
// 头结点指针
listNode *head;
// 尾结点指针
listNode *tail;
// 自定义的复制函数,如果不定义,默认策略是复制操作会让原链表和新链表共享同一个value数据域
void *(*dup)(void *ptr);
// 自定义free操作函数,如果不定义,默认策略是释放链表节点所保存的value值
void (*free)(void *ptr);
// 自定义比较两个value值函数,默认策略是比较两个指针的值
int (*match)(void *ptr, void *key);
// 记录链表的长度,获取长度操作可以O(1)
unsigned long len;
} list;
# 对应的迭代器结构体是direction属性, 0表示从Header遍历、1表示Tail
#define AL_START_HEAD 0
#define AL_START_TAIL 1
创建 --- listCreate()
# listCreate()
list *listCreate(void)
{
1. // 结构体 list
struct list *list;
2. // 申请内存
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
3. // head、tail指向NULL
list->head = list->tail = NULL;
4. len初始化为0
list->len = 0;
// 使用默认策略
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
置空链表并回收相关的结构体内存 --- listRelease()
# listRelease()
void listRelease(list *list)
{
1. // 调用的listEmpty
listEmpty(list);
2. / 回收链表的内存
zfree(list);
}
置空链表并保留相关的结构体内存 --- listEmpty()
# listEmpty()
void listEmpty(list *list)
{
unsigned long len;
listNode *current, *next;
1. // 获取头结点,从头结点开始清理
current = list->head;
len = list->len;
while(len--) {
next = current->next;
1.1 // free()回收value值
if (list->free) list->free(current->value);
1.2 // 回收当前结点
zfree(current);
1.3 // 继续遍历下一结点
current = next;
}
2. // 所有结点处理完毕,head、tail指向NULL
list->head = list->tail = NULL;
3. // len初始为0
list->len = 0;
}
从头结点插入listNode--- listAddNodeHead()
# listAddNodeHead()
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
1. // 申请内存
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
2. // 插入结点保存value值
node->value = value;
3. // 此时链表中没有结点
if (list->len == 0) {
3.1 // head、tail 指向插入结点
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
4. // 此时链表存在结点
node->prev = NULL;
4.1 // node.next指向head
node->next = list->head;
4.2 // head.prev指向node
list->head->prev = node;
4.3 // head指向新插入的node
list->head = node;
}
5. len+1
list->len++;
return list;
}
从尾结点插入listNode --- listAddNodeTail()
同 listAddNodeHead() 相反,是从尾结点插入.
# listAddNodeHead()
list *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;
}
指定结点插入listNode--- listInsertNode()
# listInsertNode()
/**
参数说明 :
list *list : 相关操作的链表
listNode *old_node : 指定结点
void *value : 插入结点value值
int after : 根据这个值来判断插入在指定结点的next位置 还是 prev位置
*/
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
1. // 申请内存
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
2. // 保存插入结点的value值
node->value = value;
3. // 插入在指定结点的next位置
if (after) {
3.1 // node.prev 指向 指定结点
node->prev = old_node;
3.2 // node->next 指向 指定结点的next结点
node->next = old_node->next;
3.3 // 如果指定结点是tail,则tail指向 插入结点
if (list->tail == old_node) {
list->tail = node;
}
} else {
4. // 插入在指定结点的prev位置
4.1 // node.next 指向 指定的结点
node->next = old_node;
4.2 // node.prev 指向 指定结点的prev结点
node->prev = old_node->prev;
4.3 // 如果指定结点是head,则head指向 插入结点
if (list->head == old_node) {
list->head = node;
}
}
5. // 如果是插入在指定结点的next位置,那么 指定结点还需要 与 插入结点连接起来
if (node->prev != NULL) {
5.1 // 指定结点的next指向 插入结点
node->prev->next = node;
}
6. // 如果是插入在指定结点的prev位置,那么 指定结点还需要 与 插入结点连接起来
if (node->next != NULL) {
6.1 // 指定结点的prev 指向 插入结点
node->next->prev = node;
}
7. len+1
list->len++;
return list;
}
删除指定结点listNode--- listDelNode()
# listDelNode()
void listDelNode(list *list, listNode *node)
{
# 处理 prev
1. // 删除的结点不是头结点
if (node->prev)
1.1 // 删除结点的prev结点的next指向 删除结点的next结点
node->prev->next = node->next;
else
2. // 删除的结点是头结点
2.1 // head指向删除结点的next结点
list->head = node->next;
# 处理 prev
# 处理 next
3. // 删除的结点不是尾结点
if (node->next)
3.1 // 删除结点的next结点的prev指向删除结点的prev结点
node->next->prev = node->prev;
else
4. // 删除的结点是尾结点
3.2 // tail指向删除结点的prev结点
list->tail = node->prev;
# 处理 next
// 删除结点的next、prev已经断开,开始回收内存
5. // 回收value值
if (list->free) list->free(node->value);
6. // 回收node
zfree(node);
7. len-1
list->len--;
}
获取迭代器--- listGetIterator()
# listGetIterator()
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;
1. // 申请内存
if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
2. // 根据direction返回从head遍历的迭代器
if (direction == AL_START_HEAD)
iter->next = list->head;
else
3. // 根据direction返回从tail遍历的迭代器
iter->next = list->tail;
4. 设置方向值
iter->direction = direction;
return iter;
}
根据迭代器获取链表--- listNext()
# listNext()
listNode *listNext(listIter *iter)
{
listNode *current = iter->next;
if (current != NULL) {
1. // 从头结点开始的链表
if (iter->direction == AL_START_HEAD)
iter->next = current->next;
2. // 从尾结点开始的链表
else
iter->next = current->prev;
}
return current;
}
回收迭代器--- listReleaseIterator()
# listReleaseIterator()
void listReleaseIterator(listIter *iter) {
zfree(iter);
}
拷贝链表--- listDup()
拷贝链表 : 默认策略是使用同一指针的value值.
# listDup()
list *listDup(list *orig)
{
list *copy;
listIter iter;
listNode *node;
1. // 根据listCreate()创建拷贝的链表
if ((copy = listCreate()) == NULL)
return NULL;
2. // 保存dup、free、match
copy->dup = orig->dup;
copy->free = orig->free;
copy->match = orig->match;
3. // 设置从头结点遍历的迭代器(从Head遍历)
listRewind(orig, &iter);
4. // 数据迁移到拷贝链表中
while((node = listNext(&iter)) != NULL) {
void *value;
4.1 // 如果自己定义了dup()
if (copy->dup) {
4.2 // 使用自定义dup()
value = copy->dup(node->value);
if (value == NULL) {
listRelease(copy);
return NULL;
}
} else
4.3 // 默认策略,使用同一指针的value值
value = node->value;
5. // 结点添加到copy链表中
if (listAddNodeTail(copy, value) == NULL) {
listRelease(copy);
return NULL;
}
}
6. // 返回已经完成的copy链表
return copy;
}
设置从头结点遍历的迭代器(从Head遍历) --- listRewind()
# listRewind()
void listRewind(list *list, listIter *li) {
li->next = list->head;
li->direction = AL_START_HEAD;
}
设置从尾结点遍历的迭代器(从Tail遍历) --- listRewindTail()
# listRewindTail()
void listRewindTail(list *list, listIter *li) {
li->next = list->tail;
li->direction = AL_START_TAIL;
}
根据value查找listNode --- listSearchKey()
# listSearchKey()
listNode *listSearchKey(list *list, void *key)
{
listIter iter;
listNode *node;
1. // 初始化默认迭代模式
listRewind(list, &iter);
2. // 开始遍历查找
while((node = listNext(&iter)) != NULL) {
2.1 // 如果有自定义match()函数则执行自定义
if (list->match) {
2.2 // 调用自定义match()
if (list->match(node->value, key)) {
2.3 // 查找到该value值的listNode结点
return node;
}
} else {
2.4 // 使用默认策略,比较指向同一指针的value值
if (key == node->value) {
2.5 // 查找到该value值的listNode结点
return node;
}
}
}
3. // 没有查找到
return NULL;
}
根据index查找对应的listNode --- listIndex()
# listIndex()
listNode *listIndex(list *list, long index) {
listNode *n;
1. // index小于0,从tail查找
if (index < 0) {
index = (-index)-1;
n = list->tail;
while(index-- && n) n = n->prev;
} else {
2. // 否则从head查找
n = list->head;
while(index-- && n) n = n->next;
}
3. // 返回listNode
return n;
}
将尾结点移到头结点 --- listRotate()
# listRotate()
void listRotate(list *list) {
1. // 获取尾结点指针,把该结点提到头结点
listNode *tail = list->tail;
if (listLength(list) <= 1) return;
# 处理尾结点 : 断开
2. // 链表的tail指针指向 尾结点的prev结点
list->tail = tail->prev;
3. // 链表的tail结点的next为NULL
list->tail->next = NULL;
# 处理尾结点
# 处理头结点
4. // list->head结点的prev指针指向 尾结点指针
list->head->prev = tail;
5. // 尾结点的prev 为 NULL
tail->prev = NULL;
6. // 尾结点的next 指向 list->head结点
tail->next = list->head;
7. list->head 指向 尾结点
list->head = tail;
# 处理头结点
}
拼接两条链表 --- listJoin()
# listJoin()
void listJoin(list *l, list *o) {
# 处理o链表的 head.prev 与 l链表的 tail 连接起来
1. // 如果o链表存在结点
if (o->head)
1.1 // 把o链表的prev与l链表的尾结点接上
o->head->prev = l->tail;
# 处理o链表的 head.prev 与 l链表的 tail 连接起来
# 处理l链表的 tail.next 与 o链表的 head 连接起来
2. // 如果l链表存在结点
if (l->tail)
2.1 // 把o链表通过l链表的尾结点的prev与0链表的头结点接上
l->tail->next = o->head;
else
3. // l链表不存在结点
3.1 // l链表head指向o链表head
l->head = o->head;
# 处理l链表的 tail.next 与 o链表的 head 连接起来
# 处理o链表的尾结点
4. // 如果o链表存在结点,则设置l链表的tail指向o链表的tail
if (o->tail) l->tail = o->tail;
# 处理o链表的尾结点
5. // 重新计算l的len值
l->len += o->len;
6. //重置o链表的head、tail、len
o->head = o->tail = NULL;
o->len = 0;
}
结束语
- 本文把list的所有API都贴出来了.
- 应用场景 : 链表被广泛于实现Redis的各种功能 : 例如key-valu的列表键、发布与订阅、慢查询、监视器等.
- 原创不易
- 希望看完这篇文章的你有所收获!
相关参考资料
- Redis设计与实现【书籍】