Redis-链表

链表是一种基本的数据结构,它是由一系列的节点组成,每个节点上都包括有两部分数据:一个是存储数据元素的数据域,一个是存储下一个节点地址的指针域。新增节点时,可以做到O(1)的复杂度。链表一般分为:单向链表、双向链表、循环链表。Redis 的链表,属于双向链表。

链表中节点结构体在文件 src/adlist.h 如下:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

其中 prev 指向当前节点的上一个节点,next 指向当前节点的下一个节点;value 用来存储当前节点的数据,其中 prevnext 共同组成了链表的指针域,value 则是它的数据域,因为是 void *,所以可以在节点中存储任意的数据类型。

多个 listNode 通过 prevnext 就可以组成一个双向链表。但是 Redis 还是决定用一个结构体来管理链表。这是它的结构体:

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;

headtaillen 就不多做介绍了,dupfreematch 主要是实现多态链表的函数,因为 listNodevalue 可以存储任意类型的数据,在复制、释放或者比较时,对于不同的类型,需要有不同的操作,所以,在生成链表时,需要对应的set每种类型的操作(复制、释放和对比)API。
src/adlist.h 64行开始,有6个宏定义的方法,作为 settergetter

#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)

对于链表结构,获取前一个节点和后一个节点的复杂度都是O(1),因为有 len 属性,所以获取链表长度复杂度也是O(1)。在网上找了些文章,在 list 的实现,主要就用到了链表,其实可以想到,因为 list 本身就是一个链表的结构。

aslist.h 文件中还有一个结构体

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

这个是 list 的迭代器,next 指针指向下个节点,direction 是定义迭代的方向,AL_START_HEADAL_START_TAIL 分别对应从头部 -> 尾部的方向、尾部 -> 头部的方向。相关的方法有:

listIter *listGetIterator(list *list, int direction)    // 初始化一个 链表迭代器

listNode *listNext(listIter *iter)  // 迭代器 next 方法

void listReleaseIterator(listIter *iter);   // 迭代器释放

void listRewind(list *list, listIter *li);  // 迭代器恢复指针至表头位置

void listRewindTail(list *list, listIter *li);  // 迭代器恢复指针至表尾位置
如果文章对您的工作有帮助的话,不如请我喝杯咖啡吧,您的支持是我继续写下去的动力。
8090Lambert WeChat Pay

WeChat Pay

8090Lambert Alipay

Alipay

分享到: