C 語(yǔ)言的字符串函數(shù)

C 語(yǔ)言 string 函數(shù)砖茸，在 C 語(yǔ)言中可以使用 char* 字符數(shù)組實(shí)現(xiàn)字符串邓梅，C 語(yǔ)言標(biāo)準(zhǔn)庫(kù) string.h 中也定義了多種字符串操作函數(shù)酱讶。

字符串使用廣泛，需要滿足：

• 高效的字符串操作枫浙，比如追加我磁、拷貝、比較厌衔、獲取長(zhǎng)度
• 能保存任意的二進(jìn)制數(shù)據(jù)贞谓，比如圖片
• 盡可能省內(nèi)存

為什么 Redis 不直接使用 C 語(yǔ)言的字符串？

• C 語(yǔ)言 char* 以 '\0'標(biāo)識(shí)字符串的結(jié)束葵诈，則中間含有'\0'的字符串無(wú)法被正確表示裸弦；也正因?yàn)榇耍瑳](méi)有辦法保存圖像等二進(jìn)制數(shù)據(jù)作喘。
• C 語(yǔ)言 char* 獲取字符串長(zhǎng)度的時(shí)間復(fù)雜度是 O(N)理疙；追加字符串的時(shí)間復(fù)雜度也是 O(N)，同時(shí)可能由于可用空間不足泞坦，無(wú)法追加窖贤。

下面代碼展示了 C 語(yǔ)言中 '\0' 結(jié)束字符對(duì)字符串的影響。下圖展示了一個(gè)值為 "Redis" 的 C 字符串：

image

#include "stdio.h"
#include "string.h"

int main(void) {
    char *a = "red\0is";
    char *b = "redis\0";
    printf("%lu\n", strlen(a));
    printf("%lu\n", strlen(b));
}

輸出結(jié)果是 3 和 5贰锁。

SDS 定義

SDS（簡(jiǎn)單動(dòng)態(tài)字符串） 是 simple dynamic string 的簡(jiǎn)稱赃梧，Redis 使用 SDS 作為字符串的數(shù)據(jù)結(jié)構(gòu)。Redis 中所有的鍵（key）底層都是 SDS 實(shí)現(xiàn)的豌熄。

比如：

redis> SET msg "hello world"
OK

redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

Redis sds 源碼主要在 sds.h 和 sds.c 中授嘀。其中可以發(fā)現(xiàn) Redis 給 char* 起了別名：

typedef char *sds;

SDS 內(nèi)部結(jié)構(gòu)

SDS 結(jié)構(gòu)中有一個(gè)元數(shù)據(jù) flags，表示的是 SDS 類型（最低 3 位）锣险。事實(shí)上蹄皱，SDS 一共設(shè)計(jì)了 5 種類型，分別是 sdshdr5芯肤、sdshdr8巷折、sdshdr16、sdshdr32 和 sdshdr64崖咨。這 5 種類型的主要區(qū)別就在于锻拘，它們數(shù)據(jù)結(jié)構(gòu)中的字符數(shù)組現(xiàn)有長(zhǎng)度 len 和分配空間長(zhǎng)度 alloc，這兩個(gè)元數(shù)據(jù)的數(shù)據(jù)類型不同击蹲。

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

image

image

static inline size_t sdslen(const sds s) {
    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;
}

獲取剩余容量：sdsavail 函數(shù)署拟，總?cè)萘?alloc - 已使用長(zhǎng)度 len，時(shí)間復(fù)雜度是 O(1)际邻。

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

SDS 的主要操作 API

image

基礎(chǔ)方法有：

sds sdsnewlen(const void *init, size_t initlen);
sds sdstrynewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t len);
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);

sds sdscatvprintf(sds s, const char *fmt, va_list ap);
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
    __attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif

sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdssubstr(sds s, size_t start, size_t len);
void sdsrange(sds s, ssize_t start, ssize_t end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

/* Callback for sdstemplate. The function gets called by sdstemplate
 * every time a variable needs to be expanded. The variable name is
 * provided as variable, and the callback is expected to return a
 * substitution value. Returning a NULL indicates an error.
 */
typedef sds (*sdstemplate_callback_t)(const sds variable, void *arg);
sds sdstemplate(const char *template, sdstemplate_callback_t cb_func, void *cb_arg);

/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, ssize_t incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);

/* Export the allocator used by SDS to the program using SDS.
 * Sometimes the program SDS is linked to, may use a different set of
 * allocators, but may want to allocate or free things that SDS will
 * respectively free or allocate. */
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

字符串初始化

整體和 Java 的 StringBuilder 很像了 O_o

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

首先是判斷輸入的 init 字符串的長(zhǎng)度芯丧，接著調(diào)用 sdsnewlen 分配內(nèi)存空間并賦值。

sds sdsnewlen(const void *init, size_t initlen) {
    return _sdsnewlen(init, initlen, 0);
}

核心函數(shù)_sdsnewlen 如下世曾，主要就是先確庇Ш悖空間是否足夠、分配空間轮听，然后再調(diào)用 memcpy 將 *init 復(fù)制到對(duì)應(yīng)的內(nèi)存空間骗露。

/* 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.
 * If SDS_NOINIT is used, the buffer is left uninitialized;
 *
 * 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, int trymalloc) {
    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. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    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 = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

Redis 源碼簡(jiǎn)潔剖析系列

最簡(jiǎn)潔的 Redis 源碼剖析系列文章

Java 編程思想-最全思維導(dǎo)圖-GitHub 下載鏈接，需要的小伙伴可以自取~

原創(chuàng)不易血巍，希望大家轉(zhuǎn)載時(shí)請(qǐng)先聯(lián)系我萧锉，并標(biāo)注原文鏈接。