Redis 源码阅读 --- sds

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

typedef char *sds;  

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh; /* 头部指针 */
    sds s;
    /* 根据 initlen 大小选择合适的 sdshdr 类型 */
    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;
    /* 根据 type 返回 sdshdr 的存储空间大小 */
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    /* + 1 是为了存储 \0 */
    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    /* s 指向 buf 数组首地址 */
    s = (char*)sh+hdrlen;
    /* flags pointer */
    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); /* 填充 buf 字符数组的内容 */
    s[initlen] = '\0'; /* 填充终止字符 \0 */
    return s;
}

1
2
3

sds sdsempty(void) {
    return sdsnewlen("",0);
}

1
2
3
4

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

1
2
3

sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

sds sdsfromlonglong(long long value) {
    /* #define SDS_LLSTR_SIZE 21 */
    char buf[SDS_LLSTR_SIZE];
    /* int sdsll2str(char *s, long long value)
     * The function returns the length of the null-terminated string
     * representation stored at 's'.
     * 's' must point to a string with room for at least SDS_LLSTR_SIZE bytes. */
    int len = sdsll2str(buf,value);

    return sdsnewlen(buf,len);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/* 由指向 buf 的指针，获取 sdshdr 的起始地址 */
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
/* 得到 sdshdr5 的长度 */
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

static inline size_t sdslen(const sds s) {
    /* 获取 flags 的值
     * 由于结构体定义使用紧凑模式，所以 s 所指的地址紧接在存储 flags 的地址之后
     * 从而 s[-1] 的内容即为 flags，注意不要和 Python 中的 -1 混淆 */
    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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/* 由指向 buf 的指针，获取 sdshdr 的起始地址 */
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

1

static inline void sdssetlen(sds s, size_t newlen);

1
2

// newlen = len + inc
static inline void sdsinclen(sds s, size_t inc);

1
2
3
4

void sdsupdatelen(sds s) {
    size_t reallen = strlen(s);
    sdssetlen(s, reallen);
}

1
2

/* sdsalloc() = sdsavail() + sdslen() */
static inline size_t sdsalloc(const sds s);

1

static inline void sdssetalloc(sds s, size_t newlen);

1
2
3
4

size_t sdsAllocSize(sds s) {
    size_t alloc = sdsalloc(s);
    return sdsHdrSize(s[-1])+alloc+1;
}

1
2
3

void *sdsAllocPtr(sds s) {
    return (void*) (s-sdsHdrSize(s[-1]));
}

1
2
3
4

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

1
2
3
4
5

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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);
    /* #define SDS_MAX_PREALLOC (1024*1024)
     * 扩容策略：如果 buf 数组未来长度小于 1 M，按所需的两倍扩容
     *          如果 buf 数组未来长度不小于 1 M，比要求多扩容 1 M */
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen); /* new type */

    /* 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); /* new hdrlen */
    if (oldtype==type) {
        /* 不需要更改头部的 len 和 flags，直接扩充 buf 数组的容量 */
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* 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); /* len + 1，\0 也被复制 */
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

1

sds sdsRemoveFreeSpace(sds s);

1

void sdsIncrLen(sds s, ssize_t incr)

1

sds sdsgrowzero(sds s, size_t len);

1

sds sdscatlen(sds s, const void *t, size_t len);

1
2
3

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

1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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 中 */
        buf[buflen-2] = '\0';
        /* void va_copy(va_list dest, va_list src);
         * The va_copy macro copies src to dest. */
        va_copy(cpy,ap);
        /* int vsnprintf(char *restrict buffer,
         *               size_t bufsz,
         *               const char *restrict format,
         *               va_list vlist );
         * writes the results to a character string buffer. At most buflen - 1
         * characters are written. The resulting character string will be
         * terminated with a null character, unless buflen is zero. */
        vsnprintf(buf, buflen, fmt, cpy);
        /* void va_end(va_list ap);
         * The va_end macro performs cleanup for an ap object initialized
         * by a call to va_start or va_copy */
        va_end(cpy);
        if (buf[buflen-2] != '\0') {    /* 当前 buf 不够长! */
            if (buf != staticbuf) s_free(buf);  
            buflen *= 2;
            buf = s_malloc(buflen);
            if (buf == NULL) return NULL;
            continue;
        }
        break;  /* 格式化字符串已全部写入 buf */
    }

    /* Finally concat the obtained string to the SDS string and return it. */
    t = sdscat(s, buf);
    if (buf != staticbuf) s_free(buf);
    return t;
}

1

sds sdscatprintf(sds s, const char *fmt, ...);

1

sds sdscatfmt(sds s, char const *fmt, ...);

1

sds sdscatrepr(sds s, const char *p, size_t len);

1

sds sdsjoin(char **argv, int argc, char *sep);

1

sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

1

sds sdscpylen(sds s, const char *t, size_t len);

1
2
3

sds sdscpy(sds s, const char *t) {
    return sdscpylen(s, t, strlen(t));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;            /* 指向第一个字符 */
    ep = end = s+sdslen(s)-1;  /* 指向终止字符 `\0` 前一字符 */
    /* char *strchr(const char *str, int ch);
     * Finds the first occurrence of `ch` (after conversion to char as if
     * by `(char)ch`) in the null-terminated byte string pointed to by `str`
     * (each character interpreted as unsigned char).
     * 从前往后遍历 sds，如果当前指针所指字符出现在 `cset` 所指字符串中，则指针 +1 */
    while(sp <= end && strchr(cset, *sp)) sp++;
    /* 前一步遍历的终止条件不是越界时, 有 ep > sp
     * 从后往前遍历 sds，如果当前指针所指字符出现在 `cset` 所指字符串中，则指针 -1 */
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    /* void* memmove( void* dest, const void* src, size_t count );
     * Copies count characters from the object pointed to by `src` to the object
     * pointed to by `dest` */
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}

1

void sdsrange(sds s, ssize_t start, ssize_t end);

1

sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count)

1
2
3
4
5
6
7

/* Free the result returned by sdssplitlen(), or do nothing if 'tokens' is NULL. */
void sdsfreesplitres(sds *tokens, int count) {
    if (!tokens) return;
    while(count--)
        sdsfree(tokens[count]);
    s_free(tokens);
}

1

sds *sdssplitargs(const char *line, int *argc)

1
2
3
4

void sdstolower(sds s) {
    size_t len = sdslen(s), j;
    for (j = 0; j < len; j++) s[j] = tolower(s[j]);
}

1
2
3
4

void sdstoupper(sds s) {
    size_t len = sdslen(s), j;
    for (j = 0; j < len; j++) s[j] = toupper(s[j]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

1

sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);