What's SDS?
简单动态字符串（Simple Dynamic String，SDS）.
How to define a SDS?
struct sdshdr{
int len;
int free;
char buf[];
}
len 记录 buf 中已使用的长度；free 记录 buf 中未使用的长度。
SDS 遵循 C 语言字符串已空字符结尾的惯例，保存空字符（'\0'）的 1 字节空间不计算在 SDS 的 len 属性里。
What's the difference between SDS & C String
- 获取 SDS 长度的空间复杂度为 O(1)，获取 C String 长度的空间复杂度为 O(n).
- SDS 的空间分配策略杜绝了发生缓冲区溢出的可能性
- SDS 的空间分配策略减少了修改字符串时带来的内存重分配次数
SDS 的空间分配策略
- 空间预分配
1）如果对 SDS 进行修改之后，SDS 的长度（len属性的值）小于 1MB，那么程序分配和len属性同样大小的未使用空间；
2）如果对 SDS 进行修改之后，SDS 的长度大于等于 1MB，那么程序会分配 1MB 的未使用空间。
void sdscat(sds s, sds p){
int allLen = s.len + p.len;
if( allLen < 1MB){
sds newS= sdsnew();
newS.len = allLen;
newS.free = allLen;
// so the real length of buf is allLen * 2 + 1
}else{
sds newS= sdsnew();
newS.len = allLen;
newS.free = 1MB;
// so the real length of buf is allLen + 1MB +1
}
}
- 惰性空间释放
当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。
与此同时，SDS 也提供了相应的 API，让我们可以在有需要时，真正地释放 SDS 的未使用空间，所以不必担心惰性空间释放策略会造成内存浪费。
void sdstrim(sds s, sds p){
s.len = s.len - p.len;
s.free = s.free + p.len;
}
