Redis6.0.8源码解析二之(数据结构)

╰半橙微兮° 2022-12-06 12:32 129阅读 0赞

### 文章目录 ###

*  简单动态字符串
 *   *  源码
 *  链表
 *  字典
 *   *  如何解决hash冲突的？
     *  (How)如何扩容和收缩?
     *  (When)何时扩容和收缩?
     *  当数据量无比庞大,如何扩容?
 *  跳跃表
 *  整数集合
 *   *  升级or降级
 *  压缩列表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 1]

# 简单动态字符串 #

redis构建了SDS数据结构,主要对c字符串的一种补充.  
**sds.h**  
结构如下:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center]

struct __attribute__ ((__packed__)) sdshdr8 {
        
        //记录buf数组中已使用字节的数量
        //等于SDS保存字符串长度,这里缓存了长度,将获取长度复杂度从O(N)降低到O(1)
        uint8_t len; /* used */
        //记录buf尚未分配字节数量
        uint8_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        //保存字符串,保留一字节存储空字符'\0'
        char buf[];
    };

与C字符串对比,SDS具备如下优点:

*  通过len记录字符串长度,从而将获取长度复杂度从O(N)降低到O(1)
 *  通过free记录尚未分配的策略,减少内存重分配次数,从而增加性能
 *  字符串以空字符串作为字符串结尾,所以不能存储二进制数据,而SDS则通过len判断字符串是否结束,从而达到了支持二进制目的.
 *  通过遵循字符串以空字符结尾的规则,从而可以重用string.h很多函数.

通过free记录尚未分配的策略,主要有如下策略:

*  预分配  
    对SDS修改时,若free空间够,则写入.否则比较SDS修改之后的长度是否>1M,若<,则free=len,则具体占用空间为free+len+1(保存空字符串)  
    若>1M,则分配1M空间,同上.
 *  惰性空间  
    主要优化字符串缩减操作,当执行字符串缩减时,并不会释放内存,而是free记录释放个数.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 1]

## 源码 ##

