透过Redis源码探究字符串的实现

sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh; //指向SDS结构体的指针
    sds s; //sds类型变量，即char*字符数组
    char type = sdsReqType(initlen); //根据数据大小获取sds header 类型
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); // 根据类型获取sds header大小
    unsigned char *fp; /* flags pointer. */

    assert(hdrlen+initlen+1 > initlen); /* Catch size_t overflow */
    sh = s_malloc(hdrlen+initlen+1); //新建SDS结构，并分配内存空间，这里加1是因为需要在最后加上\0
    ...
    return s;
}

struct __attribute__ ((__packed__)) sdshdr8 { // 占用 3 byte
    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 { // 占用 5 byte
    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 { // 占用 9 byte
    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 { // 占用 17 byte
    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[];
};

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5) // 小于 32
        return SDS_TYPE_5;
    if (string_size < 1<<8) // 小于 256
        return SDS_TYPE_8;
    if (string_size < 1<<16) // 小于 65,536
        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
}

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

sds sdsnewlen(const void *init, size_t initlen) {
	...
    sh = s_malloc(hdrlen+initlen+1); // 1.申请内存，这里长度加1是为了在最后面存放一个 \0
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);// 2.将内存的值都设置为0
    s = (char*)sh+hdrlen; 				//3.将s指针指向数据起始位置
    fp = ((unsigned char*)s)-1; 		//4.将fp指针指向sds header的flags字段
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        } 
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s); //5.构造sds结构体header
            sh->len = initlen; // 初始化 header len字段
            sh->alloc = initlen; // 初始化 header alloc字段
            *fp = type; // 初始化 header flag字段
            break;
        }
        ...
    }
    ...
    return s;
}

sds sdsnewlen(const void *init, size_t initlen) {
    ...
    if (initlen && init)  
        memcpy(s, init, initlen); //将要传入的字符串拷贝给sds变量s
    s[initlen] = '\0'; //变量s末尾增加\0，表示字符串结束
    return s;
}

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s); // 获取字符串 len 大小
    //根据要追加的长度len和目标字符串s的现有长度，判断是否要增加新的空间
    //返回的还是字符串起始内存地址
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    // 将新追加的字符串拷贝到末尾
    memcpy(s+curlen, t, len);
    // 重新设置字符串长度
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s); //这里是用 alloc-len,表示可用资源
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    if (avail >= addlen) return s; // 如果有空间剩余，那么直接返回

    len = sdslen(s); // 获取字符串 len 长度
    sh = (char*)s-sdsHdrSize(oldtype); //获取到header的指针
    newlen = (len+addlen); // 新的内存空间
    if (newlen < SDS_MAX_PREALLOC) //如果小于 1m， 那么存储空间直接翻倍
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC; //超过了1m，那么只会多增加1m空间
    ...
    return s;
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    ...

    type = sdsReqType(newlen); // 根据新的空间占用计算 sds 类型 

    hdrlen = sdsHdrSize(type); // header 长度
    if (oldtype==type) { // 和原来header一样，那么可以复用原来的空间
        newsh = s_realloc(sh, hdrlen+newlen+1); // 申请一块内存，并追加大小
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else { 
        //如果header 类型变了，表示内存头变了，那么需要重新申请内存
        //因为如果使用s_realloc只会向后追加内存
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh); // 释放掉原内存
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);//重新设置alloc字段
    return s;
}