redis数据结构源码分析——string

前面的文章大体讲解了redis的几种数据类型，针对设计表巧妙的数据类型，后续会出几篇文章单独讲解下，那么本篇文章针对string的源码进行讲解。

字符串的三种编码：

int：整型
redis数据结构源码分析——string
raw：普通字符串

#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* No longer used: old hash encoding. */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */

可以看到，这其中，int，embstr，raw都属于字符串类型。
在object类中可以看到，如果长度小于44字节，则按embstr方式编码，否则按raw方式编码

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

sds结构

那么我们都知道，string类型低层用的是sds来存储的，以下为sds的类型。

struct __attribute__ ((__packed__)) sdshdr5 {
    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 */
    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：柔性数组，存放数据用的
free=alloc-len
这里可以看到，这几种类型的内部属性其实都是一样的，唯一区别在于len和alloc所占的字节数。
以sdshdr16为例，我们看下大致结构图：

sds的设计思想和优势

1、在创建的时候返回buf指针，从外界可以直接访问sds的数据
2、可以通过len、alloc做到空间预留，可以快速取值，能达到O（1）的时间复杂度
3、根据不同的长度创建不同的sds，节省空间
4、二进制安全，可以存储二进制数据（在C中，一般字符串都是以“\0”结尾，作为C没办法存储二进制数据，但sds还可以通过len截串，找到数据。）
5、自动重新分配内存（sdsMakeRoomFor中体现），能杜绝缓冲区溢出

sds API解析

那么了解了sds结构后，我们来大致看一下sds的API

sdsnewlen（创建字符串）

首先从字符串的创建入手
代码较长，提取了重点说下，大致流程如下：
1、根据不同的长度选择不同的sds类型
2、如果是type5并且初始长度为0，强制转化成type8
3、计算不同type需要的长度，根据长度申请空间
4、根据不同类型给sdshdr属性赋初值
5、返回sds（sds.buf）

sdsfree（释放字符串）

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

大致流程：
1、通过对s的偏移，计算出sds结构体的首地址
2、调用s_free释放内存
这里的第一步讲解下，也就是s_free后的括号里的内容。首先我们的入参s，是上文所说的sds中的buf[]，因此，我们释放的时候，要找到首地址，才能做释放操作。其中，（char*）s是s的位置，而sdsHdrSize（s[-1]）头的位置，这里为什么是减呢，因为s的位置在flags之后，要找到首地址，就要向左移动，所以是减。

sdscatlen（拼接字符串）

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);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

大致流程：
1、调用sdsMakeRoomFor（这是个扩容方法，如果不需要扩容就直接返回，需要扩容就返回扩容后的字符串）
2、判断入参中的sds是否为空，为空则返回
3、调用memcpy（字符串拼接）
4、加上结束符“\0”
这里的sdsMakeRoomFor比较重要，单独说下：

sdsMakeRoomFor（SDS扩容）

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        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 operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        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 */
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        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);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;

大致流程：
1、获取当前可用空间长度avail，若大于等于新增长度addlen，说明无需扩容，直接返回
2、若avail小于addlen，s的长度加上addlen小于1M（代码中的SDS_MAX_PREALLOC就是1M），那么按新长度的2倍扩容
3、若avail小于addlen，s的长度加上addlen大于1M，那么按新长度加1M
4、根据新长度选择sds类型，若sds类型和原类型相同，则调用s_realloc_usable，扩大柔性数组
5、如果sds类型和原类型不同，则调用s_malloc_usable，重新申请内存，把原buf内容移动到新位置
6、对新串的属性进行赋值，返回。