#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
// sds結(jié)構(gòu)體，使用不同的結(jié)構(gòu)體來保存不同長度大小的字符串
typedef char *sds;
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* flags共8位，低三位保存類型標(biāo)志，高5位保存字符串長度，小于32(2^5-1) */
    char buf[]; // 保存具體的字符串
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 字符串長度，buf已用的長度 */
    uint8_t alloc; /* 為buf分配的總長度，alloc-len就是sds結(jié)構(gòu)體剩余的空間 */
    unsigned char flags; /* 低三位保存類型標(biāo)志 */
    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[];
};

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))

static inline size_t sdslen(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)->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;
}

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

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    /* 只有有足夠空間就馬上返回，否則就繼續(xù)執(zhí)行分配空間的操作 */
    if (avail >= addlen) return s;
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // SDS_MAX_PREALLOC == 1MB，如果修改后的長度小于1M，則分配的空間是原來的2倍，否則增加1MB的空間
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    type = sdsReqType(newlen);
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* 新增空間后超過當(dāng)前類型的長度，使用malloc，并把原字符串拷貝過去 */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type; // 給類型標(biāo)志位賦值
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

// SDS_MAX_PREALLOC == 1MB，如果修改后的長度小于1M，則分配的空間是原來的2倍，否則增加1MB的空間
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;
    sp = start = s;
    ep = end = s+sdslen(s)-1;
    /* 從頭部和尾部逐個字符遍歷往中間靠攏，如果字符在cest中，則繼續(xù)前進(jìn) */
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1); // 全部被去除了，長度就是0
    if (s != sp) memmove(s, sp, len); // 拷貝內(nèi)容
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}

int sdsll2str(char *s, long long value) {
    char *p, aux;
    unsigned long long v;
    size_t l;
    /* 通過取余數(shù)得到原字符串的逆轉(zhuǎn)形式 */
    v = (value < 0) ? -value : value;
    p = s;
    do {
        *p++ = '0'+(v%10);
        v /= 10;
    } while(v);
    if (value < 0) *p++ = '-';
    /* Compute length and add null term. */
    l = p-s;
    *p = '\0';
    /* 反轉(zhuǎn)字符串 */
    p--;
    while(s < p) {
        aux = *s;
        *s = *p;
        *p = aux;
        s++;
        p--;
    }
    return l;
}