中文版 | English

Redis源码分析-sds

[TOC]

定义

struct sdshdr { // redis自建的string
    unsigned int len;  // 已用的字节数量
    unsigned int free; // 未使用的字节数量
    char buf[];        // 字节数组，用于保存字符串
};

函数	作用	时间复杂度
sdsnew	创建一个包含给定c字符串的SDS	$O(N)$，N为给定C字符串的长度
ads empty	创建一个不包含任何内容的空SDS	$O(1)$
sdsfree	释放给定的SDS	$O(N)$，N为被释放SDS的长度
sdslen	返回SDS的已使用空间字节数	这个值可以通过读取SDS的len属性来直接获得，复杂度为$O(1)$
sdsavail	返回SDS的未使用空间字节数	这个值可以通过读取SDS的free属性来直接获得，复杂度为$O(1)$
sdsdup	创建一个给定的SDS的副本（copy）	$O(N)$，N为给定SDS的长度
sdsclear	清空SDS保存的字符串内容	因为惰性空间释放策略，复杂度为$O(1)$
sdscat	将给定c字符串拼接到SDS字符串的尾部	$O(N)$，N为被拼接C字符串的长度
sdscatsds	将给定SDS字符串拼接到另一个SDS字符串尾部	$O(N)$，N为被拼接SDS字符串的长度
sdscpy	将给定的c字符串复制到SDS里面，覆盖SDS原有的字符串	$O(N)$，N为被复制c字符串的长度
sdsgrowzero	用空字符将SDS扩展给定长度	$O(N)$，N为扩展新增的字节数
sdsrange	保留SDS给定区间内的数据，不在区间内的数据会被覆盖或清除	$O(N)$，N为被保留数据的字节数
sdstrim	接受一个SDS和一个C字符串作为参数，从SDS中移除所有在C字符串中出现过的字符	$O(N^2)$，N为给定C字符串的长度
sdscmp	对比两个SDS字符串是否相同	$O(N)$，N为两个SDS中较短的那个SDS的长度

当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必要的空间，还会为SDS分配额外的未使用空间。

额外分配的未使用空间数量由以下因素决定：

如果SDS的长度（即len的值）小于1MB，那么程序分配和len属性同样大小的未使用空间。

例：如果SDS的len=13，那么程序也会分配13字节的未使用空间，SDS的buf的总长度为：13+13+1=27字节（额外的1字节用于保存空字符）。
如果SDS的长度（即len的值）大于等于1MB，那么程序会分配1MB的未使用空间。

例：如果SDS的len=30MB，那么程序分配1MB的未使用空间，SDS的buf数组的实际长度为：30MB+1MB+1byte。

当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。

[1] 黄健宏.Redis设计与实现