Redis源码阅读--adlist（10）
双端链表
adlist.c .h
Redis里的List是双端链表的形式
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;
/* Directions for iterators
*
* 迭代器进行迭代的方向
*/
// 从表头向表尾进行迭代
#define AL_START_HEAD 0
// 从表尾到表头进行迭代
#define AL_START_TAIL 1注意
- 这里的表头和表尾的next都是指向null的所以永远无环
- 链表节点是使用的void*指针来保存节点值的 所以链表可以保存各种不同类型的值
int *a;
void *p
p=a;
#include
using namespace std;
int main() {int b[] = { 1,2 };
int* a = b;
void *c;
c = a;
cout << c< 这里你是可以输出c的 c存的就是指针a所村的 也就是 b数组的内存地址，但是你是不能*c 因为没有类型void
API 指定位置插入
/*
* 创建一个包含值 value 的新节点，并将它插入到 old_node 的之前或之后
*
* 如果 after 为 0 ，将新节点插入到 old_node 之前。
* 如果 after 为 1 ，将新节点插入到 old_node 之后。
*
* T = O(1)
*/
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
// 创建新节点
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
// 保存值
node->value = https://www.it610.com/article/value;
// 将新节点添加到给定节点之后
if (after) {
node->prev = old_node;
node->next = old_node->next;
// 给定节点是原表尾节点
if (list->tail == old_node) {
list->tail = node;
}
// 将新节点添加到给定节点之前
} else {
node->next = old_node;
node->prev = old_node->prev;
// 给定节点是原表头节点
if (list->head == old_node) {
list->head = node;
}
}// 更新新节点的前置指针
if (node->prev != NULL) {
node->prev->next = node;
}
// 更新新节点的后置指针
if (node->next != NULL) {
node->next->prev = node;
}// 更新链表节点数
list->len++;
return list;
}迭代器
/*
* 为给定链表创建一个迭代器，
* 之后每次对这个迭代器调用 listNext 都返回被迭代到的链表节点
*
* direction 参数决定了迭代器的迭代方向：
*AL_START_HEAD ：从表头向表尾迭代
*AL_START_TAIL ：从表尾想表头迭代
*
* T = O(1)
*/
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;
}【Redis源码阅读--adlist（10）】查找
/*
* 查找链表 list 中值和 key 匹配的节点。
*
* 对比操作由链表的 match 函数负责进行，
* 如果没有设置 match 函数，
* 那么直接通过对比值的指针来决定是否匹配。
*
* 如果匹配成功，那么第一个匹配的节点会被返回。
* 如果没有匹配任何节点，那么返回 NULL 。
*
* T = O(N)
*/
listNode *listSearchKey(list *list, void *key)
{
listIter *iter;
listNode *node;
// 迭代整个链表
iter = listGetIterator(list, AL_START_HEAD);
while((node = listNext(iter)) != NULL) {// 对比
if (list->match) {
if (list->match(node->value, key)) {
listReleaseIterator(iter);
// 找到
return node;
}
} else {
if (key == node->value) {
listReleaseIterator(iter);
// 找到
return node;
}
}
}listReleaseIterator(iter);
// 未找到
return NULL;
}推荐阅读
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 上班后阅读开始变成一件奢侈的事
- 历史教学书籍
- 绘本讲师训练营【24期】14/21阅读原创《小黑鱼》
- 21天|21天|M&M《见识》04
- 绘本讲师训练营7期9/21阅读原创《蜗牛屋|绘本讲师训练营7期9/21阅读原创《蜗牛屋 》
- 桂妃研读社|桂妃研读社|D124|如何有效阅读一本书 Day1
- Android事件传递源码分析
- 4.23世界阅读日，樊登读书狂欢放送，听书中成长