一、SDS

1、SDS结构体

redis3.2之前：不管buf的字节数有多少，都用 4字节的len来储存长度，对于只存短字符串那么优点浪费空间，比如只存 name，则len=4 则只需要一个字节8位即可表示

struct sdshdr {

    unsigned int len; // buf中已占字节数

    unsigned int free; // buf中剩余字节数

    char buf[]; // 数据空间

};

redis3.2之后：

struct __attribute__ ((__packed__)) sdshdr8 {

    uint8_t len; //已分配字节数

    uint8_t alloc; //剩余字节数

    unsigned char flags; //标识属于那种类型的SDS  低3存类型，高5不使用

    char buf[];

};

//........16、32、64

_attribute_ ((_packed_)) 关键字是为了取消字节对齐

struct test1 {

 char c;

 int i;

};

struct __attribute__ ((__packed__)) test2 {

 char c;

 int i;

};

int main()

{

 cout << "size of test1:" << sizeof(struct test1) << endl; //5

 cout << "size of test2:" << sizeof(struct test2) << endl; //8

}

注意，这些结构都存在一个 char[]内，通过偏移来访问

graph TB
subgraph
header-->buf
end

2、重要函数解析

sdsReqType

确定类型：sdsReqType根据传入的 char[] 长度来缺点应该用哪种类型的 SDS结构体来描述

static inline char sdsReqType(size_t string_size) {

    if (string_size < 1<<5)

        return SDS_TYPE_5;

    if (string_size < 1<<8) //8位 表示长度范围 0-256

        return SDS_TYPE_8;

    if (string_size < 1<<16) //16位

        return SDS_TYPE_16;

#if (LONG_MAX == LLONG_MAX)

    if (string_size < 1ll<<32)

        return SDS_TYPE_32;

    return SDS_TYPE_64;

#else

    return SDS_TYPE_32;

#endif

}

sdsnewlen

根据长度结构化 char数组，创建一个长度为 str本身长度+head长度的数组， sdsnew就是调用这个来创建sds字节数组的

sds sdsnewlen(const void *init, size_t initlen) {

    void *sh; //存放sds header数据的头指针

    sds s; //char* s

    char type = sdsReqType(initlen); //根据str长度 确定SDS header类型

    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;

    int hdrlen = sdsHdrSize(type); //header 长度

    unsigned char *fp; //类型指针

    sh = s_malloc(hdrlen+initlen+1); //分配 str长度+header长度的内存空间

    ...

    memset(sh, 0, hdrlen+initlen+1); //初始化空间

    s = (char*)sh+hdrlen; //移动到header之后的buf首地址位置

    fp = ((unsigned char*)s)-1; //移动到header的尾部 标识sds header类型

    switch(type) {

       ....

        case SDS_TYPE_8: {

//#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

  //sh指向header空间头部位置 s代表buf首地址  下面将sh移动到header的首地址

        SDS_HDR_VAR(8,s); //struct sdshdr8* sh = (void*)(s-sizeof(header))

        sh->len = initlen; //填充数据

        sh->alloc = initlen;

        *fp = type;//类型数据填充

        break;

       }

       ......

    }

    if (initlen && init)

        memcpy(s, init, initlen); //将str数据复制到buf中

    s[initlen] = '\0';

    return s;

}

sdslen、sdsavail

返回使用和未使用的空间。 **根据头部类型转化指针，然后直接 sh->len 和 sh->alloc-sh->len **即可求出

sdscat、sdscatlen、sdsMakeRoomFor

将 t拼接到 s 中，

sds sdscatsds(sds s, const sds t) {

    return sdscatlen(s, t, sdslen(t));

}

sds sdscatlen(sds s, const void *t, size_t len) {

    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len); //保证空间充足

    if (s == NULL) return NULL;

    memcpy(s+curlen, t, len); //直接copy

    sdssetlen(s, curlen+len); //设置新的长度

    s[curlen+len] = '\0';

    return s;

}

sdsMakeRoomFor是为了保证空间充足，如果不充足进行扩容，下面就是newlen的核心代码，会扩容大于需要的长度，防止多次扩容。体现了 预先分配

扩容是一个耗时的操作

    if (avail >= addlen) return s;

    len = sdslen(s);

    sh = (char*)s-sdsHdrSize(oldtype);

    newlen = (len+addlen);

    if (newlen < SDS_MAX_PREALLOC) //#define SDS_MAX_PREALLOC (1024*1024)

        newlen *= 2;

    else

        newlen += SDS_MAX_PREALLOC;

sdstrim

将cset中在s出现的删除，这个函数就体现了 惰性释放 ，不会缩减空间，仅仅改变 len，同时也体现了和 c的兼容性，可以用系统strings函数来操作 sds

sds sdstrim(sds s, const char *cset) {

    char *start, *end, *sp, *ep;

    size_t len;

    sp = start = s;

    ep = end = s+sdslen(s)-1;

    while(sp <= end && strchr(cset, *sp)) sp++;

    while(ep > sp && strchr(cset, *ep)) ep--;

    len = (sp > ep) ? 0 : ((ep-sp)+1);

    if (s != sp) memmove(s, sp, len);

    s[len] = '\0';

    sdssetlen(s,len);

    return s;

}

3、优点

A.获取长度方便

c字符串获取长度需要便利char数组，O(n)，而SDS结构体记录了长度，不需要char数组即可知道长度。

B.防止溢出

char数组不知道还有多少空间空余，可能会在两个字符串拼接的时候溢出，而SDS记录了未使用的空间，可以有效的分配扩容，防止溢出。

C.内存分配方便和使用高效

传统c的char数组，如果空间不足，需要手动扩容，然后复制原数据，截断时，也需要缩减空间，来防止内存泄漏。但是SDS可以进行 空间预分配、惰性释放 等策略来搞效的使用内存。

空间预分配:

预先分配足够的空间，减少扩容次数
惰性释放

因为SDS记录了 free未分配空间字段，所以截断字符串的时候不需要立即复制元素进行缩减，直接增加 free 数值，减少 len即可，后面要增加字符串只增加len，减少free ，覆盖写入即可。（free = alloc-len）

D.兼容C

SDS只是增加了两个字段，其实数据还是存在 char[] buf里面的，所以可以使用 c内置的字符串处理函数来处理 SDS底层字节数组。

typedef char *sds;

所以在处理字符串的API里只是传入了 char* 来处理字符串。空间是否充足都有额外的信息来描述。

二、链表

链表的话可以参考我的 https://www.cnblogs.com/biningooginind/p/12553163.html

基本参照了redis的链表操作。

1、结构体

typedef struct listNode {

    struct listNode *prev;

    struct listNode *next;

    void *value; //void* 指针 可以存放任意类型的数据

} listNode;

2、特点

链表的特点：

删除、插入 O(1)

遍历访问 O(n)

有head和tail指针，将访问最后一个元素复杂度降低到O(1)
带有 len长度，方便知道链表的长度
双链表结构，前后遍历都方便
无环
多态：数据用 void 来指向，可以存放任意类型数据，不用为每个类型都写一个链表*
迭代器模式，链表有一个迭代器，方便遍历节点

typedef struct listIter {

    listNode *next; //下一个节点

    int direction; //遍历方向 forward or backward

} listIter;

巴特西

[redis]SDS和链表