Redis的设计和实现笔记-第三章 链表
Redis的链表
因为C语言并没有内置的链表数据结构，所以Redis自己实现了链表。链表是列表数据结构的底层实现对象。Redis除了链表键外，发布与订阅，慢查询，监视器等功能也用到链表。Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。
链表的定义
typedef struct listNode {
// 前置节点
struct listNode * prev;
// 后置节点
struct listNode * next;
// 节点的值
void * value;
}listNode;
同时定义了list结构来方便操作链表
typedef struct list {
// 表头节点
listNode * head;
// 表尾节点
listNode * tail;
// 链表所包含的节点数量
unsigned long len;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr,void *key);
} list;
通过list可以方便的操作一个链表的头尾指针，获取链表长度。dup、free和match成员则是用于实现多态链表所需的类型特定函数。
- dup函数用于复制链表节点所保存的值。
- free函数用于释放链表节点所保存的值
- match函数用于对比链表节点所保存的值和另一个输入值是否相等。
Redis链表的特性
- 双向链表。通过prev和next指针可以方便的访问前置和后置节点。
- 无环。头节点和尾节点都指向null，对链表的访问以null为终点。
- 通过头节点和尾节点指针，可以直接访问头尾节点。
- 通过len属性可以直接过去到链表长度。
- 多态。通过dup和free和match三个指针函数，可以实现操作不同的数据类型。 Ps：但是最起码在一个list内的数据类型应该是一致的。从代码来看应该是不支持在一个list内使用不同的数据类型的。