redis源码解析（一）动态字符串sds结构体-蒲公英云

1. 简介

Redis是一个开源的使用ANSI C语言编写、遵守BSD协议、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，并提供多种语言的API。它通常被称为数据结构服务器，因为值（value）可以是字符串(String), 哈希(Map), 列表(list), 集合(sets) 和有序集合(sorted sets)等类型。

由于该库代码优美，实现巧妙，值得学习，因此从本篇开始将学习最新版本4.0.11 redis的源码实现。这一切，就从最基础的数据结构sds开始。

2. sds结构

动态字符串sds的实现主要在sds.c和sds.h中，其中头文件主要是实现结构体和几个基本函数，源文件中定义了动态字符串所需要的函数。基本功能和C++ STL的vector动态数组类似。

下面就来看看sds结构体吧。sds本身只是char *的别名，源码中定义如下

typedef char *sds;

根据sds动态字符串的长度不同，定义了不同的sdshdr结构体，存储sds相应的信息以及最后的buf（使用柔性数组从而可变长）。

/* 针对不同长度整形做了相应的数据结构 * 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[];
};

我们可以看到，这里主要区别在于len和alloc采用的类型长度不同，而这两个变量分别表示了当前buf的长度，以及已经分配的内存大小。flags用于表示当前采用哪种类型的sdshdr。

3. sds基本函数

下面来看下sds.h中给出的基本函数。首先需要了解两个宏定义，源码如下：

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

看着这两个宏定义，是不是有点眼熟呀？原理其实和container_of是一样的，详情可以参考这里。核心思想其实是结构体存储在虚拟内存中一块连续的地址空间（堆）里，通过偏移量计算，可以根据sds获取到sdshdr的首地址或者其他结构体内变量的地址，从而得到他们的值。SDS_HDR返回的就是sdshdr的首地址，而SDS_HDR_VAR则建立了一个sdshdr指针sh，并赋值给sh。

看懂了这两个宏定义，下面的函数就很简单了，比如这里sdslen()函数，就是SDS_HDR获取结构体指针后读取len的值。

/*获取sdshdr长度，原理和container_of一样*/
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()函数返回alloc-len的值，即当前剩余可用空间。

/*s对应的sdshdr剩余可用空间*/
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;
}

函数sdssetlen()为sdshdr设置新的长度

/*设置新的长度*/
static inline void sdssetlen(sds s, size_t newlen) { 
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) { 
        case SDS_TYPE_5:
            { 
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

函数sdsinclen()在现有的len基础上增加inc

/*已有Len的基础上增加长度*/
static inline void sdsinclen(sds s, size_t inc) { 
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) { 
        case SDS_TYPE_5:
            { 
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

函数sdsalloc()返回sdshdr分配的空间大小，即alloc值

/* alloc等于可用+现长 * sdsalloc() = sdsavail() + sdslen() */
static 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;
}

函数sdssetalloc()为sdshdr设置新的alloc值

/*设置alloc*/
static inline void sdssetalloc(sds s, size_t newlen) { 
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) { 
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}