redis数据结构源码分析——string

发布时间:2024年01月07日

前面的文章大体讲解了redis的几种数据类型,针对设计表巧妙的数据类型,后续会出几篇文章单独讲解下,那么本篇文章针对string的源码进行讲解。

字符串的三种编码:

int:整型
redis数据结构源码分析——string
raw:普通字符串

#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* No longer used: old hash encoding. */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */

可以看到,这其中,int,embstr,raw都属于字符串类型。
在object类中可以看到,如果长度小于44字节,则按embstr方式编码,否则按raw方式编码

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

sds结构

那么我们都知道,string类型低层用的是sds来存储的,以下为sds的类型。

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

首先解析下几个属性:
len:已使用长度
alloc:总长度
flags:标识,低三位表示类型,高五位预留
buf:柔性数组,存放数据用的
free=alloc-len
这里可以看到,这几种类型的内部属性其实都是一样的,唯一区别在于len和alloc所占的字节数。
以sdshdr16为例,我们看下大致结构图:
在这里插入图片描述

sds的设计思想和优势

1、在创建的时候返回buf指针,从外界可以直接访问sds的数据
2、可以通过len、alloc做到空间预留,可以快速取值,能达到O(1)的时间复杂度
3、根据不同的长度创建不同的sds,节省空间
4、二进制安全,可以存储二进制数据(在C中,一般字符串都是以“\0”结尾,作为C没办法存储二进制数据,但sds还可以通过len截串,找到数据。)
5、自动重新分配内存(sdsMakeRoomFor中体现),能杜绝缓冲区溢出

sds API解析

那么了解了sds结构后,我们来大致看一下sds的API

sdsnewlen(创建字符串)

首先从字符串的创建入手
代码较长,提取了重点说下,大致流程如下:
1、根据不同的长度选择不同的sds类型
2、如果是type5并且初始长度为0,强制转化成type8
3、计算不同type需要的长度,根据长度申请空间
4、根据不同类型给sdshdr属性赋初值
5、返回sds(sds.buf)

sdsfree(释放字符串)

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

大致流程:
1、通过对s的偏移,计算出sds结构体的首地址
2、调用s_free释放内存
这里的第一步讲解下,也就是s_free后的括号里的内容。首先我们的入参s,是上文所说的sds中的buf[],因此,我们释放的时候,要找到首地址,才能做释放操作。其中,(char*)s是s的位置,而sdsHdrSize(s[-1])头的位置,这里为什么是减呢,因为s的位置在flags之后,要找到首地址,就要向左移动,所以是减。

sdscatlen(拼接字符串)

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

大致流程:
1、调用sdsMakeRoomFor(这是个扩容方法,如果不需要扩容就直接返回,需要扩容就返回扩容后的字符串)
2、判断入参中的sds是否为空,为空则返回
3、调用memcpy(字符串拼接)
4、加上结束符“\0”
这里的sdsMakeRoomFor比较重要,单独说下:

sdsMakeRoomFor(SDS扩容)

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            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. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        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 */
        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);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;

大致流程:
1、获取当前可用空间长度avail,若大于等于新增长度addlen,说明无需扩容,直接返回
2、若avail小于addlen,s的长度加上addlen小于1M(代码中的SDS_MAX_PREALLOC就是1M),那么按新长度的2倍扩容
3、若avail小于addlen,s的长度加上addlen大于1M,那么按新长度加1M
4、根据新长度选择sds类型,若sds类型和原类型相同,则调用s_realloc_usable,扩大柔性数组
5、如果sds类型和原类型不同,则调用s_malloc_usable,重新申请内存,把原buf内容移动到新位置
6、对新串的属性进行赋值,返回。

文章来源:https://blog.csdn.net/weixin_44474209/article/details/135430339
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。