前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >redis数据结构-SDS

redis数据结构-SDS

作者头像
仙士可
发布2023-02-01 14:44:03
2710
发布2023-02-01 14:44:03
举报
文章被收录于专栏:仙士可博客仙士可博客

温馨提示:

本文最后更新于 2022年12月30日,已超过 32 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

sds

在redis中,存储字符串的结构称为 sds (Simple Dynamic String) 简单动态字符串

在源码sds.h中定义如下:

代码语言:javascript
复制
typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
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[];
};

可以看出,sds其实只是一个char 的一个别名,实现sds的完整数据结构包括了 sdshdr\ 的结构

attribute ((packed))

这个语法是gcc编译器的特有的语法,表示结构体将不使用内存对齐技术,而是使用紧凑模式存储结构体,例如:

代码语言:javascript
复制
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

struct Test1 {
    char a;//1
    uint8_t b;//1
    uint32_t c;//4
    uint64_t d;//8
};
struct __attribute__ ((__packed__))  Test2 {
    char a;//1
    uint8_t b;//1
    uint32_t c;//4
    uint64_t d;//8
};

int main() {
    printf("%ld\n", sizeof(struct Test1));//16
    printf("%ld\n", sizeof(struct Test2));//14
    return 0;
}

在这个例子中,内存存储为:

file
file

在Test1 中,最大的直接为unit64 占用8字节,为了内存对齐,则会额外分配一个新的8字节,用于存储其他属性,其他属性如果存的下就存,存不下就开辟新的8字节,用于内存对齐

file
file

而在Test2中,使用了紧凑模式,字节数等于成员占用内存数,节省了一部分内存

sds存储结构

在sds中,8的存储结构如下:

代码语言:javascript
复制
typedef char *sds;
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[];
};

如图:

file
file

可以看到,sdshdr8的内存地址,包含了len,alloc,flags,buff则存储了sds的指针和字符串数据,那么可以发现,sds指针-1的位置,是flag

代码语言:javascript
复制
unsigned char flags = s[-1];

flags低三位表示类型,通过flags能知道具体存储的类型:

代码语言:javascript
复制
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }

通过类型,可以知道前面的结构体的类型,从而知道结构体的长度,sds的指针位置-结构体长度=sdshdr的指针位置:

代码语言:javascript
复制
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

这样,我们就知道了sds和sdshdr之间的关系

创建字符串

申请长度为 sdshdr结构体长度+字符串长度+1的内存空间,为什么需要+1呢?因为存储字符串时,会额外存储 "\0"用于结尾:

代码语言:javascript
复制
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);

这样,sds字符串的指针位置,就等于 sdshdr指针+sdshdr长度

代码语言:javascript
复制
    s = (char*)sh+hdrlen;

最后,通过memcpy,将字符串的值复制到sds的上,加上\0,就完成了

代码语言:javascript
复制
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';

动态扩容字符串

当需要动态扩容字符串时,先计算新的长度数量,贪婪模式下,将扩充为2倍:

代码语言:javascript
复制
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }

计算新长度需要使用的sdshdr结构体类型,判断旧结构体类型是否一致

如果类型一致,则只需要额外分配新的内存空间即可

代码语言:javascript
复制
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    }

如果不一致,则需要类似于新增的逻辑,重新分配一块新的内存空间,将旧数据拷贝到新空间中

代码语言:javascript
复制
  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);
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2022-12-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • sds
  • attribute ((packed))
  • sds存储结构
  • 创建字符串
  • 动态扩容字符串
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档