Redis源码学习基本数据结构之链表

作者: lixin_karl | 来源:发表于2019-04-02 17:46 被阅读0次

Redis双端链表
Redis源码学习基本数据结构之链表
redis-数据结构-链表
redis基本数据结构
数据结构与算法之链表(三)单链表的常用操作
redis双向链表实现（3）
iOS 数据结构之链表
总结
Redis' lists
Redis入门--数据结构

介绍

双端链表作为一种通用的数据结构，在 Redis 内部使用得非常多，它既是 Redis 列表结构的底层实现之一，还被大量 Redis 模块所使用，用于构建 Redis 的其他功能。关联源码adlist.h/adlist.c

结构

//链表节点
typedef struct listNode {
    struct listNode *prev;//上一个节点
    struct listNode *next;//下一个节点
    void *value;//值
} listNode;

//链表的迭代器
typedef struct listIter {
    listNode *next;//下一个节点
    int direction;//迭代方向(正向迭代还是反向迭代)
} listIter;

//链表
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;

宏定义的函数

#define listLength(l) ((l)->len) //返回链表长度
#define listFirst(l) ((l)->head)//返回链表头结点
#define listLast(l) ((l)->tail)//返回链表尾结点
#define listPrevNode(n) ((n)->prev)//返回结点前一个结点
#define listNextNode(n) ((n)->next)//返回结点下一个节点
#define listNodeValue(n) ((n)->value)//返回结点数据

#define listSetDupMethod(l,m) ((l)->dup = (m))//设置链表复制函数
#define listSetFreeMethod(l,m) ((l)->free = (m))//设置链表释放内存函数
#define listSetMatchMethod(l,m) ((l)->match = (m))//设置链表结点值得匹配函数

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

函数

list *listCreate(void);//创建一个双向链表
void listRelease(list *list);//释放双向链表内存
void listEmpty(list *list);//释放链表的所有元素的内存
list *listAddNodeHead(list *list, void *value);//头部插入一个元素
list *listAddNodeTail(list *list, void *value);//尾部增加一个元素
list *listInsertNode(list *list, listNode *old_node, void *value, int after);//old_node之前或者之后插入value元素
void listDelNode(list *list, listNode *node);//删除一个节点
listIter *listGetIterator(list *list, int direction);//返回list的迭代器
listNode *listNext(listIter *iter);//list下一个节点
void listReleaseIterator(listIter *iter);//释放迭代器内存
list *listDup(list *orig);//复制链表
listNode *listSearchKey(list *list, void *key);//寻找key与链表中数据一样的或者想匹配的节点
listNode *listIndex(list *list, long index);//找到第index个节点 0表示head  -1表示tail
void listRewind(list *list, listIter *li);//创建一个从head开始的正向链表迭代器
void listRewindTail(list *list, listIter *li);//创建一个从tail开始的正向链表迭代器
void listRotate(list *list);//将尾部节点移除插入到头部
void listJoin(list *l, list *o);//将o拼接到o上去