Redis Source Read Notes (1) – Dynamic string SDS

I have always been interested in Redis source code. In my spare time, I always find time to read it and record my reading experience here. Without further ado, let’s take a look at the relatively simple data structure inside Redis – simple dynamic string SDS, source files are SDS.c and SDS.h.

SDS data structure definition

struct sdshdr {
    // The length of the current string (excluding '\0')
    int len;
    // The length of the remaining free space in the BUF
    int free;
    // Array of characters
    char buf[];
};Copy the code

Redis does not use the string representation in C language (character array ending with ‘\0’), but builds the data structure of SDS as the default string of Redis. Compared with the traditional string of C language, Redis has the advantages of dynamically expanding memory, binary security and compatibility with some C string functions.

Basic operating function

1, SDS create function -sdsnewlen

// The type alias used to point to the buF property of SDSHDR
typedef char *sds;Copy the code

sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;
    // Select the appropriate memory allocation method according to whether there is initialization content
    //+1 because an extra byte is needed to store '\0'
    if (init) {
        // Zmalloc does not initialize allocated memory
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        // zcalloc initializes all allocated memory to 0
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }
    // Failed to allocate memory
    if (sh == NULL) return NULL;
    // Set the initialization length
    sh->len = initlen;
    // New SDS does not reserve any space
    sh->free = 0;
    // If there are specified initializations, copy them to the BUF of SDSHDR
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\ 0';
    // Return the BUF section instead of the entire SDSHDR
    return (char*)sh->buf;
}Copy the code

Note the return value of the function: sh->buf. Many basic operations of SDS start with sh->buf to find the SDSHDR structure, such as sdslen.

2. Obtain the length of the string in SDS -sdslen

/* Gets the string length */
static inline size_t sdslen(const sds s) {
    /* sizeof(struct SDSHDR)) is 8, and s refers to the buf array in SDSHDR, so the result of s-8 is the address of the SDSHDR structure --sh, and len is the length of the string */
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}Copy the code

3, space extension function -sdsMakeRoomFor

// Maximum preallocated length
#define SDS_MAX_PREALLOC (1024*1024)Copy the code

//s Specifies the number of bytes that need to be expanded
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    The sdsavail() function retrieves the current free space of s
    size_t free = sdsavail(s);
    size_t len, newlen;
    If there is enough byte space in s, return it directly
    if (free >= addlen) return s;
    // Get the length of space currently occupied by S
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    // s Specifies the minimum required length
    newlen = (len+addlen);
    // The size required to allocate the new space to S based on the new length
    if (newlen < SDS_MAX_PREALLOC)
        // If the new length is less than 1M
        newlen *= 2;
    else
        // Otherwise, allocate 1 MB more space
        newlen += SDS_MAX_PREALLOC;
    newsh = realloc(sh, sizeof(struct sdshdr)+newlen+1);
    // Insufficient memory, allocation failed, return
    if (newsh == NULL) return NULL;
    // Update the SDS free length
    newsh->free = newlen - len;
    / / returns the SDS
    return newsh->buf;
}Copy the code

The space preallocation policy can reduce the number of memory reallocations caused by string changes and avoid cache overflow: When the string (SDS) operation function needs to modify the SDS, the function will check whether the SDS space meets the requirements after modification. If not, the function will expand the SDS space to the required size after modification, and then perform the modification operation to avoid cache overflow. Cache overflow: For example, when using the strcat() function, if the required memory space is not allocated beforehand, it is prone to cache overflow.

4. Other operating functions

sds sdscat(sds s, const char *t);  // String concatenation function
sds sdsempty(void);     / / clear the SDS
sds sdscpy(sds s, const char *t); // Copy the string
sds sdscatfmt(sds s, char const*fmt, ...) ;// String formatting output
sds sdstrim(sds s, const char *cset);       // String reduction
sds sdsRemoveFreeSpace(sds s);   // Reclaim SDS free spaceCopy the code

conclusion

Write a blog for the first time, if there is a mistake or inappropriate place, the owner of the building is very welcome everyone can reply to discuss, will reply in time. I hope that through the analysis of these functions, play a role of casting a brick to attract jade, readers can have a deeper understanding of the role of other functions and the implementation of the way, experience the author’s programming ideas, at the same time, this is also a way to improve their OWN C language. Thank you very much for Teacher Huang Jianhong’s Redis Design and Implementation, this book has given me a lot of help and support!