Redis实现原理(二)链表
目录一、链表在Redis中的作用二、链表实现1. 结构1.1 链表节点结构1.2 链表结构2 链表和链表节点的API一、链表在Redis中的作用链表键发布与订阅慢查询监视器保存客户端状态信息构建客户端输出缓冲区...二、链表实现1. 结构1.1 链表节点结构adlist.h/listNode,如下:typedef stru...
·
目录
一、链表在Redis中的作用
- 链表键
- 发布与订阅
- 慢查询
- 监视器
- 保存客户端状态信息
- 构建客户端输出缓冲区
- ...
二、链表实现
1. 结构
1.1 链表节点结构
adlist.h/listNode,如下:
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
struct *value;
};
1.2 链表结构
双端链表结构如下图:
链表结构源码如下:
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 链表所包含的节点数量
unsigned long len;
// 节点复制函数
void *(*dup)(void *prt);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
}
特性:
- 双端
- 无环
- 带表头指针和表尾指针
- 带链表长度计数器
- 多态
2 链表和链表节点的API
函数 | 作用 | 时间复杂度 |
listSetDupMethod | 将给定的函数设置为链表的节点值复制函数 | O(1) |
listGetDupMethod | 返回链表当前正在使用的节点值复制函数 | O(1) |
listSetFreeMethod | 将给定的函数设置为链表的节点值释放函数 | O(1) |
listGetFree | 返回链表当前正在使用的节点值释放函数 | O(1) |
listSetMatchMethod | 将给定的函数设置为链表的节点值对比函数 | O(1) |
listGetMatchMethod | 返回链表当前正在使用的节点值对比函数 | O(1) |
listLength | 返回链表的长度 | O(1) |
listFirst | 返回链表的表头节点 | O(1) |
listLast | 返回链表的表尾节点 | O(1) |
listPrevNode | 返回给点节点的前置节点 | O(1) |
listNextNode | 返回给点节点的后置节点 | O(1) |
listNodeValue | 返回给定节点目前正在保存的值 | O(1) |
liistCreate | 创建一个不包含任何节点的新链表 | O(1) |
listAddNodeHead | 将一个包含给定值的新节点添加到给定链表的表头 | O(1) |
listAddNodeTail | 将一个包含给定值的新节点添加到给定链表的表尾 | O(1) |
listInsertNode | 将一个包含给定值的新节点添加到给定节点的之前或者之后 | O(1) |
listSearchKey | 查找并返回链表中包含给定值的节点 | O(N) |
listIndex | 返回链表在给定索引上的节点 | O(N) |
listDelNode | 从链表中删除给定节点 | O(N) |
listRotate | 将链表的表尾节点弹出,然后将被弹出的节点插入到链表的表头,成为新的表头节点 | O(1) |
listDup | 复制一个给定链表的副本 | O(N) |
listRelease | 释放给定链表,以及链表中的所有节点 | O(N) |
更多推荐
已为社区贡献2条内容
所有评论(0)