Redis源码详解3:动态字符串

C语言并没有在语言层面上支持字符串,Redis对C语言原生的char*类型做了封装,实现了简单的动态字符串,可以动态扩展,实现代码基本在sds.hsds.csdsalloc.c三个文件中。

先看头文件sds.h

#define SDS_MAX_PREALLOC (1024*1024)
const char *SDS_NOINIT;
typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {  // 8位长度的字符串头
    uint8_t len; /* 字符串真实长度; used */
    uint8_t alloc; /* 最大容量,不包括header和空终止符; excluding the header and null terminator */
    unsigned char flags; /* header类型,只用最后3位; 3 lsb of type, 5 unused bits */
    char buf[];
};
// 省略 sdshdr16 sdshdr32 sdshdr64

#define SDS_TYPE_5  0   // b'00000000'
#define SDS_TYPE_8  1   // b'00000001'
#define SDS_TYPE_16 2   // b'00000010'
#define SDS_TYPE_32 3   // b'00000011'
#define SDS_TYPE_64 4   // b'00000100'
#define SDS_TYPE_MASK 7 // b'00000111'
#define SDS_TYPE_BITS 3

字符串可以动态增加长度,SDS_MAX_PREALLOC=1Mb,用于控制预分配的内存大小,有以下意义:

  • 如果字符串长度增加后小于1Mb,扩容预分配容量为原来的字符串容量的2倍。
  • 如果字符串长度增加后等于1Mb,每次扩容1Mb。

SDS_NOINIT是一个特殊的char指针,在创建字符串的时候将这个指针作为参数传入则不会将原有内存中的数字清零。

sdschar*类型的封装

接下来是sds头部的定义,除了sdshdr5以外,其他4个头部结构都是类似的,每个头部有4个字段,len表示已经使用的长度,alloc表示已经分配的容量,不包含头部和终止符’\0’,flags表示sds的类型,buf是sds内部存储的真正的字符串。sdshdr5比较特殊,只使用flags字段表示类型。flags只用最低的三位,从0到4分别表示SDS_TYPE_5,SDS_TYPE_8,SDS_TYPE_16,SDS_TYPE_32,SDS_TYPE_64。

sds.c

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    // 空字符串
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    // flags指针
    unsigned char *fp;
    // 分配内存 头部+字符串长度+1结尾'\0'
    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    // 分配内存失败
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
    // 指针指向flags
    fp = ((unsigned char*)s)-1;
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        // 省略 SDS_TYPE_16 SDS_TYPE_32 SDS_TYPE_64
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    // 终止符
    s[initlen] = '\0';
    return s;
}

sds在内存中的结构如下:

----------------------------------------
| len | alloc | flags | ...buf... | \0 |
----------------------------------------
|<------header------->|
               ^      ^
               |      |
              s-1     s

发表评论

电子邮件地址不会被公开。 必填项已用*标注