字符串

構(gòu)造方法

不同長度的字符串采用不同數(shù)據(jù)結(jié)構(gòu)記錄其長度

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

字符串追加方法

/* 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);
  
    // 按需調(diào)整空間，如果容量不夠容納追加的內(nèi)容，就會重新分配字節(jié)數(shù)組并復(fù)制原字符串的內(nèi)容到新數(shù)組中
    s = sdsMakeRoomFor(s,len); 
    if (s == NULL) return NULL;   // 內(nèi)存不足
    memcpy(s+curlen, t, len);     // 追加目標字符串到字節(jié)數(shù)組中
    sdssetlen(s, curlen+len);     // 設(shè)置追加后的長度
    s[curlen+len] = '\0';         // 讓字符串以 \0 結(jié)尾，便于調(diào)試打印
    return s;
}

列表

通過鏈表結(jié)構(gòu)實現(xiàn)，高插入、刪除效率，查詢效率低

構(gòu)造源碼

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

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;

字典

構(gòu)造源碼

• 一個字典中包含有兩個dictht結(jié)構(gòu)，即一個字典中存放了兩個hashtable
• 其中一個table在正常使用時為空，用于字典擴容時的漸進式rehash

typedef struct dictht {
    // 哈希表數(shù)組
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩碼，用于計算索引值，總是等于 size - 1
    unsigned long sizemask;
    // 該哈希表已有節(jié)點的數(shù)量
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    // 內(nèi)部有兩個 dictht 結(jié)構(gòu)
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

內(nèi)部節(jié)點構(gòu)造

typedef struct dictEntry {
    // 鍵
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下個哈希表節(jié)點，形成鏈表
    struct dictEntry *next;
} dictEntry;