redis 链表

前言

借鉴了 黄健宏 的 <<Redis 设计与实现>> 一书, 对 redis 源码进行学习

欢迎大家给予意见, 互相沟通学习

概述

redis 的链表结构是双向链表

redis 的链表结构是无环的, head 节点的 prev 与 tail 节点的 next 指向的均为 NULL

多态: 链表节点的值 value 类型是 void *, 也就是可以存储任意类型的值

list 结构定义

定义位置 (src/adlist.h)

list 结构

//双端链表结构

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;

listNode 结构

// 双端链表节点

typedef struct listNode {

    // 前置节点

    struct listNode *prev;

    // 后置节点

    struct listNode *next;

    // 节点的值

    void *value;

} listNode;

listIter 结构

// 双端链表迭代器

typedef struct listIter {

    // 当前迭代到的节点

    listNode *next;

    // 迭代的方向

    int direction;

} listIter;

list api (src/adlist.c)

函数	作用	备注
listCreate	创建新链表	list *listCreate(void)
listRelease	释放链表	void listRelease(list *list)
listAddNodeHead	创建节点, 并添加到链表头部	list listAddNodeHead(list list, void *value)
listAddNodeTail	创建节点, 并添加到链表尾部	list listAddNodeTail(list list, void *value)
listInsertNode	创建节点, 并将其插入到指定节点前面或后面	list listInsertNode(list list, listNode old_node, void value, int after) {
listDelNode	删除节点	void listDelNode(list list, listNode node)
listGetIterator	获取链表迭代器	listIter listGetIterator(list list, int direction)
listReleaseIterator	释放链表迭代器	void listReleaseIterator(listIter *iter)
listRewind	重置迭代器指针, 从头开始	void listRewind(list list, listIter li)
listRewindTail	重置迭代器指针, 从尾开始	void listRewindTail(list list, listIter li)
listNext	获取迭代器当前所指向的节点	listNode listNext(listIter iter)
listDup	复制链表, 返回副本	list listDup(list orig)
listSearchKey	链表中查询值与 key 匹配的节点	listNode listSearchKey(list list, void *key)
listIndex	获取指定索引的节点	listNode listIndex(list list, long index)
listRotate	将表尾节点取出移动到表头	void listRotate(list *list)

redis 链表

redis 链表

前言

概述

list 结构定义

list api (src/adlist.c)

相关文章