💮 sds

吞佛童子2022年10月10日

大约 9 分钟

💮 sds

1. 数据结构

__attribute__ ((__packed__)) 的作用：
- 让编译器以紧凑方式分配内存
- 默认情况下若数据类型不同，比如一个 int 和一个 char 一起存放，则 char 也会是 int 的四字节长度
- 若没有该属性，则编译器可能会为 struct 的字段做优化对齐，在其中填充空字节，
  - 这样就无法保证 header & sds 的数据部分严格前后相邻
  - 也就无法按照固定向低地址方向偏移 1 个字节的方式获取 flag 字段，进而无法得出是哪种 header 类型
可以存放任意字符
- C 语言字符串以 \0 即 null 字符作为字符串的终止，因此字符串中间某个字符不能存放 null
- 而 sds 采用 {len + alloc + flags + char[]} 的形式，无需通过 null 判断字符串的终止，而是根据长度、类型计算终止位置，因此可以存储任意字符
获取字符串长度复杂度为 O(1)
不会发生缓冲区的溢出
- 在已有字符串后拼接字符串时，首先根据 alloc - len 判断是否有剩余足够空间，若否，则先扩充 alloc 大小
- 在申请新空间时，若 新空间 < 最大可申请大小(1024 * 1024 == 1MB)，则新空间大小 == 2 * (原字符串长度 + 追加字符串长度)，否则为 1MB
- 减少了扩容的次数
多种 sds 数据结构，节省内存空间
- 可灵活根据不同字符串的大小分配合适的数据结构存储
给定 sds 的结构如何分析？
- 通过 char[] 的地址向前偏移 1 个字节，这个字节就是 flags 所在的字节
- 通过分析 flag 可以得到 header 的类型，判断是 sdshdr5 还是 sdshdr8 等等
- 然后就可以推断出 header 对应的地址，然后就可以读取 len, alloc 等内容，再以此截取指定长度的字符数就是存储的字符串了

typedef char *sds;

/* sdshdr5 从未被使用过 */
// 没有 alloc 字段，无法为字符串分配空余空间
// 若字符串动态增长，必然要重新分配内存
// 适用于存储 静态的短字符串 && len < 2^5
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 一个字节，低 3 位表示 header 的类型，高 5 位记录 字符串长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 字符串的字符数，不包含 len, alloc, flag 之类，就只是 使用的字符的长度 */
    uint8_t alloc; /* 分配给字符串的空间长度，不包含 flag 和 null 结束符，通过 alloc - len 可得出剩余分配空间 */
    unsigned char flags; /* 一个字节，低 3 位表示 header 的类型，高 5 位未被使用 */
    // 字符数组，长度 == 最大容量 + 1，存放 header & data，这里 + 1 是因为最后要额外添加一个 null(ASCⅡ 对应 '\0') 以便和 C 兼容
    // 这里并没有指定数组长度，这时 C 的一种特殊写法，在分配内存时，并不占用内存空间，仅仅是一个标识作用
    // 在分配后，若计算 sizeof(struct sdshdr8) 就只会得到前面字段的长度 == 3 字节
    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[];
};

// 定义的 header 类型，用 flag 的低 3 位表示，共 5 中类型
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

2. 基础函数

包含在 .h 文件中

#define SDS_TYPE_MASK 7 // 用于获取 flag 的低 3 位
#define SDS_TYPE_BITS 3 // header 所占的位数
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) // 获取 header 起始指针
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS) // 获取 sdshdr5 的 字符串字符数，即获取 flag 的 高 5 位

// 获取字符串长度
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1]; // s 前面一个字节表示的是 flags
    switch(flags & SDS_TYPE_MASK) { // 与 SDS_TYPE_MASK 想与，只保留低 3 位获取 header 类型
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags); // 直接求 flags 的高 5 位就是长度
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len; // 得到 header 指针所在地址后，那么指向的就是这个对象了，然后获取 sds.len 直接读取
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

// 获取字符串剩余可用空间 == alloc - len
static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags & SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0; // sdshdr5 一经确定，无法分配动态空间
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

