【Redis 源码日志】— Redis 数据结构 sds

作者:郑思愿

出处:http://daoluan.net


sds 结构简介

sds 被称为是 Hacking String. hack 的地方就在 sds 保存了字符串的长度以及剩余空间。sds 的实现在 sds.c 中。

sds 头部的实现:

struct sdshdr {
   int len;
   int free;
   char buf[];
};

hacking sds

倘若使用指针即char *buf,分配内存需要量两个步骤:一次分配结构体,一次分配char *buf,在是否内存的时候也需要释放两次内存:一次为char *buf,一次为结构体内存。而用长度为 0 的字符数组可以将分配和释放内存的次数都降低为 1 次,从而简化内存的管理。

另外,长度为 0 的数组即 char buf[] 不占用内存:

// char buf[] 的情况
struct sdshdr s;
printf("%d",sizeof(s));
// 8

// char *buf 的情况
struct sdshdr s;
printf("%d",sizeof(s));
// 12

Redis 中涉及较多的字符串操作,譬如 APPEND 命令。相比普通的字符串,sds 获取字符串的长度以及剩余空间的复杂度都是 O(1),前者需要 O(N)。

// 返回sdshdr.len
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

// 返回sdshdr.free
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

sds.c 中还实现了针对 sds 的字符串操作函数,譬如分配,追加,释放等,这些函数具体详细的实现读者可以自行剖析。

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 【Redis 源码日志】— Redis 数据结构 sds
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