/**
     *
     *  初始化一个sds
     * @param init   字符串
     * @param initlen  字符串长度
     * @return 返回sds的buf部分
     *
     *  * 复杂度
     *  T = O(N)
     */
    sds sdsnewlen(const void *init, size_t initlen) {
        
        void *sh;
        sds s;
        //获取类型
        char type = sdsReqType(initlen);
        /* Empty strings are usually created in order to append. Use type 8
         * since type 5 is not good at this. */
        //若为SDS_TYPE_5,则默认设置类型为SDS_TYPE_8
        if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
        //获取类型长度
        int hdrlen = sdsHdrSize(type);
        unsigned char *fp; /* flags pointer. */
    
        //zmalloc 不初始化所分配的内存
        sh = s_malloc(hdrlen+initlen+1);
        // 内存分配失败，返回
        if (sh == NULL) return NULL;
        if (init==SDS_NOINIT)
            init = NULL;
        else if (!init)
            //将分配的内存全部初始化为 0
            memset(sh, 0, hdrlen+initlen+1);
        //将s指针偏移到buf
        s = (char*)sh+hdrlen;
        fp = ((unsigned char*)s)-1;
    
        //初始化sh
        switch(type) {
        
            case SDS_TYPE_5: {
        
                *fp = type | (initlen << SDS_TYPE_BITS);
                break;
            }
            case SDS_TYPE_8: {
        
                //将sh转成type对应的数据类型
                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;
            }
        }
        //如果有指定初始化内容，将它们复制到buf中
        if (initlen && init)
            memcpy(s, init, initlen);
        //buf最后一位填充 '\0'
        s[initlen] = '\0';
        //返回buf部分
        return s;
    }
    
    /* Create an empty (zero length) sds string. Even in this case the string
     * always has an implicit null term. */
    /**
     *
     * @return 返回一个保存了空字符串的sds
     *  * 复杂度
     *  T = O(1)
     */
    sds sdsempty(void) {
        
        return sdsnewlen("",0);
    }
    
    /* Create a new sds string starting from a null terminated C string. */
    /**
     * 根据给定字符串,init sds
     * @param init
     * @return
     *
     *  * 复杂度
     *  T = O(N)
     */
    sds sdsnew(const char *init) {
        
        size_t initlen = (init == NULL) ? 0 : strlen(init);
        return sdsnewlen(init, initlen);
    }
    
    /* Duplicate an sds string. */
    /**
     * 复制一个sds
     * * 复杂度
     *  T = O(N)
     * @param s
     * @return
     */
    sds sdsdup(const sds s) {
        
        return sdsnewlen(s, sdslen(s));
    }
    
    /* Free an sds string. No operation is performed if 's' is NULL. */
    /**
     * 释放sds
     *  * 复杂度
     *  T = O(N)
     * @param s
     * @return
     */
    void sdsfree(sds s) {
        
        if (s == NULL) return;
    
        //释放
        s_free(
                //获取sdshdr起始偏移
                (char*)s-
        //根据数据类型获取sdshdr具体长度
        sdsHdrSize(
                //获取flag,也就是当前存储的数据类型
                s[-1]));
    }
    
    /* 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);
    }
    
    /* 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. */
    /**
     * 不释放buf空间情况下, 重置sds保存的字符串
     *  * 复杂度
     *  T = O(1)
     * @param s
     */
    void sdsclear(sds s) {
        
        sdssetlen(s, 0);
        s[0] = '\0';
    }
    
    /* 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 中 buf 的长度进行扩展，确保在函数执行之后，
     *  buf 至少会有 addlen + 1 长度的空余空间
     * （额外的 1 字节是为 \0 准备的）
     *
     *  * 复杂度
     *  T = O(N)
     * @param s
     * @param addlen
     * @return
     */
    sds sdsMakeRoomFor(sds s, size_t addlen) {
        
        void *sh, *newsh;
        //获取sds可用长度
        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;
    
        //获取sds占用空间长度
        len = sdslen(s);
        //获取之前类型的sh偏移
        sh = (char*)s-sdsHdrSize(oldtype);
        //s最少需要的长度
        newlen = (len+addlen);
    
        //根据新长度，为 s 分配新空间所需的大小
        if (newlen < SDS_MAX_PREALLOC)
            // 如果新长度小于 SDS_MAX_PREALLOC
            // 那么为它分配两倍于所需长度的空间
            newlen *= 2;
        else
            // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
            newlen += SDS_MAX_PREALLOC;
    
        //获取新的数据类型
        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);
        if (oldtype==type) {
        
            //重新分配长度
            newsh = s_realloc(sh, hdrlen+newlen+1);
            //分配失败返回NULL
            if (newsh == NULL) return NULL;
            //返回新的sds
            s = (char*)newsh+hdrlen;
        } else {
        
            /* Since the header size changes, need to move the string forward,
             * and can't use realloc */
            //再次重新分配一个sdshdr
            newsh = s_malloc(hdrlen+newlen+1);
            //分配失败返回NULL
            if (newsh == NULL) return NULL;
            //将原来的sdr复制到重新分配的sdshdr上
            memcpy((char*)newsh+hdrlen, s, len+1);
            //释放原来的sh
            s_free(sh);
            //记录新的sdr偏移
            s = (char*)newsh+hdrlen;
            //设置新的数据类型
            s[-1] = type;
            //设置长度
            sdssetlen(s, len);
        }
        //重新设置可分配长度
        sdssetalloc(s, newlen);
        return s;
    }
    
    /* 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+1长度
     * @param s
     * @return
     */
    sds sdsRemoveFreeSpace(sds s) {
        
        void *sh, *newsh;
        char type, oldtype = s[-1] & SDS_TYPE_MASK;
        int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
        //获取sds占用空间长度
        size_t len = sdslen(s);
        //获取可用空间
        size_t avail = sdsavail(s);
        //获取sh偏移
        sh = (char*)s-oldhdrlen;
    
        /* Return ASAP if there is no space left. */
        //无需分配
        if (avail == 0) return s;
    
        /* 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;
    }
    
    /* Return the total size of the allocation of the specified 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.
     */
    /**
     *
     * @param s
     * @return  分配字节数
     *  * 复杂度
     *  T = O(1)
     */
    size_t sdsAllocSize(sds s) {
        
        size_t alloc = sdsalloc(s);
        return sdsHdrSize(s[-1])+alloc+1;
    }
    
    /* Return the pointer of the actual SDS allocation (normally SDS strings
     * are referenced by the start of the string buffer). */
    /**
     *
     * @param s
     * @return sds起始指针
     */
    void *sdsAllocPtr(sds s) {
        
        return (void*) (s-sdsHdrSize(s[-1]));
    }
    
    /* 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);
     */
    /**
     * 将已使用长度,偏移到incr,若incr是负数,则向左截断.
     * @param s
     * @param incr
     */
    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';
    }
    
    /* 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 扩充至指定长度，未使用的空间以 0 字节填充。
     *  * 复杂度：
     *  T = O(N)
     * @param s
     * @param len
     * @return
     */
    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 */
        //尚未使用的空间,填充0
        memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
        //设置新的使用空间的长度
        sdssetlen(s, len);
        return s;
    }
    
    /* 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. */
    /**
     * 将len长度的t字符串,追加到s
     * @param s
     * @param t
     * @param len
     * @return
     */
    sds sdscatlen(sds s, const void *t, size_t len) {
        
        size_t curlen = sdslen(s);
    
        //扩容
        s = sdsMakeRoomFor(s,len);
        // 内存不足,直接返回
        if (s == NULL) return NULL;
        //将t追加到sds字符串末尾
        memcpy(s+curlen, t, len);
        //更改长度
        sdssetlen(s, curlen+len);
        //添加新结尾符号
        s[curlen+len] = '\0';
        //返回sds
        return s;
    }
    
    /* 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. */
    /**
     * 将t追加到s
     * @param s
     * @param t
     * @return
     */
    sds sdscat(sds s, const char *t) {
        
        return sdscatlen(s, t, strlen(t));
    }
    
    /* 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追加到s
     * @param s
     * @param t
     * @return
     */
    sds sdscatsds(sds s, const sds t) {
        
        return sdscatlen(s, t, sdslen(t));
    }
    
    /* Destructively modify the sds string 's' to hold the specified binary
     * safe string pointed by 't' of length 'len' bytes. */
    /**
     * 将len长度的t复制到s中,会覆盖s内容,内存不足则重新分配
     *  *
     * 复杂度
     *  T = O(N)
     * @param s
     * @param t
     * @param len
     * @return
     */
    sds sdscpylen(sds s, const char *t, size_t len) {
        
        //分配的长度<len,则扩容
        if (sdsalloc(s) < len) {
        
            s = sdsMakeRoomFor(s,len-sdslen(s));
            //内存不足,则返回NULL
            if (s == NULL) return NULL;
        }
        //复制内容
        memcpy(s, t, len);
        s[len] = '\0';
        //更新属性
        sdssetlen(s, len);
        return s;
    }
    
    /**
     * 将复制到s中,会覆盖s内容,内存不足则重新分配
     * @param s
     * @param t
     * @return
     */
    /* 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));
    }
    
    /* 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
    /**
     * 将 ll 类型的value转成字符串,并存入s
     * @param s
     * @param value
     * @return
     */
    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;
    }
    
    /* Identical sdsll2str(), but for unsigned long long type. */
    /**
     * 将 ull 类型的value转成字符串,并存入s
     * @param s
     * @param v
     * @return
     */
    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;
    }
    
    /* Create an sds string from a long long value. It is much faster than:
     *
     * sdscatprintf(sdsempty(),"%lld\n", value);
     */
    /**
     * 将long long类型value转成string,然后根据value新建sds
     * @param value
     * @return
     */
    sds sdsfromlonglong(long long value) {
        
        char buf[SDS_LLSTR_SIZE];
        int len = sdsll2str(buf,value);
    
        return sdsnewlen(buf,len);
    }
    
    /* Like sdscatprintf() but gets va_list instead of being variadic. */
    sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
        
        va_list cpy;
        char staticbuf[1024], *buf = staticbuf, *t;
        size_t buflen = strlen(fmt)*2;
    
        /* We try to start using a static buffer for speed.
         * If not possible we revert to heap allocation. */
        if (buflen > sizeof(staticbuf)) {
        
            buf = s_malloc(buflen);
            if (buf == NULL) return NULL;
        } else {
        
            buflen = sizeof(staticbuf);
        }
    
        /* Try with buffers two times bigger every time we fail to
         * fit the string in the current buffer size. */
        while(1) {
        
            buf[buflen-2] = '\0';
            va_copy(cpy,ap);
            vsnprintf(buf, buflen, fmt, cpy);
            va_end(cpy);
            if (buf[buflen-2] != '\0') {
        
                if (buf != staticbuf) s_free(buf);
                buflen *= 2;
                buf = s_malloc(buflen);
                if (buf == NULL) return NULL;
                continue;
            }
            break;
        }
    
        /* Finally concat the obtained string to the SDS string and return it. */
        t = sdscat(s, buf);
        if (buf != staticbuf) s_free(buf);
        return t;
    }
    
    /* Append to the sds string 's' a string obtained using printf-alike format
     * specifier.
     *
     * 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.
     *
     * Example:
     *
     * s = sdsnew("Sum is: ");
     * s = sdscatprintf(s,"%d+%d = %d",a,b,a+b).
     *
     * Often you need to create a string from scratch with the printf-alike
     * format. When this is the need, just use sdsempty() as the target string:
     *
     * s = sdscatprintf(sdsempty(), "... your format ...", args);
     */
    sds sdscatprintf(sds s, const char *fmt, ...) {
        
        va_list ap;
        char *t;
        va_start(ap, fmt);
        t = sdscatvprintf(s,fmt,ap);
        va_end(ap);
        return t;
    }
    
    /* This function is similar to sdscatprintf, but much faster as it does
     * not rely on sprintf() family functions implemented by the libc that
     * are often very slow. Moreover directly handling the sds string as
     * new data is concatenated provides a performance improvement.
     *
     * However this function only handles an incompatible subset of printf-alike
     * format specifiers:
     *
     * %s - C String
     * %S - SDS string
     * %i - signed int
     * %I - 64 bit signed integer (long long, int64_t)
     * %u - unsigned int
     * %U - 64 bit unsigned integer (unsigned long long, uint64_t)
     * %% - Verbatim "%" character.
     */
    sds sdscatfmt(sds s, char const *fmt, ...) {
        
        size_t initlen = sdslen(s);
        const char *f = fmt;
        long i;
        va_list ap;
    
        /* To avoid continuous reallocations, let's start with a buffer that
         * can hold at least two times the format string itself. It's not the
         * best heuristic but seems to work in practice. */
        s = sdsMakeRoomFor(s, initlen + strlen(fmt)*2);
        va_start(ap,fmt);
        f = fmt;    /* Next format specifier byte to process. */
        i = initlen; /* Position of the next byte to write to dest str. */
        while(*f) {
        
            char next, *str;
            size_t l;
            long long num;
            unsigned long long unum;
    
            /* Make sure there is always space for at least 1 char. */
            if (sdsavail(s)==0) {
        
                s = sdsMakeRoomFor(s,1);
            }
    
            switch(*f) {
        
            case '%':
                next = *(f+1);
                f++;
                switch(next) {
        
                case 's':
                case 'S':
                    str = va_arg(ap,char*);
                    l = (next == 's') ? strlen(str) : sdslen(str);
                    if (sdsavail(s) < l) {
        
                        s = sdsMakeRoomFor(s,l);
                    }
                    memcpy(s+i,str,l);
                    sdsinclen(s,l);
                    i += l;
                    break;
                case 'i':
                case 'I':
                    if (next == 'i')
                        num = va_arg(ap,int);
                    else
                        num = va_arg(ap,long long);
                    {
        
                        char buf[SDS_LLSTR_SIZE];
                        l = sdsll2str(buf,num);
                        if (sdsavail(s) < l) {
        
                            s = sdsMakeRoomFor(s,l);
                        }
                        memcpy(s+i,buf,l);
                        sdsinclen(s,l);
                        i += l;
                    }
                    break;
                case 'u':
                case 'U':
                    if (next == 'u')
                        unum = va_arg(ap,unsigned int);
                    else
                        unum = va_arg(ap,unsigned long long);
                    {
        
                        char buf[SDS_LLSTR_SIZE];
                        l = sdsull2str(buf,unum);
                        if (sdsavail(s) < l) {
        
                            s = sdsMakeRoomFor(s,l);
                        }
                        memcpy(s+i,buf,l);
                        sdsinclen(s,l);
                        i += l;
                    }
                    break;
                default: /* Handle %% and generally %<unknown>. */
                    s[i++] = next;
                    sdsinclen(s,1);
                    break;
                }
                break;
            default:
                s[i++] = *f;
                sdsinclen(s,1);
                break;
            }
            f++;
        }
        va_end(ap);
    
        /* Add null-term */
        s[i] = '\0';
        return s;
    }
    
    /* Remove the part of the string from left and from right composed just of
     * contiguous characters found in 'cset', that is a null terminted C string.
     *
     * 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.
     *
     * Example:
     *
     * s = sdsnew("AA...AA.a.aa.aHelloWorld     :::");
     * s = sdstrim(s,"Aa. :");
     * printf("%s\n", s);
     *
     * Output will be just "HelloWorld".
     */
    /**
     * 对sds左右二端修剪,清除cset指定的所有字符
     *  * 复杂度：
     *  T = O(M*N)，M 为 SDS 长度， N 为 cset 长度。
     * @param s
     * @param cset
     * @return
     */
    sds sdstrim(sds s, const char *cset) {
        
        char *start, *end, *sp, *ep;
        size_t len;
    
        sp = start = s;
        ep = end = s+sdslen(s)-1;
        //分别用sp和ep标记剩余字符非cset的指针
        while(sp <= end && strchr(cset, *sp)) sp++;
        while(ep > sp && strchr(cset, *ep)) ep--;
        //重新计算去除cset后剩余长度
        len = (sp > ep) ? 0 : ((ep-sp)+1);
        //将sp~ep中间的字符,移动到sds
        if (s != sp) memmove(s, sp, len);
        //标记最后一个字符为空字符串
        s[len] = '\0';
        //更新长度
        sdssetlen(s,len);
        return s;
    }
    
    /* Turn the string into a smaller (or equal) string containing only the
     * substring specified by the 'start' and 'end' indexes.
     *
     * start and end can be negative, where -1 means the last character of the
     * string, -2 the penultimate character, and so forth.
     *
     * The interval is inclusive, so the start and end characters will be part
     * of the resulting string.
     *
     * The string is modified in-place.
     *
     * Example:
     *
     * s = sdsnew("Hello World");
     * sdsrange(s,1,-1); => "ello World"
     */
    /**
     * 截断start~end字符
     *  * 复杂度
     *  T = O(N)
     * @param s
     * @param start
     * @param end
     */
    void sdsrange(sds s, ssize_t start, ssize_t end) {
        
        size_t newlen, len = sdslen(s);
    
        if (len == 0) return;
        if (start < 0) {
        
            start = len+start;
            if (start < 0) start = 0;
        }
        if (end < 0) {
        
            end = len+end;
            if (end < 0) end = 0;
        }
        newlen = (start > end) ? 0 : (end-start)+1;
        if (newlen != 0) {
        
            if (start >= (ssize_t)len) {
        
                newlen = 0;
            } else if (end >= (ssize_t)len) {
        
                end = len-1;
                newlen = (start > end) ? 0 : (end-start)+1;
            }
        } else {
        
            start = 0;
        }
        if (start && newlen) memmove(s, s+start, newlen);
        s[newlen] = 0;
        sdssetlen(s,newlen);
    }
    
    /* Apply tolower() to every character of the sds string 's'. */
    /**
     * 将sds转成小写
     * @param s
     */
    void sdstolower(sds s) {
        
        size_t len = sdslen(s), j;
    
        for (j = 0; j < len; j++) s[j] = tolower(s[j]);
    }
    
    /* Apply toupper() to every character of the sds string 's'. */
    /**
     *将sds转成大写
     * @param s
     */
    void sdstoupper(sds s) {
        
        size_t len = sdslen(s), j;
    
        for (j = 0; j < len; j++) s[j] = toupper(s[j]);
    }
    
    /* Compare two sds strings s1 and s2 with memcmp().
     *
     * Return value:
     *
     *     positive if s1 > s2.
     *     negative if s1 < s2.
     *     0 if s1 and s2 are exactly the same binary string.
     *
     * If two strings share exactly the same prefix, but one of the two has
     * additional characters, the longer string is considered to be greater than
     * the smaller one. */
    /**
     * 比较
     *  * T = O(N)
     * @param s1
     * @param s2
     * @return
     */
    int sdscmp(const sds s1, const sds s2) {
        
        size_t l1, l2, minlen;
        int cmp;
    
        l1 = sdslen(s1);
        l2 = sdslen(s2);
        minlen = (l1 < l2) ? l1 : l2;
        cmp = memcmp(s1,s2,minlen);
        if (cmp == 0) return l1>l2? 1: (l1<l2? -1: 0);
        return cmp;
    }

