redis 5.0.7 源码阅读——双向链表
2024-09-07 20:31:38
redis中双向链表相关的文件为：adlist.h与adlist.c
一、数据结构
redis里定义的双向链表，与普通双向链表大致相同
单个节点：
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
链表：
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;
链表以函数指针的方式，实现了复制、销毁与比较的方法的多态。
迭代器：
typedef struct listIter {
listNode *next;
int direction;
} listIter;
迭代器中有个成员变量direction，用于表示当前遍历的方向。
大致结构：
/*
+-------------------+ +----------------> +--------------+ <-------+
|listNode *head |--------+ |listNode *prev|-->NULL |
+-------------------+ +--------------+ |
|listNode *tail |--------+ |listNode *next|----+ |
+-------------------+ | +--------------+ | |
|void *(*dup)(...) | | |void *value | | |
+-------------------+ | +--------------+ | |
|void (*free)(...) | | | |
+-------------------+ | | |
|int (*match)(...) | | | |
+-------------------+ +----------------> +--------------+ <--+ |
|unsigned long len | |listNode *prev|---------+
+-------------------+ +--------------+
|listNode *next|-->NULL
+--------------+
|void *value |
+--------------+
*/
二、创建
redis中创建一个初始双向链表比较简单，只要分配好内存，并给成员变量赋初值就可以了
list *listCreate(void)
{
struct list *list; if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
list->head = list->tail = NULL;
list->len = ;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
redis中提供了头插法、尾插法以及指定位置插入节点三种方式向链表中添加节点，与普通双向链表无异，此处不做详细叙述。
三、销毁
因链表中每个节点的value可能指向堆空间，故不能直接把list结构体free，这样会造成内存泄露。需要先将每个节点的value释放，才可以free结构体
清空所有节点：
void listEmpty(list *list)
{
unsigned long len;
listNode *current, *next; current = list->head;
len = list->len;
while(len--) {
next = current->next;
//若指定了销毁的函数，则使用指定的函数进行销毁value
if (list->free) list->free(current->value);
zfree(current);
current = next;
}
list->head = list->tail = NULL;
list->len = ;
}
销毁链表：
void listRelease(list *list)
{
listEmpty(list);
zfree(list);
}
同样，redis的链表提供了与普通链表相同的删除单个节点的操作，此处也不做叙述。
四、迭代器操作
redis中提供了获取迭代器的接口
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;
}
以AL_START_HEAD为例，生成好的迭代器结构如下：
/*
+-------------------+ +---> +--------------+ <-------+----+
|listNode *head |----+ |listNode *prev|-->NULL | |
+-------------------+ +--------------+ | | +--------------+
|listNode *tail |----+ |listNode *next|----+ | +--|listNode *next|
+-------------------+ | +--------------+ | | +--------------+
|void *(*dup)(...) | | |void *value | | | |int direction |
+-------------------+ | +--------------+ | | +--------------+
|void (*free)(...) | | | |
+-------------------+ | | |
|int (*match)(...) | | | |
+-------------------+ +---> +--------------+ <--+ |
|unsigned long len | |listNode *prev|---------+
+-------------------+ +--------------+
|listNode *next|-->NULL
+--------------+
|void *value |
+--------------+
*/
迭代器的next方法：
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;
}
调用一次之后的结构：
/*
+-------------------+ +---> +--------------+ <-------+
|listNode *head |----+ |listNode *prev|-->NULL |
+-------------------+ +--------------+ | +--------------+
|listNode *tail |----+ |listNode *next|----+ | +--|listNode *next|
+-------------------+ | +--------------+ | | | +--------------+
|void *(*dup)(...) | | |void *value | | | | |int direction |
+-------------------+ | +--------------+ | | | +--------------+
|void (*free)(...) | | | | |
+-------------------+ | | | |
|int (*match)(...) | | | | |
+-------------------+ +---> +--------------+ <--+----|----+
|unsigned long len | |listNode *prev|---------+
+-------------------+ +--------------+
|listNode *next|-->NULL
+--------------+
|void *value |
+--------------+
*/
再次调用：
/*
+-------------------+ +---> +--------------+ <-------+
|listNode *head |----+ |listNode *prev|-->NULL |
+-------------------+ +--------------+ | +--------------+
|listNode *tail |----+ |listNode *next|----+ | +--|listNode *next|
+-------------------+ | +--------------+ | | | +--------------+
|void *(*dup)(...) | | |void *value | | | | |int direction |
+-------------------+ | +--------------+ | | | +--------------+
|void (*free)(...) | | | | |
+-------------------+ | | | |
|int (*match)(...) | | | | |
+-------------------+ +---> +--------------+ <--+ | +-->NULL
|unsigned long len | |listNode *prev|---------+
+-------------------+ +--------------+
|listNode *next|-->NULL
+--------------+
|void *value |
+--------------+
*/
调用next函数的返回值为调用之前的listNode首地址
五、其它操作
redis的双向链表还提供了其它操作。其中，查找指定的key与复制整个list依赖于迭代器的使用，并使用到自定义的比较/复制方法。
除此之外，还提供了类似随机读取的方式，其内部实现为遍历，且“越界”时返回NULL。同时，它支持index为负数，表示从尾开始。类似旋转的操作，把尾节点移至原头节点之前，成为新的头节点。当然，还有拼接两个链表的操作。
redis 5.0.7 下载链接
http://download.redis.io/releases/redis-5.0.7.tar.gz
源码阅读顺序参考：
https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst
最新文章
- GCC 中零长数组与变长数组
- svn: E155004 is already locked 解决方案
- .NET Core也可以使用MongoDB了
- history 清空历史记录 或 history不记录历史命令
- 在 Apache error_log 中看到多个信息，提示 RSA server certificate CommonName (CN) 与服务器名不匹配(转)
- MySQL单机多实例安装并配置主从复制
- mvc路由设置参数配置类似于url重写
- python三大神器之一fabric使用
- Cadence关闭StartPage的方法
- Ubuntu 查找命令
- js动画学习（三）
- GUI(JMenuBar+JMenu+JMenuItem)
- 记录一次参加D2前端技术论坛的杭州之行
- Android简易记事本
- PHP全栈学习笔记7
- Android Fragment碎片
- 一段曾经处理datetime的代码
- iOS - 常用的CG结构体
- 【python】logging日志模块写入中文编码错误解决办法
- mysql字符集和字符排序