redis核心原理与实践_字符串

redisObject

sds

代码在sds.h/sds.c 文件中

定义/结构

/**
 * 短字符串1个字节表示，3位表示类型，2的5次方存储长度的大小也就是len（不是表示内容），长度小于等于（2的5次方-1）个字符串
 * 长字符串 2个字节，len占1字节，free占1字节，长度小于等于（2的8次方-1）个字符串，对应sdshdr8
 * 再长字符串 4个字节，len和free各自占2字节，长度小于等于（2的16次方-1）个字符串，对应sdshdr16
 * 更长字符串 8个字节，len和free各自占4字节，长度小于等于（2的32次方-1）个字符串，对应sdshdr32
**/
struct __attribute__ ((__packed__))sdshdr5 {
    unsigned char flags; /* 低3位存储类型, 高5位存储长度 flags占1个字节，其低3位（bit）表示type，高5位（bit）表示长度，能表示的长度区间为0～31*/
    char buf[];/*柔性数组，存放实际内容*/
};
struct __attribute__((__packed__))sdshdr8 {
    uint8_t len; /* 已使用长度，用1字节存储 */
    uint8_t alloc; /* 总长度，用1字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};
struct __attribute__((__packed__))sdshdr16 {
    uint16_t len; /*已使用长度，用2字节存储*/
    uint16_t alloc; /* 总长度，用2字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};
struct __attribute__((__packed__))sdshdr32 {
    uint32_t len; /*已使用长度，用4字节存储*/
    uint32_t alloc; /* 总长度，用4字节存储*/
    unsigned char flags;/* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};
struct __attribute__((__packed__))sdshdr64 {
    uint64_t len; /*已使用长度，用8字节存储*/
    uint64_t alloc; /* 总长度，用8字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};

构建函数

//init字符串内容  initlen字符串长度  tcmalloc内存分配由google用于优化C++多线程就应用而开发
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    //s就是一个字符数组的指针，即结构中的buf。这样设计的好处在于直接对上层提供了字符串内容指针，兼容了部分C函数，且通过偏移能迅速定位到SDS结构体的各处成员变量 。
    sds s;
    //根据字符串长度判断类型
    char type = sdsReqType(initlen);
    //当initlen为0的时候，意味着要申请一个空sds，
    //空字符串大概率之后会append，但sdshdr5不适合用来append，故选择 sdshdr8
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    //查询结构体长度不包括buf  ==> sizeof(len+alloc+flags)
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    //s_trymalloc_usable（）尝试分配内存，如果失败，则返回NULL。 如果非NULL，则将 useable 设置为可用大小。
    //s_malloc_usable（）分配内存或紧急/异常情况。 如果非NULL，则将 usable 设置为可用大小。
    //hdrlen+initlen+1 ==> 结构体长度+字符串长度+'\0'空字符串 
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
         //这里判断是否需要初始化
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)//需要初始化
    //先在一段内存块中填充某个给定的值，sh：起始地址; 0:填充的值; hdrlen+initlen+1: 结构体的长度+字符串的长度+'\0'
        memset(sh, 0, hdrlen+initlen+1);
    //指向sds中字符串的指针 字符串位置=sds起始位置+结构体长度
    s = (char*)sh+hdrlen;
    //指向 sds 的 flags  flags位置=字符串位置-1
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    //如果有指定初始化内容，将它们复制到buf中
    if (initlen && init)
        memcpy(s, init, initlen);//将init字符串的initlen个字节复制到buf
    s[initlen] = '\0';
    return s;
}

扩容

/**
 * 扩大sds字符串末尾的可用空间，以便调用者确保在调用此函数后，最多可以覆盖addlen字符串末尾后的字节，
 * 再加上一个字节表示nul项。注意：这不会更改返回的sds字符串的*length*通过sdslen（），但只有可用的缓冲区空间。*/
// sds的扩容 s:原sds ,addlen:追加字符串长度
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //调用sdsvail获取可用空间大小
    size_t avail = sdsavail(s);
    ////分别记录原始sds的长度，和新分配的sds长度
    size_t len, newlen, reqlen;
    //分别记录新分配sds的type，和原始sds的type
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
     //如果可用空间已经大于addlen，则直接返回s
    if (avail >= addlen) return s;

    //直接获取字符串长度,复杂度为O(1)
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (newlen < SDS_MAX_PREALLOC) //原字符串长度+addlen如果小于1MB，则分配(原字符串长度+addlen)两倍长的缓冲区
        newlen *= 2;
    else //否则分配原字符串长度+addlen+1MB长的缓冲区。
        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. */
    //SDS_TYPE_5 类型不支持扩容操作
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    //重新计算类型
    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */

    //如果和原类型相同直接执行realloc,realloc负责为指定指针重新分配给定大小的空间,尝试在原地址空间重新分配,无法满足要求再重新分配地址空间并进行复制
    //malloc 直接重新申请内存空间,移动sds
    if (oldtype==type) {
        //空间大小为对应sdshdr(sds结构体)的大小+新分配缓冲大小+1（字符串结尾’\0’的空间）
        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 */
        //如果和原类型不相同，也分配空间大小为对应sdshdr的大小+新分配缓冲大小+1大小的空间
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
         //旧buf中的数据拷贝进新的buf
        memcpy((char*)newsh+hdrlen, s, len+1);
        //释放原结构的内存
        s_free(sh);
        s = (char*)newsh+hdrlen;
        //将原结构中的len和flags赋值给新分配的结构，
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    //修改alloc参数为新分配缓冲区大小，返回新分配结构的buf的起始地址
    sdssetalloc(s, usable);
    return s;
}