# 链表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 2]  
**adlist.h**

链表数据结构

typedef struct list {
        
        //头节点
        listNode *head;
        //尾节点
        listNode *tail;
        //复制节点保存值
        void *(*dup)(void *ptr);
        //释放节点保存值
        void (*free)(void *ptr);
        //对比节点和另外一个输入值是否相等
        int (*match)(void *ptr, void *key);
        //节点数
        unsigned long len;
    } list;

链表节点结构

typedef struct listNode {
        
        //前置节点
        struct listNode *prev;
        //后置节点
        struct listNode *next;
        //值
        void *value;
    } listNode;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 3]  
[点击这里可以参考java实现的双端链表][java]

# 字典 #

数据结构如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 4]  
**dict.h**  
字典表

typedef struct dict {
        
        //类型
        dictType *type;
        //私有数据
        void *privdata;
        //hash表,ht[1]只会对ht[0]进行rehash时使用
        dictht ht[2];
        //记录rehash进度,rehash不在进行时,为-1
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        unsigned long iterators; /* number of iterators currently running */
    } dict;

字典类型

typedef struct dictType {
        
        //算hash值得
        uint64_t (*hashFunction)(const void *key);
        //复制键
        void *(*keyDup)(void *privdata, const void *key);
        //复制value
        void *(*valDup)(void *privdata, const void *obj);
        //比较键
        int (*keyCompare)(void *privdata, const void *key1, const void *key2);
        //销毁键
        void (*keyDestructor)(void *privdata, void *key);
        //销毁val
        void (*valDestructor)(void *privdata, void *obj);
    } dictType;

