redis源码解析（一）动态字符串sds结构体

r囧r小猫 2022-05-10 07:36 201阅读 0赞

## 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是一样的，详情可以参考[这里][Link 1]。核心思想其实是结构体存储在虚拟内存中一块连续的地址空间（堆）里，通过偏移量计算，可以根据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;
        }
    }

## 4. 小结 ##

本文介绍了sds动态字符串的结构体及最基本的几个操作函数，在下一篇文章中将进一步分析实现“动态”的功能函数。

[Link 1]: https://blog.csdn.net/u013354486/article/details/80331133