第 2 章 简单动态字符串

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

1. 获取 SDS 长度的空间复杂度为 O(1)，获取 C String 长度的空间复杂度为 O(n).
2. SDS 的空间分配策略杜绝了发生缓冲区溢出的可能性
3. SDS 的空间分配策略减少了修改字符串时带来的内存重分配次数

SDS 的空间分配策略

1. 空间预分配
   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
  }
}

2. 惰性空间释放
   当 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;
}