字段hash表

typedef struct dictht {
        
        //hash表数组,存键值对
        dictEntry **table;
        //table总容量
        unsigned long size;
        //hasn表大小掩码,计算索引值,总是为size-1
        unsigned long sizemask;
        //键值对数量,包含因为冲突形成链表的键值对
        unsigned long used;
    } dictht;

键值对

typedef struct dictEntry {
        
        //键
        void *key;
        //值
        union {
        
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        //下个hash节点,解决hash碰撞
        struct dictEntry *next;
    } dictEntry;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 5]

## 如何解决hash冲突的？ ##

采用链地址法.采用头插法.  
[点击这里可以参考java实现hash链地址法][java_hash]  
[也点击这里参考CHM源码,包括扩容机制][CHM]

## (How)如何扩容和收缩? ##

1.  为ht\[1\]分配空间  
    若扩展,则ht\[0\].used \* 2,然后在used~uses\*2范围内取出>=used的2^n  
    若缩减,找出>=used的2^n
2.  将ht\[0\]所有键值对重新计算hashCode和索引,然后存ht\[1\]中
3.  释放ht\[0\],变更ht\[1\]为ht\[0\],然后新建空白ht\[1\]  
    这里我们可以看到每次rehash后,扩容大小绝对为2^N,这样有啥意义了?大家有没有发现计算索引的sizemask,这个值为容量-1,而容量为2的N次幂,这就保证了sizemask二进制表示为1111111,然后每次hash取模时,都能均匀分布.

