前言

最近开始阅读redis源码，虽然是c语言并不会，但是不影响逻辑阅读，对于内存分配以及回收这一块不太了解，所以不深入探究其中，只要能看懂结构的所占的内存大小和分配时候的代码即可。

正文

SDS（简单动态字符串）

C语言的字符串有许多缺点，redis将字符串进行改造，实现了一个新的字符串结构：sds，看一下实现原理。

struct __attribute__ ((__packed__)) sdshdr5 {
   string length 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc;
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; 
    uint32_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; 
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};
复制代码

字符串一共有5种不同的长度，内部使用了

• len：表示当前字符串长度
• alloc：表示总量
• flags：来表示字符串类型
• buf[]：存储实际字符串。

经过查询__attribute__ ((packed))让结构体在内存中紧凑排序，不需要字节对齐。

值得一提的是，长度为5的字符串是没有alloc信息的，由于长度太短一般不用做用扩容。

看一下新建sds方法

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    //字符串一般用于调整 追加新字符串 使用SDS_TYPE_8比较适合
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    //通过type动态分配内存
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    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 = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
复制代码

sdsnewlen的前半段通过传入的initLen来获取字符串长度，如果initlen为0会获取到SDS_TYPE_5类型，但是由前面可知它并不适合扩容，所以默认分配SDS_TYPE_8

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
    //通过LONG_MAX和LLONG_MAX所占的内存空间来判断使用32位还是64位
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}
复制代码

sdsReqType通过与$2^n$来比大小确定初始字符串长度，在64位和32位机器上做了特殊的判断

static inline int sdsHdrSize(char type) {
    switch(type&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return sizeof(struct sdshdr5);
        case SDS_TYPE_8:
            return sizeof(struct sdshdr8);
        case SDS_TYPE_16:
            return sizeof(struct sdshdr16);
        case SDS_TYPE_32:
            return sizeof(struct sdshdr32);
        case SDS_TYPE_64:
            return sizeof(struct sdshdr64);
    }
    return 0;
}
复制代码

然后根据获取的字符串长度，使用sizeof来获取对应结构体的内存占用

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);
    s[initlen] = '\0';
    return s;
复制代码

后半部分则是根据字符串长度做出对应的赋值，在字符串的结尾设置’\0’，随后创建sds结束。

++sds具有动态扩容的属性，看一下扩容的代码++

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;

    //如果空间够返原sds
    if (avail >= addlen) return s;

    //获取原sds使用长度
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    //小于1M翻倍 大于1M每次扩容1M
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        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);
        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;
        //将原来的字符串复制到新内存空间，包括结尾的 '/0'
        memcpy((char*)newsh+hdrlen, s, len+1);
        //释放原来内存
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        //设置len参数
        sdssetlen(s, len);
    }
    //跟新内存alloc
    sdssetalloc(s, newlen);
    return s;
}
复制代码

该方法接受原字符串和扩容长度，根据中间代码可以得出扩容策略：

• 不满足1M每次扩容为原来的2倍
• 超过1M每次扩容1M。
• 如果扩容后字符串长度类型没有变化，使用s_realloc重新分配内存，不然则重新分配内存释放原来的字符串内存。

sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    size_t avail = sdsavail(s);
    sh = (char*)s-oldhdrlen;

    if (avail == 0) return s;

    type = sdsReqType(len);
    hdrlen = sdsHdrSize(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;
}
复制代码

字符串缩容就和扩容大同小异了，代码差不多

总结一下sds和c语言字符串的特点

adlist 双端list

该list和其他语言的双端实现差不多，简单看一下

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

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;
复制代码

listNode保存前后指针，list结构内部有三个自己实现的方法：复制、释放和匹配节点，默认策略通过指针比较。

list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}
复制代码

创建一个head和tail都为空的list

list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}
复制代码

往头部插入一个节点，代码易懂不解释

总结，该list的实现很简单，只实现了基础功能够用就行。

skipList(跳表)

参考一下我使用其他语言实现的skipList：

跳表实现原理

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;
复制代码

zskiplistNode内部保存了一个level数组，用来保存每一层的数据，span保存了跨度。

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}
复制代码

创建zskiplist，初始化一个空的zskiplist，最大层数为ZSKIPLIST_MAXLEVEL=32，初始化每一层。

分为两个阶段看插入代码

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    //update用于找到score插入位置
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    //rank用于记录上一个节点的span
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    serverAssert(!isnan(score));
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
复制代码

这一个for循环是通过score和字符串来比较每一层的数据，来确定当前数据应该插入的位置，保存在upate数组中

//随机获取当前插入层数
level = zslRandomLevel();
    //如果层数超过当前的，多出来的层进行初始化和设置update
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }y
        zsl->level = level;
    }
    //创建node
    x = zslCreateNode(level,score,ele);
   //遍历每一层 插入node
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    //修改当前span
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
复制代码

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
复制代码

随机层数代码，ZSKIPLIST_P为0.25，表示晋升概率

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;
    int i;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                sdscmp(x->level[i].forward->ele,ele) <= 0))) {
            rank += x->level[i].span;
            x = x->level[i].forward;
        }

        /* x might be equal to zsl->header, so test if obj is non-NULL */
        if (x->ele && sdscmp(x->ele,ele) == 0) {
            return rank;
        }
    }
    return 0;
}
复制代码

zslGetRank获取元素排名，通过这个方法可以看出来span对于排名的作用。

zskiplist的优点不再赘述，可以看给出的链接

总结

本文介绍了sds、adlist和zskipklist的源码，下篇文章看一下dict源码