社区首页 >专栏 >sds数据结构分析-redis源码阅读笔记（1）

sds数据结构分析-redis源码阅读笔记（1）

原创

evenleo

修改于 2020-11-18 03:44:42

4851

文章被收录于专栏：C++的沉思C++的沉思

sds

定义

typedef char *sds;

数据结构：

struct sdshdr {

    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

创建对象

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;
    // 根据是否有初始化内容，选择适当的内存分配方式
    // T = O(N)
    if (init) {
        // zmalloc 不初始化所分配的内存
        sh = zmalloc(sizeof(struct sdshdr) + initlen + 1);
    }
    else {
        // zcalloc 将分配的内存全部初始化为 0
        sh = zcalloc(sizeof(struct sdshdr) + initlen + 1);
    }

    // 内存分配失败，返回
    if (sh == NULL) return NULL;
    // 设置初始化长度
    sh->len = initlen;
    // 新 sds 不预留任何空间
    sh->free = 0;
    // 如果有指定初始化内容，将它们复制到 sdshdr 的 buf 中
    // T = O(N)
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    // 以 \0 结尾
    sh->buf[initlen] = '\0';
    // 返回 buf 部分，而不是整个 sdshdr
    return (char*)sh->buf;
}

获取长度

// 获取字符串长度
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s - (sizeof(struct sdshdr)));
    return sh->len;
}
// 获取空闲空间长度
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s - (sizeof(struct sdshdr)));
    return sh->free;
}

追加字符串

sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    // 原有字符串长度
    size_t curlen = sdslen(s);
    // 扩展 sds 空间
    // T = O(N)
    s = sdsMakeRoomFor(s, len);
    // 内存不足？直接返回
    if (s == NULL) return NULL;
    // 复制 t 中的内容到字符串后部
    // T = O(N)
    sh = (void*)(s - (sizeof(struct sdshdr)));
    memcpy(s + curlen, t, len);
    // 更新属性
    sh->len = curlen + len;
    sh->free = sh->free - len;
    // 添加新结尾符号
    s[curlen + len] = '\0';
    // 返回新 sds
    return s;
}

// 对sds空间进行拓展
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    // 获取 s 目前的空余空间长度
    size_t free = sdsavail(s);
    size_t len, newlen;
    // s 目前的空余空间已经足够，无须再进行扩展，直接返回
    if (free >= addlen) return s;
    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (void*)(s - (sizeof(struct sdshdr)));
    // s 最少需要的长度
    newlen = (len + addlen);
    // 根据新长度，为 s 分配新空间所需的大小
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于 SDS_MAX_PREALLOC 
        // 那么为它分配两倍于所需长度的空间
        newlen *= 2;
    else
        // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr) + newlen + 1);
    // 内存不足，分配失败，返回
    if (newsh == NULL) return NULL;
    // 更新 sds 的空余长度
    newsh->free = newlen - len;
    // 返回 sds
    return newsh->buf;
}