## (When)何时扩容和收缩? ##

扩容时机:

1.  服务器没有执行BGSAVE或BGREWRITEAOF命令,且hash表负载因子>=1
2.  服务器正在执行BGSAVE或BGREWRITEAOF命令,且hash表负载因子>=5  
    负载因子=ht\[0\].used/ht\[0\].size  
    可以发现当执行BGSAVE或BGREWRITEAOF命令时,负载因子变得很大,这是因为刷入磁盘需要占用大量磁盘IO,为了减少IO争抢,而扩展负载因子.  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 7]

收缩时机:  
负载因子<0.1

## 当数据量无比庞大,如何扩容? ##

当键值对有成百上千时,如果一次性rehash,这对服务器来说可能暂时降低吞吐,那么这里就要谈谈rehash的渐进式策略.也就是rehash分多次完成.  
步骤如下:

1.  rehash时,设置rehashidx=0,表示开始rehash了
2.  然后在每次对字典CURD时,都会将ht\[0\].table.dictEntry\[rehashidx\]保存ht\[1\]中,然后rehashidx+=1
3.  rehash完成,rehashidx=-1  
    这样的优点,将性能消耗平摊到每次CRUD上,而不是集中消耗性能.  
    针对R时,会先去ht\[0\]查,查不到接着ht\[1\]查.  
    在C时,一律保存ht\[1\]中,  
    这保证了rehash期间ht\[0\]不作任何操作,最终数据都会到ht\[1\]中.

