// 基于本地 Redis 仓 (unstable), src/sds.h
typedef char *sds;   // sds 就是 char*，指向 header 后面的 buf；拿到 sds 的代码可以完全不知道 header 的存在

/* 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 */ // 长度直接塞进 flags 高 5 位，连 len 字段都省了：header 只有 1 字节，但也因此记不住"剩余空间"
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */                                    // 已用长度，O(1) 直接读；长度不靠 '\0' 判定，二进制安全的根源
    uint8_t alloc; /* excluding the header and null terminator */ // 已分配容量（不含 header 和结尾 '\0'），剩余空间 = alloc - len
    unsigned char flags; /* 3 lsb of type, 5 unused bits */    // 低 3 位标记 header 类型；packed 保证它一定是 buf 的前一字节
    char buf[];                                                // 柔性数组不占结构体大小，sds 指针就指向这里
};
// ... sdshdr16 / sdshdr32 / sdshdr64 结构完全相同，只是 len/alloc 依次换成 uint16/32/64_t

#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
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#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))))  // 从 buf 指针回退 sizeof(header)，拿到结构体指针；packed 取消对齐填充，这个减法才精确成立
#define SDS_TYPE_5_LEN(s) (((unsigned char)(s[-1])) >> SDS_TYPE_BITS)

static inline unsigned char sdsType(sds s) {
    unsigned char flags = s[-1];        // 一切操作的起点：buf 前一字节必是 flags
    return flags & SDS_TYPE_MASK;
}

static inline size_t sdslen(const sds s) {   // O(1) 取长度，对比 strlen 的 O(n)
    switch (sdsType(s)) {
        case SDS_TYPE_5: return SDS_TYPE_5_LEN(s);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        // ... 32/64 同理
    }
    return 0;
}

static inline size_t sdsavail(const sds s) {
    switch(sdsType(s)) {
        case SDS_TYPE_5: {
            return 0;                   // 类型 5 没有 alloc 字段，永远报告"没有剩余空间"——所以它只配给不再增长的短串
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        // ... 16/32/64 同理
    }
    return 0;
}

// 基于本地 Redis 仓 (unstable), src/sds.c
char sdsReqType(size_t string_size) {   // 按长度选最省的 header 类型
    if (string_size < 1 << 5) return SDS_TYPE_5;
    if (string_size <= (1 << 8) - sizeof(struct sdshdr8) - 1) return SDS_TYPE_8;    // 上限要扣掉 header 和 '\0'：按"整块分配不超过类型可寻址范围"算，防 alloc 字段截断
    if (string_size <= (1 << 16) - sizeof(struct sdshdr16) - 1) return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size <= (1ll << 32) - sizeof(struct sdshdr32) - 1) return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;                 // 32 位平台 size_t 到不了 4G 以上，TYPE_64 无意义
#endif
}

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;

    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;  // 空串大概率是为了 append 建的，类型 5 记不住剩余空间，直接升 8
    int hdrlen = sdsHdrSize(type);
    size_t bufsize;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &bufsize) :
        s_malloc_usable(hdrlen+initlen+1, &bufsize);    // header + 数据 + '\0' 一次 malloc：单块内存，一次 free，缓存友好；_usable 带回分配器实际给的大小
    if (sh == NULL) return NULL;

    adjustTypeIfNeeded(&type, &hdrlen, bufsize);        // jemalloc 常按 size class 多给内存，多到超出当前类型 alloc 字段的表示范围时，就地升级类型
    return sdsnewplacement(sh, bufsize, type, init, initlen);
}

sds sdsnewplacement(char *buf, size_t bufsize, char type, const char *init, size_t initlen) {
    assert(bufsize >= sdsReqSize(initlen, type));
    int hdrlen = sdsHdrSize(type);
    size_t usable = bufsize - hdrlen - 1;
    sds s = buf + hdrlen;               // 返回值不是分配起点，是 buf 的位置——这就是"sds 指针指向数据"的落地处
    unsigned char *fp = ((unsigned char *)s) - 1; /* flags pointer. */
    // ... 按 type 填 len / alloc / flags（alloc 记的是 usable，即分配器实际给的可用空间）
    if (init == SDS_NOINIT)
        init = NULL;                    // SDS_NOINIT：调用方稍后自己填内容（如从 socket 读入），跳过 memset 省一次大写入
    else if (!init)
        memset(s, 0, initlen);
    else if (initlen)
        memcpy(s, init, initlen);

    s[initlen] = '\0';                  // 永远补 '\0'：花 1 字节换来能直接传给 printf/strcmp 等只读 C 函数
    return s;
}

// 基于本地 Redis 仓 (unstable), src/sds.c
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);          // 底层可能 realloc/malloc，s 会变！所以 sds API 都要求用返回值覆盖旧指针
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);           // 空间由 MakeRoomFor 保证够，这里放心拷——溢出防线在扩容层，不在每个调用点
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

#define SDS_MAX_PREALLOC (1024*1024)    // 预分配封顶 1MB（定义在 sds.h）

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 = sdsType(s);
    int hdrlen;
    size_t bufsize, usable;
    int use_realloc;

    /* 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)  // 新长度 < 1MB：直接翻倍，N 次 append 摊下来只有 O(logN) 次真实 realloc
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC; // >= 1MB：每次固定加 1MB，大字符串再翻倍浪费就失控了
    }

    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 */
    use_realloc = (oldtype == type);
    if (use_realloc) {                  // 类型没变 => header 大小没变 => 数据相对偏移不变，可以 realloc（能原地扩就不搬数据）
        newsh = s_realloc_usable(sh, hdrlen + newlen + 1, &bufsize, NULL);
        if (newsh == NULL) return NULL;
        s = (char*)newsh + hdrlen;
        if (adjustTypeIfNeeded(&type, &hdrlen, bufsize)) {  // 分配器多给到超出本类型上限：升级 header，数据往后挪出新 header 的位置
            memmove((char *)newsh + hdrlen, s, len + 1);
            s = (char *)newsh + hdrlen;
            s[-1] = type;
            sdssetlen(s, len);
        }
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc_usable(hdrlen + newlen + 1, &bufsize);  // header 变大，数据起点要后移，realloc 只会保留"从头开始"的字节，帮不上忙
        if (newsh == NULL) return NULL;
        adjustTypeIfNeeded(&type, &hdrlen, bufsize);
        memcpy((char*)newsh+hdrlen, s, len+1);  // len+1：连结尾 '\0' 一起搬
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = bufsize - hdrlen - 1;
    assert(type == SDS_TYPE_5 || usable <= sdsTypeMaxSize(type));
    sdssetalloc(s, usable);             // alloc 记分配器实际给的可用大小，不是请求的 newlen——多给的也用上
    return s;
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 1);       // greedy：不确定后面还追加多少时用（APPEND 命令走这条）
}

/* Unlike sdsMakeRoomFor(), this one just grows to the necessary size. */
sds sdsMakeRoomForNonGreedy(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 0);       // 明确知道最终大小时用，一字节不多要
}