C Implementing dynamic strings , Ensure binary security , That is not to \0 ending ,redis The implementation of the

sds data structure

typedef char *sds;

typedef char *sds;

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

#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

sds It's essentially a char* The pointer to , Point to a contiguous piece of memory

For strings of different lengths , Through different flags The lower three digits of ,alloc Is the allocated length ,len It's the total length ,buf It's a flexible array , Real string data

__attribute__((__packed__)) Achieve byte alignment

 1、 Create string

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    //  Get the string according to its length type
    char type = sdsReqType(initlen);
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); // Calculate the length required for different heads 
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen; //s It's pointing buf The pointer to 
    fp = ((unsigned char*)s)-1;
    //  According to the type and input parameters , initialization sds The head information of 
    switch(type) {
        ...
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        ...
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

2、 Release string , Will free up memory

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

3、 Empty string , Don't free memory , Easy to use again

void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

4、 String concatenation

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

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);// Directly joining together ,  It ensures binary security 
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';// Add a close 
    return s;
}

Which calls sdsMakeRoomFor, It mainly realizes operations such as capacity expansion .

There are two situations ：

1、 If the concatenated string is not larger than the available size , You don't need to expand the capacity to splice directly

2、 If it is larger than the available size , Then expand the capacity , The expansion rule is if it is less than 1MB, Double the capacity , Greater than 1MB, By new length +1MB Capacity expansion

3、 According to the expansion , On memory remalloc or malloc operation

Specific implementation code ：

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;

    //  If the flexible array has enough free space , Go straight back to 
    if (avail >= addlen) return s;

    //  Calculate the expansion method , According to greater than 1Mb To distinguish expansion methods 
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    //  type 5 It's not safe 
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    //  If the type does not change , be realloc, otherwise malloc, In this way, if there is enough space to expand , Will reduce the number of copies 
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        //  The type has changed , All assignments need to be reassigned 
        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;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}