Redis 源码解析 - Redis 动态字符串与链表

这篇文章只简单介绍两个数据结构的基础实现,函数部分实在是没有什么可说的,对于这两种结构熟悉的朋友可直接观看后述章节.

动态字符串

C语言中没有带有动态字符串的标准库,但是这种数据结构在很多情况下还是比较常用的,所以Redis中实现了简单的动态字符串.这个可以说是整个Redis的构建中最为常用的一种数据结构了,不但可以用作字典的键,还可以用作字典的值,甚至可以用作缓冲区.

基本结构如下:

struct sdshdr {
   
      
    
    // buf 中已占用空间的长度 使用len来判断可以保证字节数组存储的对象二进制安全 即不以'\0'来判断结尾
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

这其中我们可以看到一个很重要的点,就是动态字符串并不像一般的C字符串一样使用’\0’结尾来记录结尾(虽然结尾还是’’\0),而是使用结构体中加上一个成员来判断长度.这样不但在进行长度判断的时候可以O(1)完成,而且保证动态字符串是二进制安全的.

动态字符串相比于普通C系字符串有以下好处:

1、二进制安全(可存储汉字,音频,图片等).；
2、不会有使用C系标准库的字符串函数时出现的缓冲区溢出问题.；
3、兼容部分标准库的字符串函数.；

说实话,在动态字符串中其实没什么好说的,所有的API都非常简单,在sds.h/sds.c中.有兴趣的朋友可以挑几个函数看看实现.

链表

链表也是一个在Redis中使用十分广泛的一个数据结构,它可以做的事情实在是太多了:

1、五大存储类型之一.；
2、存储发布订阅中客户端信息.；
3、集群中故障转移中存储判断某个节点已下线的信息.；
4、回复缓冲区.；
5、事务中服务器存储命令.；
6、 …；

所以这是一个非常重要的数据结构,但它同时也是比较简单的.

listNode是每个节点的数据,带着两个指针的同时有一个void指针,指向真实存储的值,那么如何知道其信息呢,一般在使用链表的时候我们很清楚这个链表的作用是什么,也不会在其中存储两个类型的数据,所以在使用的时候一个强制类型转换就可以了.

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;

一个链表的结构基本就是这样:

我们可以看到在就够提中还有几个函数指针,它们的功能分别是复制,释放和比较,因为值的默认存储是void,与其在后面使用时进行强制类型转换倒不如初始化的时候先注册好,减少使用的困难程度.

当然有这种结构的话迭代器也是必不可少的,Redis链表中也自带迭代器,但它比起SCAN中的游标可要简单多了,我们来看看其实现吧:

typedef struct listIter {
   
     

    // 当前迭代到的节点
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

通过记录迭代方向,我们可以很方便的进行两个方向的迭代.

函数同样不想说太多,都是C语言基础,这里就不费口舌了,大家把重点放在后面系列的文章,那些才是阐明Redis的重点所在,事实上这篇文章就是为了能使整个基础结构部分能够有头有尾而存在的,是我24篇里面写的最后一篇文章。

01、Redis 源码解析 - Redis 动态字符串与链表

动态字符串

链表