面向过程的C语言没有可变长的字符串,而面向对象语言里,Java有的final String字符串,StringBuffer、StringBuilder可变长对象,C++中有std::string字节流对象。Redis在sds.c、sds.h文中实现了动态可变字符串。
sds数据结构是一个struct类型的结构体,len是分配的字符串空间的占用长度,free是剩余未使用的长度,buf是被sds指向的真实字符串,最后一个字节被’\0‘填充。
sdslen函数是获取sds字符串的已近使用长度,sdsavail函数是获取sds字符串的未使用的长度。 const sds s字符串是指向sdshdr中char buf[]的指针字符串,(void*)(s-(sizeof(struct sdshdr)))的含义为sds向前偏移8个字节的地址,其中,len为4个字节,free是4个字节,buf[]是不占用字节的。
/* * 返回 sds 实际保存的字符串的长度 * * T = O(1) */ static inline size_t sdslen(const sds s) { struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); return sh->len; } /* * 返回 sds 可用空间的长度 * * T = O(1) */ static inline size_t sdsavail(const sds s) { struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); return sh->free; }
sdsnewlen创建一个新的sds字符串,init是一个void类型的数组,initlen是新字符串的长度,如果init为空就会使用zmalloc创建,不为空就会使用zcalloc创建(有关Redis内存分配操作可以看分享的的第一章)。分配空间时+1操作是为了给字符串增加一个结束符号’\0’。分配空间成功后如果initlen和init都不为空,就会使用memcpy(void *dest, const void *src, size_t n) 函数拷贝init到sh->buf中。
memcpy(void *dest, const void *src, size_t n) 返回的从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。
sds sdsnewlen(const void *init, size_t initlen) { struct sdshdr *sh; // 根据是否有初始化内容,选择适当的内存分配方式 // T = O(N) if (init) { // zmalloc 不初始化所分配的内存 sh = zmalloc(sizeof(struct sdshdr) + initlen + 1); } else { // zcalloc 将分配的内存全部初始化为 0 sh = zcalloc(sizeof(struct sdshdr) + initlen + 1); } // 内存分配失败,返回 if (sh == NULL) { return NULL; } // 设置初始化长度 sh->len = initlen; // 新 sds 不预留任何空间 sh->free = 0; // 如果有指定初始化内容,将它们复制到 sdshdr 的 buf 中 // T = O(N) if (initlen && init) { memcpy(sh->buf, init, initlen); } // 以 \0 结尾 sh->buf[initlen] = '\0'; // 返回 buf 部分,而不是整个 sdshdr return (char *) sh->buf; }
调用sdsnewlen创建一个长度为0的空串。
sds sdsempty(void) { return sdsnewlen("", 0); }
在程序设计时,经常会为了不影响原有变量,而去创建一个克隆拷贝一个新的变量去进行逻辑处理。sdsnew函数中就是给定一个init字符串,如果init不为空就传入有值的initlen。
sds sdsnew(const char *init) { size_t initlen = (init == NULL) ? 0 : strlen(init); return sdsnewlen(init, initlen); } sds sdsdup(const sds s) { return sdsnewlen(s, sdslen(s)); }
sds 是指向sdshdr->bufd的指针,所以要向左偏移sizeof(struct sdshdr)个字节,找到结构体sdshdr分配的地址,调用zfree函数回收地址。
void sdsfree(sds s) { if (s == NULL) { return; } zfree(s - sizeof(struct sdshdr)); }
sdsclear函数是清空字符串,但是不回收空间,只是把sh->buf[0]置为了’\0’。在开发团队都遵守规范的清空下,此作法最高效。
void sdsclear(sds s) { // 取出 sdshdr struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr))); // 重新计算属性 sh->free += sh->len; sh->len = 0; // 将结束符放到最前面(相当于惰性地删除 buf 中的内容) sh->buf[0] = '\0'; }
sdsMakeRoomFor函数为了增加鲁棒性,加入很多的校验。SDS_MAX_PREALLOC是一个define 定义的常量,他的最大的大小是1024*1024个字节。函数的扩容机制并不是根据addlen的长度实际分配的,原字符串大小加上新字符串的长度小于SDS_MAX_PREALLOC,对
newlen扩容两倍,否者分配newlen+SDS_MAX_PREALLOC的长度。
/* * 最大预分配长度 */ #define SDS_MAX_PREALLOC (1024*1024) sds sdsMakeRoomFor(sds s, size_t addlen) { struct sdshdr *sh, *newsh; // 获取 s 目前的空余空间长度 size_t free = sdsavail(s); size_t len, newlen; // s 目前的空余空间已经足够,无须再进行扩展,直接返回 if (free >= addlen) { return s; } // 获取 s 目前已占用空间的长度 len = sdslen(s); sh = (void *) (s - (sizeof(struct sdshdr))); // s 最少需要的长度 newlen = (len + addlen); // 根据新长度,为 s 分配新空间所需的大小 if (newlen < SDS_MAX_PREALLOC) { // 如果新长度小于 SDS_MAX_PREALLOC (1024*1024) // 那么为它分配两倍于所需长度的空间 newlen *= 2; } else { // 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC newlen += SDS_MAX_PREALLOC; } // T = O(N) newsh = zrealloc(sh, sizeof(struct sdshdr) + newlen + 1); // 内存不足,分配失败,返回 if (newsh == NULL) { return NULL; } // 更新 sds 的空余长度 newsh->free = newlen - len; // 返回 sds return newsh->buf; }
回收sds中的为使用的空间。sdsMakeRoomFor函数在扩容时,会导致sds字符串有很多的内存空间分配了但是未使用。sdsRemoveFreeSpace正好可以弥补它带来的内存开销。
sds sdsRemoveFreeSpace(sds s) { struct sdshdr *sh; sh = (void *) (s - (sizeof(struct sdshdr))); // 进行内存重分配,让 buf 的长度仅仅足够保存字符串内容 // T = O(N) sh = zrealloc(sh, sizeof(struct sdshdr) + sh->len + 1); // 空余空间为 0 sh->free = 0; return sh->buf; }
公式为:sdshdr 大小 + sdshdr->len +sdshdr->free +1(结束符)
size_t sdsAllocSize(sds s) { struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr))); return sizeof(*sh) + sh->len + sh->free + 1; }
此函数使用了Debug的assert断言功能,在sh->free >= incr或sh->free >= 0时都会使程序异常终止。通过incr来修改sdshdr的len与free的大小。
void sdsIncrLen(sds s, int incr) { struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr))); // 确保 sds 空间足够 assert(sh->free >= incr); // 更新属性 sh->len += incr; sh->free -= incr; // 这个 assert 其实可以忽略 // 因为前一个 assert 已经确保 sh->free - incr >= 0 了 assert(sh->free >= 0); // 放置新的结尾符号 s[sh->len] = '\0'; }
调用sdsMakeRoomFor重新配分空间,最后调用memset把这一块内存空间的值设置为0。
void *memset(void *str, int c, size_t n) 复制字符 c(一个无符号字符)到参数 str 所指向的字符串的前 n 个字符。
sds sdsgrowzero(sds s, size_t len) { struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr))); size_t totlen, curlen = sh->len; // 如果 len 比字符串的现有长度小, // 那么直接返回,不做动作 if (len <= curlen) { return s; } // 扩展 sds // T = O(N) s = sdsMakeRoomFor(s, len - curlen); // 如果内存不足,直接返回 if (s == NULL) { return NULL; } /* Make sure added region doesn't contain garbage */ // 将新分配的空间用 0 填充,防止出现垃圾内容 // T = O(N) sh = (void *) (s - (sizeof(struct sdshdr))); //memset 将某一块内存中的内容全部设置为指定的值 memset(s + curlen, 0, (len - curlen + 1)); /* also set trailing \0 byte */ // 更新属性 totlen = sh->len + sh->free; sh->len = len; sh->free = totlen - sh->len; // 返回新的 sds return s; }
sdscatlen函数类似于Java中字符从apped()追加操作。把 长度为len的const void类型的 *t串,追加到sds s的末尾。首先使用sdsMakeRoomFor扩充空间,再使用memcpy函数进行字符串的拷贝,最后修改新串的len与free。sdscat 调用sdscatlen函数,会使用strlen库函数计算字符串的值,传递给
sdscatlen的size_t len。sdscatsds函数是将一个sds追加到另一个sds之后。
sds sdscatlen(sds s, const void *t, size_t len) { struct sdshdr *sh; // 原有字符串长度 size_t curlen = sdslen(s); // 扩展 sds 空间 // T = O(N) s = sdsMakeRoomFor(s, len); // 内存不足?直接返回 if (s == NULL) { return NULL; } // 复制 t 中的内容到字符串后部 // T = O(N) sh = (void *) (s - (sizeof(struct sdshdr))); memcpy(s + curlen, t, len); // 更新属性 sh->len = curlen + len; sh->free = sh->free - len; // 添加新结尾符号 s[curlen + len] = '\0'; // 返回新 sds return s; } sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); } sds sdscatsds(sds s, const sds t) { return sdscatlen(s, t, sdslen(t)); }
sdscpylen函数将字符串 t 的前 len 个字符复制到 sds s 当中,并在字符串的最后添加终结符。如果如果 sds 的长度少于 len 个字符,那么调用sdsMakeRoomFor函数进行扩容。
sdscpy函数是封装函数,通过计算字符串的长度,调用sdscpylen函数经行复制字符串。
sds sdscpylen(sds s, const char *t, size_t len) { struct sdshdr *sh = (void *) (s - (sizeof(struct sdshdr))); // sds 现有 buf 的长度 size_t totlen = sh->free + sh->len; // 如果 s 的 buf 长度不满足 len ,那么扩展它 if (totlen < len) { // T = O(N) s = sdsMakeRoomFor(s, len - sh->len); if (s == NULL) { return NULL; } sh = (void *) (s - (sizeof(struct sdshdr))); totlen = sh->free + sh->len; } // 复制内容 // T = O(N) memcpy(s, t, len); // 添加终结符号 s[len] = '\0'; // 更新属性 sh->len = len; sh->free = totlen - len; // 返回新的 sds return s; } sds sdscpy(sds s, const char *t) { return sdscpylen(s, t, strlen(t)); }
int sdsll2str(char *s, long long value) :数字 -> 字符串转换
int sdsull2str(char *s, unsigned long long v) :无符号数字 -> 字符串转换
sds sdsfromlonglong(long long value):longlong->sds
sds sdscatvprintf(sds s, const char *fmt, va_list ap):格式化打印sds
sds sdscatprintf(sds s, const char *fmt, …) :打印任意数量个字符串,并将这些字符串追加到给定 sds 的末尾
sds sdscatfmt(sds s, char const *fmt, …):格式化字符串
sds sdstrim(sds s, const char *cset):清除字符串中包含cset的字符
void sdsrange(sds s, int start, int end):按照索引开始start,结束end截取字符串
void sdstolower(sds s):sds全部转换小写
void sdstoupper(sds s) :sds全部转换大写
int sdscmp(const sds s1, const sds s2):比较字符串的大小,相等返回 0 ,s1 较大返回正数, s2 较大返回负数
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count):slipt拆分字符串,使用分隔符 sep 对 s 进行分割,返回一个 sds 字符串的数组,*count 为返回数组元素的数量
void sdsfreesplitres(sds *tokens, int count) :释放字符串数组的内存,回收空间
sds sdscatrepr(sds s, const char p, size_t len):把p变为带有“”号的字符串,追加到sds的末尾
int is_hex_digit(char c) :判断是否是十六进制数,如果是返回正数
hex_digit_to_int(char c) :十六进制转十进制
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen) :在sds中,把from中出现了的字符,替换成字符to
sds sdsjoin(char **argv, int argc, char *sep) :指定分隔符链接sds