sds

sds结构

数据结构

这里比较有意思的是GNU C的零长度数组   
sizeof(char buf[0]) == 0
关于这篇内容的C语言技巧改日写一篇文章阐述

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};   

len：字符串长度
alloc：可用容量
flags：数据类型
buf：字符数据

可以看到，内容相同的数据结构，因为类型的原因按字长定义了四种。   
redis存储的时候选最小的可用的结构去描述字符串，在避免内存消耗方面做到了极致。

宏解析

#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)   

flags值最大为4，占3位，所以SDS_TYPE_BITS为3，SDS_TYPE_MASK为7。   
SDS_HDR就是获得一个类型的基地址，同时做了强制类型转换，这里所谓的基地址就是结构体的地址。 
SDS_HDR_VAR就是定义了一个具体类型的指针。   
可以看到redis作者通过宏来动态管理字符串的类型。这些trick玩的比较好，有可能是我玩单片机的时候接触不到这么高级的写法。

函数解析

因为传入的sds都是真正存储的地方，而函数中都会先获取到具体类型才会做逻辑。   

unsigned char flags = s[-1];   
因为声明结构体时已经取消了优化字节对齐，所以这些结构体都是程序都是连续存储的   
上述操作就是拿到了结构体的flags成员,这里的trick就是[]的玩法，其实就是base_addr+offset   

sdslen

typedef char *sds;

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}
//就是获取到真正类型后直接取出对应的成员

static inline size_t sdsavail(const sds s);
static inline void sdssetlen(sds s, size_t newlen);
static inline void sdsinclen(sds s, size_t inc);
static inline size_t sdsalloc(const sds s);
static inline void sdssetalloc(sds s, size_t newlen);
//上述几个函数都是对结构体成员的获取和更新    

//其实就是在算法前多了获取类型的操作

最基本的创建函数

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    
    char type = sdsReqType(initlen);        //根据长度觉得使用哪种sdshdr
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;      //源码中提到不会使用SDS_TYPE_5，所以特殊处理一下
    int hdrlen = sdsHdrSize(type);          //获取当前sdshdr类型的大小
    unsigned char *fp;                      // flags pointer

    sh = s_malloc(hdrlen+initlen+1);        //申请需要的内存，多的1个字节用于存放'\0'
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
        
    if (sh == NULL) return NULL;            //没有申请到足够内存则退出
    s = (char*)sh+hdrlen;                   //得到柔性数组的地址
    fp = ((unsigned char*)s)-1;             //拿到flags的地址
    
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);               //根据现在的类型，去初始化sdshdr的成员信息，不包含柔性数组
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    
    if (initlen && init)
        memcpy(s, init, initlen);           //将数组拷贝到柔性数组当中
    s[initlen] = '\0';
    return s;
}

最基本的追加

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);      //就是获取sdshdr中的len属性

    s = sdsMakeRoomFor(s,len);      //扩容
    if (s == NULL) return NULL;     //出错则返回
    memcpy(s+curlen, t, len);       //将需要添加的字符串拷贝到目的字符串尾部
    sdssetlen(s, curlen+len);       //设置sdshdr的len属性
    s[curlen+len] = '\0';           
    return s;
}

扩容机制

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);             //获取目的字符串当中的可用空间
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    if (avail >= addlen) return s;          //如果可用空间足够则什么都不做，直接返回

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);                  //获取追加后的长度
    if (newlen < SDS_MAX_PREALLOC)          //SDS_MAX_PREALLOC宏是1M内存的大小，如果小于1M，则在当前长度的基础上翻倍
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;         //如果追加后的长度超过1M，则长度追加1M个字节

    type = sdsReqType(newlen);              //根据新的长度判断对应的sdshdr类型

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);              //获取新类型的sdshdr大小
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);     //如果新旧类型一直，则在原来的地址上重新安装长度分配空间
        if (newsh == NULL) return NULL;             //分配失败则返回
        s = (char*)newsh+hdrlen;                    //获得柔性数组的地址
    } else {
        newsh = s_malloc(hdrlen+newlen+1);          //新的类型发送变化，sdshdr不一致，所以重新分配新的内存
        if (newsh == NULL) return NULL;             //分配失败则返回
        memcpy((char*)newsh+hdrlen, s, len+1);      
        s_free(sh);                                 //释放原来的sdshdr空间
        s = (char*)newsh+hdrlen;                    //获得柔性数组的地址
        s[-1] = type;
        sdssetlen(s, len);                          //设置新sdshdr的len属性
    }
    sdssetalloc(s, newlen);                         //设置新sdshdr的alloc属性
    return s;
}