redis 5.0.7 源码阅读——双向链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了redis 5.0.7 源码阅读——双向链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8194字，纯文字阅读大概需要12分钟。
内容图文
redis中动态字符串sds相关的文件为：adlist.h与adlist.c
一、数据结构
redis里定义的双向链表，与普通双向链表大致相同
单个节点：
1 typedef struct listNode {
2 struct listNode *prev;
3 struct listNode *next;
4 void *value;
5 } listNode;
链表：
1 typedef struct list {
2 listNode *head;
3 listNode *tail;
4 void *(*dup)(void *ptr);
5 void (*free)(void *ptr);
6 int (*match)(void *ptr, void *key);
7 unsigned long len;
8 } list;
链表以函数指针的方式，实现了复制、销毁与比较的方法的多态。
迭代器：
1 typedef struct listIter {
2 listNode *next;
3 int direction;
4 } listIter;
迭代器中有个成员变量direction，用于表示当前遍历的方向。
大致结构：
1 /* 2 +-------------------+ +----------------> +--------------+ <-------+ 3 |listNode *head |--------+ |listNode *prev|-->NULL | 4 +-------------------+ +--------------+ | 5 |listNode *tail |--------+ |listNode *next|----+ | 6 +-------------------+ | +--------------+ | | 7 |void *(*dup)(...) | | |void *value | | | 8 +-------------------+ | +--------------+ | | 9 |void (*free)(...) | | | | 10 +-------------------+ | | | 11 |int (*match)(...) | | | | 12 +-------------------+ +----------------> +--------------+ <--+ | 13 |unsigned long len | |listNode *prev|---------+ 14 +-------------------+ +--------------+ 15 |listNode *next|-->NULL 16 +--------------+ 17 |void *value | 18 +--------------+ 19 */
二、创建
redis中创建一个初始双向链表比较简单，只要分配好内存，并给成员变量赋初值就可以了
1 list *listCreate(void)
2 {
3 struct list *list;
4
5 if ((list = zmalloc(sizeof(*list))) == NULL)
6 return NULL;
7 list->head = list->tail = NULL;
8 list->len = 0;
9 list->dup = NULL;
10 list->free = NULL;
11 list->match = NULL;
12 return list;
13 }
redis中提供了头插法、尾插法以及指定位置插入节点三种方式向链表中添加节点，与普通双向链表无异，此处不做详细叙述。
三、销毁
因链表中每个节点的value可能指向堆空间，故不能直接把list结构体free，这样会造成内存泄露。需要先将每个节点的value释放，才可以free结构体
清空所有节点：
1 void listEmpty(list *list)
2 {
3 unsigned long len;
4 listNode *current, *next;
5
6 current = list->head;
7 len = list->len;
8 while(len--) {
9 next = current->next;
10 //若指定了销毁的函数，则使用指定的函数进行销毁value
11 if (list->free) list->free(current->value);
12 zfree(current);
13 current = next;
14 }
15 list->head = list->tail = NULL;
16 list->len = 0;
17 }
销毁链表：
1 void listRelease(list *list)
2 {
3 listEmpty(list);
4 zfree(list);
5 }
同样，redis的链表提供了与普通链表相同的删除单个节点的操作，此处也不做叙述。
四、迭代器操作
redis中提供了获取迭代器的接口
1 listIter *listGetIterator(list *list, int direction)
2 {
3 listIter *iter;
4
5 if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
6 if (direction == AL_START_HEAD)
7 iter->next = list->head;
8 else
9 iter->next = list->tail;
10 iter->direction = direction;
11 return iter;
12 }
以AL_START_HEAD为例，生成好的迭代器结构如下：
1 /* 2 +-------------------+ +---> +--------------+ <-------+----+ 3 |listNode *head |----+ |listNode *prev|-->NULL | | 4 +-------------------+ +--------------+ | | +--------------+ 5 |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next| 6 +-------------------+ | +--------------+ | | +--------------+ 7 |void *(*dup)(...) | | |void *value | | | |int direction | 8 +-------------------+ | +--------------+ | | +--------------+ 9 |void (*free)(...) | | | | 10 +-------------------+ | | | 11 |int (*match)(...) | | | | 12 +-------------------+ +---> +--------------+ <--+ | 13 |unsigned long len | |listNode *prev|---------+ 14 +-------------------+ +--------------+ 15 |listNode *next|-->NULL 16 +--------------+ 17 |void *value | 18 +--------------+ 19 */
迭代器的next方法：
1 listNode *listNext(listIter *iter)
2 {
3 listNode *current = iter->next;
4
5 if (current != NULL) {
6 if (iter->direction == AL_START_HEAD)
7 iter->next = current->next;
8 else
9 iter->next = current->prev;
10 }
11 return current;
12 }
调用一次之后的结构：
1 /* 2 +-------------------+ +---> +--------------+ <-------+ 3 |listNode *head |----+ |listNode *prev|-->NULL | 4 +-------------------+ +--------------+ | +--------------+ 5 |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next| 6 +-------------------+ | +--------------+ | | | +--------------+ 7 |void *(*dup)(...) | | |void *value | | | | |int direction | 8 +-------------------+ | +--------------+ | | | +--------------+ 9 |void (*free)(...) | | | | | 10 +-------------------+ | | | | 11 |int (*match)(...) | | | | | 12 +-------------------+ +---> +--------------+ <--+----|----+ 13 |unsigned long len | |listNode *prev|---------+ 14 +-------------------+ +--------------+ 15 |listNode *next|-->NULL 16 +--------------+ 17 |void *value | 18 +--------------+ 19 */
再次调用：
1 /* 2 +-------------------+ +---> +--------------+ <-------+ 3 |listNode *head |----+ |listNode *prev|-->NULL | 4 +-------------------+ +--------------+ | +--------------+ 5 |listNode *tail |----+ |listNode *next|----+ | +--|listNode *next| 6 +-------------------+ | +--------------+ | | | +--------------+ 7 |void *(*dup)(...) | | |void *value | | | | |int direction | 8 +-------------------+ | +--------------+ | | | +--------------+ 9 |void (*free)(...) | | | | | 10 +-------------------+ | | | | 11 |int (*match)(...) | | | | | 12 +-------------------+ +---> +--------------+ <--+ | +-->NULL 13 |unsigned long len | |listNode *prev|---------+ 14 +-------------------+ +--------------+ 15 |listNode *next|-->NULL 16 +--------------+ 17 |void *value | 18 +--------------+ 19 */
调用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
内容总结
以上是互联网集市为您收集整理的redis 5.0.7 源码阅读——双向链表全部内容，希望文章能够帮你解决redis 5.0.7 源码阅读——双向链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。