redis源码解析（二）动态字符串sds基本功能函数

迷南。 2022-05-10 10:06 192阅读 0赞

## 1. 简介 ##

本文继上文基础上，分析动态字符串的功能函数，位于sds.c。由于函数较多，本篇介绍实现动态变化的基本增删新建释放函数。

## 2. 源码分析 ##

sdsHdrSize()函数用于返回sdshdr的大小，主要使用sizeof()函数实现。

/*返回sdshdr大小，主要使用sizeof()函数*/
    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;
    }

sdsReqType()根据size返回sdsHdr类型

/*根据size返回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;
    #endif
        return SDS_TYPE_64;
    }

sdsnewlen()函数创建新的sds动态数组

/* 初始化函数 * Create a new sds string with the content specified by the 'init' pointer * and 'initlen'. * If NULL is used for 'init' the string is initialized with zero bytes. * * The string is always null-termined (all the sds strings are, always) so * even if you create an sds string with: * * mystring = sdsnewlen("abc",3); * * You can print the string with printf() as there is an implicit \0 at the * end of the string. However the string is binary safe and can contain * \0 characters in the middle, as the length is stored in the sds header. */
    sds sdsnewlen(const void *init, size_t initlen) { 
        void *sh;
        sds s;
    	/*根据initlen返回type*/
        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;
    	/*hdrlen赋值为sds的size*/
        int hdrlen = sdsHdrSize(type);
        unsigned char *fp; /* flags pointer. */
    
    	/*分配空间*/
        sh = s_malloc(hdrlen+initlen+1);
        if (!init)
            memset(sh, 0, hdrlen+initlen+1);
    
    	/*错误返回*/
        if (sh == NULL) return NULL;
    	/*s指向数据，fp为首指针前一位，指向flag，存储type*/
        s = (char*)sh+hdrlen;
        fp = ((unsigned char*)s)-1;
        switch(type) { 
            case SDS_TYPE_5: { 
                *fp = type | (initlen << SDS_TYPE_BITS);
                break;
            }
            case SDS_TYPE_8: { 
                SDS_HDR_VAR(8,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
            case SDS_TYPE_16: { 
                SDS_HDR_VAR(16,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
            case SDS_TYPE_32: { 
                SDS_HDR_VAR(32,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
            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;
    }

sdsempty()函数利用sdsnewlen创建空sds动态数组

/* 创建空sds * Create an empty (zero length) sds string. Even in this case the string * always has an implicit null term. */
    sds sdsempty(void) { 
        return sdsnewlen("",0);
    }

sdsnew()利用sdsnewlen()创建sds动态数组

/* 创建新sds * 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);
    }

sdsdup()函数使用sdsnewlen()复制已有的sds

/* 复制sds * Duplicate an sds string. */
    sds sdsdup(const sds s) { 
        return sdsnewlen(s, sdslen(s));
    }

sdsfree()函数释放sds的空间

/* 释放sds * Free an sds string. No operation is performed if 's' is NULL. */
    void sdsfree(sds s) { 
        if (s == NULL) return;
        s_free((char*)s-sdsHdrSize(s[-1]));
    }

sdsupdatelen()函数更新sdsHdr的长度

/* 当sds数据变化后，调用该函数更新sds长度 * Set the sds string length to the length as obtained with strlen(), so * considering as content only up to the first null term character. * * This function is useful when the sds string is hacked manually in some * way, like in the following example: * * s = sdsnew("foobar"); * s[2] = '\0'; * sdsupdatelen(s); * printf("%d\n", sdslen(s)); * * The output will be "2", but if we comment out the call to sdsupdatelen() * the output will be "6" as the string was modified but the logical length * remains 6 bytes. */
    void sdsupdatelen(sds s) { 
        size_t reallen = strlen(s);
        sdssetlen(s, reallen);
    }

sdsclear()函数将sds长度和内容置零

/* 清空sds * Modify an sds string in-place to make it empty (zero length). * However all the existing buffer is not discarded but set as free space * so that next append operations will not require allocations up to the * number of bytes previously available. */
    void sdsclear(sds s) { 
        sdssetlen(s, 0);
        s[0] = '\0';
    }

动态字符串之扩容：sdsMakeRoomFor()函数。根据增加的addlen来调整sdsHdr的类型。

/* sds扩容 * Enlarge the free space at the end of the sds string so that the caller * is sure that after calling this function can overwrite up to addlen * bytes after the end of the string, plus one more byte for nul term. * * Note: this does not change the *length* of the sds string as returned * by sdslen(), but only the free buffer space we have. */
    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;
    
        /* 可用空间够大，则不扩容了 * Return ASAP if there is enough space left. */
        if (avail >= addlen) return s;
    
        len = sdslen(s);
        sh = (char*)s-sdsHdrSize(oldtype);
        newlen = (len+addlen);
        /*这里的翻倍规则和动态数组vector是一样的：便于下次扩容*/
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    
        type = sdsReqType(newlen);
    
        /* 不适用type 5 * 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);
        if (oldtype==type) { 
            newsh = s_realloc(sh, hdrlen+newlen+1);
            if (newsh == NULL) return NULL;
            s = (char*)newsh+hdrlen;
        } else { 
            /* 头部size变化了 * Since the header size changes, need to move the string forward, * and can't use realloc */
            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;
    }

压缩空间的函数sdsRemoveFreeSpace()，功能和扩展空间相反。

/* 用于节省空间，和扩容相反 * Reallocate the sds string so that it has no free space at the end. The * contained string remains not altered, but next concatenation operations * will require a reallocation. * * After the call, the passed sds string is no longer valid and all the * references must be substituted with the new pointer returned by the call. */
    sds sdsRemoveFreeSpace(sds s) { 
        void *sh, *newsh;
        char type, oldtype = s[-1] & SDS_TYPE_MASK;
        int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
        size_t len = sdslen(s);
        sh = (char*)s-oldhdrlen;
    
        /* Check what would be the minimum SDS header that is just good enough to * fit this string. */
        type = sdsReqType(len);
        hdrlen = sdsHdrSize(type);
    
        /* If the type is the same, or at least a large enough type is still * required, we just realloc(), letting the allocator to do the copy * only if really needed. Otherwise if the change is huge, we manually * reallocate the string to use the different header type. */
        if (oldtype==type || type > SDS_TYPE_8) { 
            newsh = s_realloc(sh, oldhdrlen+len+1);
            if (newsh == NULL) return NULL;
            s = (char*)newsh+oldhdrlen;
        } else { 
            newsh = s_malloc(hdrlen+len+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, len);
        return s;
    }

sdsAllocSize()函数返回sds的总大小

/* 返回sds对应的总大小 * Return the total size of the allocation of the specifed sds string, * including: * 1) The sds header before the pointer. * 2) The string. * 3) The free buffer at the end if any. * 4) The implicit null term. */
    size_t sdsAllocSize(sds s) { 
        size_t alloc = sdsalloc(s);
        return sdsHdrSize(s[-1])+alloc+1;
    }

sdsAllocPtr()函数返回sds位置的指针

/* Return the pointer of the actual SDS allocation (normally SDS strings * are referenced by the start of the string buffer). */
    void *sdsAllocPtr(sds s) { 
        return (void*) (s-sdsHdrSize(s[-1]));
    }

sdsIncrLen()函数：增加sds的长度，减少剩余空间的大小

/* 增加sds长度，并减少剩余空间大小 * Increment the sds length and decrements the left free space at the * end of the string according to 'incr'. Also set the null term * in the new end of the string. * * This function is used in order to fix the string length after the * user calls sdsMakeRoomFor(), writes something after the end of * the current string, and finally needs to set the new length. * * Note: it is possible to use a negative increment in order to * right-trim the string. * * Usage example: * * Using sdsIncrLen() and sdsMakeRoomFor() it is possible to mount the * following schema, to cat bytes coming from the kernel to the end of an * sds string without copying into an intermediate buffer: * * oldlen = sdslen(s); * s = sdsMakeRoomFor(s, BUFFER_SIZE); * nread = read(fd, s+oldlen, BUFFER_SIZE); * ... check for nread <= 0 and handle it ... * sdsIncrLen(s, nread); */
    void sdsIncrLen(sds s, ssize_t incr) { 
        unsigned char flags = s[-1];
        size_t len;
        switch(flags&SDS_TYPE_MASK) { 
            case SDS_TYPE_5: { 
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char oldlen = SDS_TYPE_5_LEN(flags);
                assert((incr > 0 && oldlen+incr < 32) || (incr < 0 && oldlen >= (unsigned int)(-incr)));
                *fp = SDS_TYPE_5 | ((oldlen+incr) << SDS_TYPE_BITS);
                len = oldlen+incr;
                break;
            }
            case SDS_TYPE_8: { 
                SDS_HDR_VAR(8,s);
                assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
                len = (sh->len += incr);
                break;
            }
            case SDS_TYPE_16: { 
                SDS_HDR_VAR(16,s);
                assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
                len = (sh->len += incr);
                break;
            }
            case SDS_TYPE_32: { 
                SDS_HDR_VAR(32,s);
                assert((incr >= 0 && sh->alloc-sh->len >= (unsigned int)incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
                len = (sh->len += incr);
                break;
            }
            case SDS_TYPE_64: { 
                SDS_HDR_VAR(64,s);
                assert((incr >= 0 && sh->alloc-sh->len >= (uint64_t)incr) || (incr < 0 && sh->len >= (uint64_t)(-incr)));
                len = (sh->len += incr);
                break;
            }
            default: len = 0; /* Just to avoid compilation warnings. */
        }
        s[len] = '\0';
    }

sdsgrowzero()函数将sds增长len，正常的部分填充0.

/* 将sds增长至某值，增长部分填充0 * Grow the sds to have the specified length. Bytes that were not part of * the original length of the sds will be set to zero. * * if the specified length is smaller than the current length, no operation * is performed. */
    sds sdsgrowzero(sds s, size_t len) { 
        size_t curlen = sdslen(s);
    
        if (len <= curlen) return s;
        s = sdsMakeRoomFor(s,len-curlen);
        if (s == NULL) return NULL;
    
        /* Make sure added region doesn't contain garbage */
        memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
        sdssetlen(s, len);
        return s;
    }

sdscatlen()函数将字符串t增加在sds之后。

/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the * end of the specified sds string 's'. * * After the call, the passed sds string is no longer valid and all the * references must be substituted with the new pointer returned by the call. */
    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;
    }

sdscat()函数和上面函数的区别在于不输入长度len，而使用strlen获取长度

/* 在sds之后增加一个字符串t * Append the specified null termianted C string to the sds string 's'. * * After the call, the passed sds string is no longer valid and all the * references must be substituted with the new pointer returned by the call. */
    sds sdscat(sds s, const char *t) { 
        return sdscatlen(s, t, strlen(t));
    }

sdscatsds()函数在已有的sds之后加上另一个sds

/* 在已有的sds之后添加另一个sds * Append the specified sds 't' to the existing sds 's'. * * After the call, the modified sds string is no longer valid and all the * references must be substituted with the new pointer returned by the call. */
    sds sdscatsds(sds s, const sds t) { 
        return sdscatlen(s, t, sdslen(t));
    }

sdscpylen()使用t代替已有的s

/* 将已有的s内容用t代替 * Destructively modify the sds string 's' to hold the specified binary * safe string pointed by 't' of length 'len' bytes. */
    sds sdscpylen(sds s, const char *t, size_t len) { 
        if (sdsalloc(s) < len) { 
            s = sdsMakeRoomFor(s,len-sdslen(s));
            if (s == NULL) return NULL;
        }
        memcpy(s, t, len);
        s[len] = '\0';
        sdssetlen(s, len);
        return s;
    }

sdscpy()函数和上面函数的区别在于不需要输入len，使用strlen获取

/* 使用自动获取长度的方式，将s内容用以NULL结尾的字符串t代替 * Like sdscpylen() but 't' must be a null-termined string so that the length * of the string is obtained with strlen(). */
    sds sdscpy(sds s, const char *t) { 
        return sdscpylen(s, t, strlen(t));
    }

sdsll2str()函数将一个long long整数转换为字符串s

/* 将一个long long整数转换为字符串s * Helper for sdscatlonglong() doing the actual number -> string * conversion. 's' must point to a string with room for at least * SDS_LLSTR_SIZE bytes. * * The function returns the length of the null-terminated string * representation stored at 's'. */
    #define SDS_LLSTR_SIZE 21
    int sdsll2str(char *s, long long value) { 
        char *p, aux;
        unsigned long long v;
        size_t l;
    
        /* 每次获取最低位，因此存储的是逆序的 * Generate the string representation, this method produces * an reversed string. **/
        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';
    
        /* Reverse the string. */
        p--;
        while(s < p) { 
            aux = *s;
            *s = *p;
            *p = aux;
            s++;
            p--;
        }
        return l;
    }

和上面类似，只是类型为unsigned

/* 和上面类似，只是类型为unsigned * Identical sdsll2str(), but for unsigned long long type. */
    int sdsull2str(char *s, unsigned long long v) { 
        char *p, aux;
        size_t l;
    
        /* Generate the string representation, this method produces * an reversed string. */
        p = s;
        do { 
            *p++ = '0'+(v%10);
            v /= 10;
        } while(v);
    
        /* Compute length and add null term. */
        l = p-s;
        *p = '\0';
    
        /* Reverse the string. */
        p--;
        while(s < p) { 
            aux = *s;
            *s = *p;
            *p = aux;
            s++;
            p--;
        }
        return l;
    }

从long long类型创建一个sds

/* 从long long类型创建一个sds * Create an sds string from a long long value. It is much faster than: * * sdscatprintf(sdsempty(),"%lld\n", value); */
    sds sdsfromlonglong(long long value) { 
        char buf[SDS_LLSTR_SIZE];
        int len = sdsll2str(buf,value);
    
        return sdsnewlen(buf,len);
    }