Cベースは手書きredis sds

59080 ワード

前言-Simple Dynamic Strings
antirezはRedis,Disque,HiredisプロジェクトにおけるSDSコードを統一したいと考え,このプロジェクトを構築した.
https://github.com/antirez/sds . もっと紹介する背景知識は、READMEを読むことができます.md.  
sdsプロジェクトはC文字列データ構造の実環境における取捨選択実現であり、ライブラリ自体は非スレッドで安全である.下
みんなを連れて関連コードを手書きして、このライブラリの意図を徹底的に理解します(antirez注釈の素晴らしい). 
#define SDS_MAX_PREALLOC  (1024*1024)

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

#define SDS_TYPE_5    0
#define SDS_TYPE_8    1
#define SDS_TYPE_16   2
#define SDS_TYPE_32   3
#define SDS_TYPE_64   4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
#define SDS_HDR(T, s)     ((struct sdshdr##T *)((s) - (sizeof(struct sdshdr##T))))
#define SDS_HDR_VAR(T, s) struct sdshdr##T * sh = SDS_HDR(T, s)

まず、sdshdr 5 sdshdr 8 sdshdr 16 sdshdr 32 sdshdr 64を分析し、著者の意図を感じることができる.  
まず、これらの基本構造には、len、alloc、flags、bufの4つのフィールドがあります.ある同級生は、sdshdr 5
の中でallocとlenフィールドがなくて、これsdshdr 5の構造は比較的に特殊で、そのallocとlenはすべてflagsに隠れています
の各見出しページがあります.関数マクロSDS_からTYPE_5_LEN(f)、見えます.従ってsdshdr 5が表す文字
列の長さと文字列の容量はデフォルトで同じです.もう少し考えてみようattribute__ ((__packed__)) 意図(コンパイラにノットをキャンセルするように伝える)
コンパイル中の最適化位置合わせは、実際の占有バイト数で位置合わせされる).構造メモリのコンパイル位置合わせの最適化を取り消すには、
2点、1メモリを節約し、2メモリの移植が強くなる.  
その後、多くは流水ラインコードである、非常に理解しやすい.例えば、このような関係のあるコードsdsalloc()=sdsavial()+sdslen()
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;
}

inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch (flags & SDS_TYPE_MASK) {
    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;       
    }
    default:
        return 0;
    }  
}

/* sdsalloc() = sdsavail() + sdslen() */
inline size_t sdsalloc(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)->alloc;
    case SDS_TYPE_16:
        return SDS_HDR(16, s)->alloc;
    case SDS_TYPE_32:
        return SDS_HDR(32, s)->alloc;
    case SDS_TYPE_64:
        return SDS_HDR(64, s)->alloc;
    }
    return 0;
}

すぐにsdsalloc()、sdsavial()、sdslen()が何をしているのか理解できたのではないでしょうか❤
 
本文-コードサンプリングの説明
1.コードを繰り返すことで、より良い修正が可能
/* 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;
}

/* 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 or unsigned long long convert to char*では、機能が簡単です.関数の末尾のコード
重複が少なくなく、多重化を再構築することができる. 
inline int sdsreverse(char * s, char * p) {
    /* Compute length and add null term. */
    size_t l = p - s;
    *p = '\0';

    p--;
    while (s < p) {
        char aux = *s;
        *s = *p;
        *p = aux;

        s++;
        p--;
    }

    return (int)l;
}

/* 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;
    unsigned long long v;

    /* Generate the string representation, this method produces
     * an reversed string. */
    v = (value < 0) ? -value : value;
    p = s;
    do {
        *p++ = '0' + (v % 10);
    } while ((v /= 10));
    if (value < 0) *p++ = '-';

    return sdsreverse(s, p);
}

/* Identical sdsll2str(), but for unsigned long long type. */
int sdsull2str(char * s, unsigned long long v) {
    /* Generate the string representation, this method produces
     * an reversed string. */
    char * p = s;
    do {
        *p++ = '0' + (v % 10);
    } while ((v /= 10));

    return sdsreverse(s, p);
}

