sds.c

Redis的字符串，没有采用C原生的字符串，而是使用了sds。
SDS，Simple Dynamic Strings，表示简单动态字符串。

Redis对于内存的时候是极度简约的，根据不同字符串长度采用不同的类型。

首先，在sds.h存在着一个sds指针引用。

typedef char *sds;

1. 创建SDS

//用来创建新的Redis字符串sds，返回sds字符指针，
//在sds.h中存在着一个sds字符指针 typedef char *sds;
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    //根据sds初始长度获取类型
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    //根据类型获取hdr长度
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    //分配内存，包含预分配的内存
    sh = s_malloc(hdrlen+initlen+1);
    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是一个指针引用，标记位
    fp = ((unsigned char*)s)-1;
    //根据len判断type，根据type选择合适的header
    switch(type) {
        case SDS_TYPE_5: {
            //sdshdr5，initlen左移3位，再做或运算
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            //sdshdr8
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            //sdshdr16
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            //sdshdr32
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            //sdshdr64
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    //以\0结尾
    s[initlen] = '\0';
    return s;
}

在代码中发现通过initlen获取type，再通过type获取hdrlen，再根据以上信息给sdshdr赋予初始值及内存空间的分配。

第一部分，根据sds初始长度获取类型

    char type = sdsReqType(initlen);

sdsReqType的实现如下。

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<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
}

根据不同的string_size选择不同的SDS_TYPE_。

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

第二部分，根据type返回选择的hdr的大小。

    int hdrlen = sdsHdrSize(type);

sdsHdrSize的实现如下：

static inline int sdsHdrSize(char type) {
    switch(type&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return sizeof(struct sdshdr5);
        case SDS_TYPE_8:
            return sizeof(struct sdshdr8);
        case SDS_TYPE_16:
            return sizeof(struct sdshdr16);
        case SDS_TYPE_32:
            return sizeof(struct sdshdr32);
        case SDS_TYPE_64:
            return sizeof(struct sdshdr64);
    }
    return 0;
}

通过操作一个int来作&运算，匹配多种SDS_TYPE_。

第三部分，sdshdr的结构。

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    //低3位存储type，高5位存字符串长度
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    //字符串长度
    uint8_t len; /* used */
    //分配的空间大小
    uint8_t alloc; /* excluding the header and null terminator */
    //标记位，低3位存储SDS的type
    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[];
};

包含有sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。
sdshdr5和其它类型的数据结构不太一致。

• flags表示type，sdshdr5的低3位表示type，高5位表示字符串长度。
• buf用来存储真实字符串数据。
• len用来表示字符串长度。
• alloc表示最大的容纳字符串长度。
  +---------------------------------+
  | alloc | len | flags | buf | \0 |
  +---------------------------------+
  2. SDS扩容

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //剩余可用空间，alloc-len 分配的空间 - 字符串长度
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    /* Return ASAP if there is enough space left. */
    //如果剩余可用空间大于要扩大的容量数，则直接返回。
    if (avail >= addlen) return s;
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    //小于1M的时候，2倍扩容
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    //大于1M的时候，每次增加1M
    else
        newlen += SDS_MAX_PREALLOC;
    //根据长度获取类型
    type = sdsReqType(newlen);

    /* 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 operat ion. */
    if (type == SDS _TYPE_5) type = SDS_TYPE_8;
    //根据类型获取header大小
    hdrlen = sdsHdrSize(type);
    //类型不变，则仅仅分配空间
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        //类型变了（header大小变了），需要分配空间且移动数据
        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;
        //修改sdshdr的len参数
        sdssetlen(s, len);
    }
    //修改sdshdr的alloc参数
    sdssetalloc(s, newlen);
    return s;
}

大致策略就是，
如果当前可以容量avail大于需求扩容数addlen，则不扩容返回。
如果当前len小于1M，则每次加倍扩容，以0补齐。
如果当前len大于1M，则每次递增1M，以0补齐。

3. SDS缩容

/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    size_t avail = sdsavail(s);
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if there is no space left. */
    if (avail == 0) return s;

    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    //根据len获取type
    type = sdsReqType(len);
    //根据type获取hdrlen
    hdrlen = sdsHdrSize(type);

    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
    //判断类型是否变了
    if (oldtype==type || type > SDS_TYPE_8) {
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else {
        //类型变了，重新分配内存
        newsh = s_malloc(hdrlen+len+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        //释放原来的内存空间
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        //修改sdshdr的len参数
        sdssetlen(s, len);
    }
    //修改sdshdr的alloc参数
    sdssetalloc(s, len);
    return s;
}

4. SDS长度
老样子，计算type，获取len。

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    //做&运算，计算出type
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            //sdshdr5的len存储在flags的高5位
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            //#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
            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;
}

sdshdr5需要通过移位运算，计算出len，而其它的只需要调用sdshdr结构中的len属性即可。

4. SDS可用长度
老样子，计算type，获取alloc，获取len，做减法。

static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    //做&运算，计算出type
    switch(flags&SDS_TYPE_MASK) {
        //sdshdr5没有预分配机制，返回0
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            //sdshdr8，计算公式：alloc-len 分配的内存 - 已有字符串长度
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}