# 跳跃表 #

场景  
有序集合  
集群节点内部数据

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 8]  
**server.h**

//跳跃表节点
    typedef struct zskiplistNode {
        
        //元素
        sds ele;
        //分值,节点按分值从小到大排列
        double score;
        //后退,指向当前节点的前一个节点,主要用于表尾向表头遍历使用
        struct zskiplistNode *backward;
        //节点层
        struct zskiplistLevel {
        
            //前进指针,用于访问位于表尾方向的其他节点,主要用于表头向表尾遍历使用
            struct zskiplistNode *forward;
            //跨度,记录前进指针所指向节点和当前节点的距离
            unsigned long span;
        } level[];
    } zskiplistNode;
    
    //跳跃表列表
    typedef struct zskiplist {
        
        //头,尾节点
        struct zskiplistNode *header, *tail;
        //节点数(不包含头节点)
        unsigned long length;
        //所有节点最大的层数(不包含头节点)
        int level;
    } zskiplist;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 9]

# 整数集合 #

**intset.h**

//整数数组
    typedef struct intset{
        
        //编码
        uint32_t encoding;
        //元素数量
        uint32_t length;
        //保存元素的数组,唯一,有序排列
        //具体存储的位数与编码有关,若编码是int16,则16位存.每个数组值都是16位存储
        int8_t contents[];
    } intset;

