Redis5.0源码 - 数据结构 - 链表

 

Redis使用的C语言并没有内置链表这种数据结构,所以Redis构建了自己的链表实现。

设计

  • 相关文件:adlist.hadlist.c

跟Redis链表实现相关的数据结构如下:


/* 链表节点结构 */
typedef struct listNode {
    struct listNode *prev;  // 前置节点
    struct listNode *next;  // 后置节点
    void *value;            // 节点的值
} listNode;

/* 链表遍历所使用的Iterator结构 */
typedef struct listIter {
    listNode *next;
    int direction;  // 遍历方向:0 - 从头开始,1 - 从尾开始
} 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;

Redis的链表结构如下图所示

Redis的链表结构

Redis链表的特点

  1. 双向无环链表:首先,很显然Redis的链表是一个双向无环链表,获取当前节点的前驱节点和后驱节点的时间复杂度为O(1);
  2. 有表头表尾指针:获取表头节点和表尾节点的时间复杂度为O(1);
  3. 链表有len属性:获取链表长度的时间复杂度为O(1);
  4. 多态:用void*指针来保存节点内容,并提供节点处理函数dup,free,match。可以用来存储不同类型。

常用API

函数 作用
listLength 返回链表长度
listFirst 返回表头
listLast 返回表尾
listPrevNode 返回当前节点的前置节点
listNextNode 返回当前节点的后置节点
listNodeValue 返回当前节点的值
listSetDupMethod 设置dup函数
listSetFreeMethod 设置free函数
listSetMatchMethod 设置match函数
listGetDupMethod(l) 获取dup函数
listGetFree(l) 获取free函数
listGetMatchMethod(l) 获取match函数
listCreate 创建一个不包含任何节点的新链表
listRelease 释放整个链表结构
listEmpty 删除链表的所有节点,使链表成为空链表,链表依旧存在
listAddNodeHead 在链表头部插入节点
listAddNodeTail 在链表尾部插入节点
listInsertNode 在指定节点前或后插入新节点,前后取决于参数after
listDelNode 删除指定节点
listGetIterator 获取链表的迭代器,根据参数direction确定从头还是从尾开始
listNext 根据迭代器返回下一个节点
listReleaseIterator 释放迭代对象占用的内存
listDup 复制整个链表
listSearchKey 根据给定key查找节点
listIndex 根据index索引返回链表节点(head为索引0)
listRewind 创建一个迭代器(迭代器由函数外部传入),从头开始
listRewindTail 创建一个迭代器(迭代器由函数外部传入),从尾开始
listRotate 将链表的表尾节点弹出,插入到链表的表头,成为新的表头
listJoin 将一个链表o追加到另一个链表l后,并清空o链表