专栏首页C++的沉思sds数据结构分析-redis源码阅读笔记(1)
原创

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

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;
}

sds和C字符串的区别

  • 常数复杂度获取字符串长度
  • 杜绝缓冲区溢出
  • 减少修改字符串时带来的内存重分配次数
  • 二进制安全
  • 兼容部分C字符串函

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从位图原理到布隆过滤器的实现

    假设一个int占4个字节(32位),40个亿个整数就是160亿个字节,大概相当于16GB,假设一台计算机只有2GB内存,则16GB一次加载不完,需要分8次加载,...

    evenleo
  • KMP算法分析

    KMP 算法是一种改进的字符串匹配算法,KMP 算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 三人提出的,因此人们称它为克努特—莫...

    evenleo
  • 跳表原理及C++实现

    二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了吗?实际上,只需要对链表稍加改造,就可以支持类似“...

    evenleo
  • redis_3.0.7_sds.h_sdslen()

    青木
  • redis_3.0.7_sds.c_dsRemoveFreeSpace()

    青木
  • redis_3.0.7_sds.c_dsRemoveFreeSpace()

    青木
  • redis_3.0.7_sds.c_sdsAllocSize()

    青木
  • TOP 5:外媒眼中的中国云计算独角兽

    编者按:数字经济不断深化发展的当下,云计算产业风起云涌,也孕育了众多的创业公司。作为全球IDC产业“第二级”,中国市场也愈加吸引全世界的目光。近日,一家外媒就介...

    CloudBest
  • 从SAP最佳业务实践看企业管理(3)-CRM

    那我们就废话少说,先从CRM开始。 CRM软件最早是Oracle(美国的一家软件巨头)公司的几个工程师出来创办的Siebel公司开发的软件产品,据说当年Orac...

    SAP最佳业务实践
  • 机械版CG 实验2 直线生成算法的实现

    理解基本图形元素光栅化的基本原理,掌握一种基本图形元素光栅化算法,利用OpenGL实现直线光栅化的DDA算法。

    步行者08

扫码关注云+社区

领取腾讯云代金券