## 升级or降级 ##

如果之前存了很多16位数据,接着插入了一个32位数据,就需要将之前16位数据升级为64位.  
升级的步骤如下

1.  分配所有元素占用32位所需空间
2.  接着移动之前16位最后一个数据到重新计算32位的索引位置.
3.  移动完成后,最后新加入的32位数据插入最后一个位.

![在这里插入图片描述][20200913173056993.png_pic_center]  
优点:  
可存储任意类型数据  
当存储高位数时,才会考虑升级,节省内存

不存在降级

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 10]

# 压缩列表 #

使用场景：  
List  
Hash  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 11]  
![在这里插入图片描述][20200913182326453.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 12]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]: /images/20221123/d146360b79ab4dafb7a7bb06470febf6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 1]: /images/20221123/c5802f52fe2f4222b498f56c1a90c109.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/077b35a1783445748847f89d42da14e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d09288da40094d87841a8ea472404408.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/77c3ebff5f744e4dbe6c9a0ef2caa1f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/7bf410fec5dc42cb811690d58dfb06bf.png
[java]: https://blog.csdn.net/Nuan_Feng/article/details/56668716
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/41b5429d90bd4136a531d1f57bb9ce7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/a13be028207742ea96b49099f697fde8.png
[java_hash]: https://blog.csdn.net/Nuan_Feng/article/details/56669176
[CHM]: https://blog.csdn.net/Nuan_Feng/article/details/107071174
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/b88983ae5e9c4730a2b53518acb277c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/31e9c72cabbc4444b571b93415283ab5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/4de4411d295f4402844eb9ff50bbd451.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/57dc39c7b08c4f8399a58296a48f75f4.png
[20200913173056993.png_pic_center]: /images/20221123/03ca6840eef5496cb0d52c68ab431ce6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/35c120316fec4a0e83a537bd53180591.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/80d77f3e732e423cb8a3bf9ab79f5313.png
[20200913182326453.png_pic_center]: /images/20221123/f1d7887408044f27a93862beef8ff768.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221123/5811e4ae7271463bbc4c2c14dff3e980.png