老学究の気質が際立っているように見えるのではないでしょうか. 
2.vsnprintf用の硬すぎる
/* 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;
}

while vsnprintfが拡張するのは暴力的だ.より良い操作はmanvsnprintf/ここで私の提出を見ることができます
https://github.com/antirez/sds/pull/115/commits/51e2cd78b1a102055979ec9eb83766b8d2cd6927
/* Like sdscatprintf() but gets va_list instead of being variadic. */
sds sdscatvprintf(sds s, const char * fmt, va_list ap) {
    int size;
    va_list cpy;
    char staticbuf[1024], * buf, * t;

    /* Determine required size */
    va_copy(cpy, ap);
    size = vsnprintf(NULL, 0, fmt, cpy);
    va_end(cpy);

    if (size < 0) return NULL;

    /* For '\0' */
    size++;

    /* We try to start using a static buffer for speed.
     * If not possible we revert to heap allocation. */
    if (size > sizeof(staticbuf)) {
        buf = s_malloc(size);
        if (buf == NULL) return NULL;        
    } else {
        buf = staticbuf;
    }

    va_copy(cpy, ap);
    size = vsnprintf(buf, size, fmt, cpy);
    va_end(ap);

    if (size < 0) {
        if (buf != staticbuf) s_free(buf);
        return NULL;
    }

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

聞かないで、聞くのは神様です.
3.sdssplitargsは人に色を見せにくい
/* Helper function for sdssplitargs() that returns non zero if 'c'
 * is a valid hex digit. */
int is_hex_digit(char c) {
    return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') ||
           (c >= 'A' && c <= 'F');
}

/* Helper function for sdssplitargs() that converts a hex digit into an
 * integer from 0 to 15 */
int hex_digit_to_int(char c) {
    switch(c) {
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    case 'a': case 'A': return 10;
    case 'b': case 'B': return 11;
    case 'c': case 'C': return 12;
    case 'd': case 'D': return 13;
    case 'e': case 'E': return 14;
    case 'f': case 'F': return 15;
    default: return 0;
    }
}

/* Split a line into arguments, where every argument can be in the
 * following programming-language REPL-alike form:
 *
 * foo bar "newline are supported
" and "\xff\x00otherstuff" * * The number of arguments is stored into *argc, and an array * of sds is returned. * * The caller should free the resulting array of sds strings with * sdsfreesplitres(). * * Note that sdscatrepr() is able to convert back a string into * a quoted string in the same format sdssplitargs() is able to parse. * * The function returns the allocated tokens on success, even when the * input string is empty, or NULL if the input contains unbalanced * quotes or closed quotes followed by non space characters * as in: "foo"bar or "foo'
*/ sds *sdssplitargs(const char *line, int *argc) { const char *p = line; char *current = NULL; char **vector = NULL; *argc = 0; while(1) { /* skip blanks */ while(*p && isspace(*p)) p++; if (*p) { /* get a token */ int inq=0; /* set to 1 if we are in "quotes" */ int insq=0; /* set to 1 if we are in 'single quotes' */ int done=0; if (current == NULL) current = sdsempty(); while(!done) { if (inq) { if (*p == '\\' && *(p+1) == 'x' && is_hex_digit(*(p+2)) && is_hex_digit(*(p+3))) { unsigned char byte; byte = (hex_digit_to_int(*(p+2))*16)+ hex_digit_to_int(*(p+3)); current = sdscatlen(current,(char*)&byte,1); p += 3; } else if (*p == '\\' && *(p+1)) { char c; p++; switch(*p) { case 'n': c = '
'; break; case 'r': c = '\r'; break; case 't': c = '\t'; break; case 'b': c = '\b'; break; case 'a': c = '\a'; break; default: c = *p; break; } current = sdscatlen(current,&c,1); } else if (*p == '"') { /* closing quote must be followed by a space or * nothing at all. */ if (*(p+1) && !isspace(*(p+1))) goto err; done=1; } else if (!*p) { /* unterminated quotes */ goto err; } else { current = sdscatlen(current,p,1); } } else if (insq) { if (*p == '\\' && *(p+1) == '\'') { p++; current = sdscatlen(current,"'",1); } else if (*p == '\'') { /* closing quote must be followed by a space or * nothing at all. */ if (*(p+1) && !isspace(*(p+1))) goto err; done=1; } else if (!*p) { /* unterminated quotes */ goto err; } else { current = sdscatlen(current,p,1); } } else { switch(*p) { case ' ': case '
': case '\r': case '\t': case '\0': done=1; break; case '"': inq=1; break; case '\'': insq=1; break; default: current = sdscatlen(current,p,1); break; } } if (*p) p++; } /* add the token to the vector */ vector = s_realloc(vector,((*argc)+1)*sizeof(char*)); vector[*argc] = current; (*argc)++; current = NULL; } else { /* Even on empty input string return something not NULL. */ if (vector == NULL) vector = s_malloc(sizeof(void*)); return vector; } } err: while((*argc)--) sdsfree(vector[*argc]); s_free(vector); if (current) sdsfree(current); *argc = 0; return NULL; } /* 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); }

sdssplitargs関数は理解しにくくなりましたが、demoを書いて皆さんに共有しました.
#include 

#include "sds.h"

int main(int argc, char * argv[]) {
    int count;
    const char * line = " hset name \"name:filed\" \"value:field\" ";
    sds * tokens = sdssplitargs(line, &count);

    printf("line = [%s], count = [%d]
", line, count); for (int i = 0; i < count; i++) { printf("tokens[%d] = [%s]
", i, tokens[i]); } sdsfreesplitres(tokens, count); return 0; }

しゅつりょく
line = [ hset name "name:filed" "value:field" ], count = [4]
tokens[0] = [hset]
tokens[1] = [name]
tokens[2] = [name:filed]
tokens[3] = [value:field]

瞬時に悟るかどうか->sdssplitargsはいったいそんなことをするのか! 
全体的に書いて、antirez sdsが実現したのはとても穏やかで、派手なところはありません.
興味のある友人が書くと、収穫が少なくない~
 
後記-もっと頑張れ
間違いは避けられないので、交流を歓迎して水を吹きます~
責任を負わない-https://music.163.com/#/song?id=1363553512
    ( ·  )
     ,     。
     ,     。
     ,     。
     ,     。
     ,     。
     ,     。
     ,     。
     ,     。