簡單動態(tài)字符串 sds

數(shù)據(jù)結(jié)構(gòu)

typedef char *sds;

struct sdshdr {
        // 記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量
        // 等于 SDS 所保存字符串的長度
        int len;
        // 記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
        int free;
        // 字節(jié)數(shù)組，用于保存字符串
        char buf[];
};

與 C 中字符串結(jié)構(gòu)不同的是，C語言需要遍歷字符串以確認字符串結(jié)束的位置(On)，SDS 的效率是 O1.

SDS 的好處不止于此，還可以避免在修改 buf，尤其是追加情況下， 的內(nèi)存溢出問題。

內(nèi)存分配

直接引用別人博客里說的內(nèi)容吧。

1. 在函數(shù)sdsnewlen中，根據(jù)是否需要初始化使用zmalloc和zcalloc兩個不同函數(shù)。
2. 計算字符串長度的時候，直接使用函數(shù)sdslen，不需要調(diào)用strlen。
3. 需要擴展free的空間時， 需要調(diào)用函數(shù)sdsMakeRoomFor， 該函數(shù)空間分配策略比較有意思， 如果free>=addlen,直接返回。 否則判斷free＋addlen是否小于SDS_MAX_PREALLOC這個宏， 如果小于，那么這次就分配2*（free＋addlen）的空間， 這樣每次多分配一陪的空間； 否則就分配free+addlen+SDS_MAX_PREALLOC的空間。 這樣可以控制最大多分配多少的空間， 以至于不要浪費太多空間。例如： sds old＝sdsnew("test one"); sds new=sdscat(old,"test"); 此時有12的空余空間， 如果再次調(diào)用``sdscat(new,”test”)``, 那么就不需要分配空間。
4. 在函數(shù)sdscatvprintf中， 空間申請是以16，32，64..這樣增長的， 無處不透露提高性能。
5. 在函數(shù)sdscmp中， 調(diào)用memcmp， 性能要比strcmp好， 而且還是二進制安全的。
6. 在函數(shù)sdssplitlen中， 默認分配的數(shù)組為5， 然后按照2的倍數(shù)進行增長， 這樣做法，有點浪費空間，但是加快速度，不要每分割出來一個字符串就要申請空間。 比較的時候把seplen為1分出來， 也是加快字符串比較速度的考慮， 大部分時候應(yīng)該是seplen為1。

增加的情況

為什么需要用 free，為什么需要預(yù)先分配內(nèi)存空間？
其實目的很明確，就是避免過多次的分配內(nèi)存空間，因為這個過程時間消耗很大。如果需要修改字符串，檢查 free 是否夠用，如果夠則不分配內(nèi)存，否則分配。達到減少內(nèi)存變動次數(shù)的目的。

預(yù)分配空間的大小是這樣決定的：

1 length >> 20 > 1，length 對于的大小超過 1M，分配 1M 的free
2 length >> 20 <=1, 分配與 length 相同大小的 free

減少的情況-惰性空間釋放

用幾個圖來說明釋放時候 free 的變化情況：

初始狀態(tài)

釋放全部 x,y 的狀態(tài)圖

釋放后追加的狀態(tài)

其他

SDS 是二進制安全的，比 C 只能保存文本數(shù)據(jù)相比具有更多的優(yōu)勢?？梢约嫒莶糠?C 語言中的字符串函數(shù)。