// 设置字符串长度
static inline void sdssetlen(sds s, size_t newlen) {
    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;
    }
}

// 增加字符串长度
static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

/* 获取字符串容量 sdsalloc() = sdsavail() + sdslen() */
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags); // 直接返回字符串长度
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

// 设置字符串容量
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags & SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            break; // 没有 alloc 这个字段，自然也无法设置其值
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

3. 创建

/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

// 创建一个初始长度为 initlen 的字符串
sds sdsnewlen(const void *init, size_t initlen) {
    return _sdsnewlen(init, initlen, 0);
}

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen); // 根据给定初始长度，确定使用哪种 sds
     // 如果得出是要用 sdshdr5 那么需要采用 sdshdr8，因为空字符串创建后一般都需要追加数据，因此 dsshdr5 不太合适
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); // 当前类型 sds 的内存大小，这里 char[] 还未分配，因此得到的是 header 的大小
    unsigned char *fp; /* flags 指针 */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) : // 尝试分配内存 == header + initlen + null 结束符
        s_malloc_usable(hdrlen+initlen+1, &usable); // 无论如何都要分配内存
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s); // 获取 sds header 地址
            sh->len = initlen; // 修改 len
            sh->alloc = usable; // 修改 alloc
            *fp = type; // 设置 flag 类型
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0'; // 最后一个有效字符是 null，和 C 兼容
    return s;
}

// 根据类型获取 header 的大小
static inline int sdsHdrSize(char type) {
    switch(type&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return sizeof(struct sdshdr5);
        case SDS_TYPE_8:
            return sizeof(struct sdshdr8);
        case SDS_TYPE_16:
            return sizeof(struct sdshdr16);
        case SDS_TYPE_32:
            return sizeof(struct sdshdr32);
        case SDS_TYPE_64:
            return sizeof(struct sdshdr64);
    }
    return 0;
}

// 根据给定大小确定使用哪种 sds 结构
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

// 根据指定 sds 类型，获取 能够存放的最大字符数
static inline size_t sdsTypeMaxSize(char type) {
    if (type == SDS_TYPE_5)
        return (1<<5) - 1;
    if (type == SDS_TYPE_8)
        return (1<<8) - 1;
    if (type == SDS_TYPE_16)
        return (1<<16) - 1;
#if (LONG_MAX == LLONG_MAX)
    if (type == SDS_TYPE_32)
        return (1ll<<32) - 1;
#endif
    return -1; /* this is equivalent to the max SDS_TYPE_64 or SDS_TYPE_32 */
}

4. 字符串拼接

/* 在 s 后面追加 t
 */
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

/* 在 s 后面追加 len 长度的 t */
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s); // 获取 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;
}

/* 申请多余 所需空闲空间 的大小，这样可以避免频繁的追加数据导致的 频繁的 内存申请 */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 1);
}

/* 
 * 为字符串申请足够的空间
 * 若空间本身已经足够，那么无需任何操作；若空间不足以放置 addlen，那么需要申请更多的空间
 * greedy == 1 时，申请比 所需更大的空间，为了防止未来频繁的内存申请
 * greedy == 0 时，申请足够 所需空间即可
 * 该函数不会改变通过 sdslen() 得到的字符串大小，而仅仅是申请了内存
 */
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;

    /* 1. 有足够空间，直接返回 */
    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; // 申请后总空间大小 == 2 * (原字符串长度 + 追加字符串长度)
        else
            newlen += SDS_MAX_PREALLOC; // 申请后总空间大小 == 最大可申请大小(1024 * 1024 == 1MB)
    }

    type = sdsReqType(newlen); // 获取新数组大小对应的 sds 类型

    /* 若为 sds5，变为 sds8 */
    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 { 
        /* 类型改变，整个字符串都需要重新分配 */
        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;
}

#define SDS_MAX_PREALLOC (1024*1024)

💮 sds

# 💮 sds

# 1. 数据结构

# 2. 基础函数

# 3. 创建

# 4. 字符串拼接

💮 sds

1. 数据结构

2. 基础函数

3. 创建

4. 字符串拼接