Redis一 - 动态字符串 (Simple Dynamic String)

Redis一 - 动态字符串 (Simple Dynamic String)

主要文件 sds.hsds.c 文件

定义

1
2
3
4
5
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};

相比于传统 C 语言字符串,具有以下优势:

  • 常数复杂度获取字符串长度
1
2
3
4
static inline size_t sdslen(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->len;
}
  • 杜绝缓冲区溢出

克服传统 C 语言字符串容易溢出的问题:

1
char *strcat(char *dest, const char *src)

先检查长度是否足够,不够的话自动扩展空间,然后执行拼接:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}

sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
size_t curlen = sdslen(s);

s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
sh = (void*) (s-(sizeof(struct sdshdr)));
memcpy(s+curlen, t, len);
sh->len = curlen+len;
sh->free = sh->free-len;
s[curlen+len] = '\0';
return s;
}
  • 减少修改字符串带来的内存重分配次数

空间预分配策略: 字符串长度小于 1MB,空间成倍增长;字符串长度大于 1MB,空间递进增长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define SDS_MAX_PREALLOC (1024*1024)

sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s);
size_t len, newlen;

if (free >= addlen) return s;
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
if (newsh == NULL) return NULL;

newsh->free = newlen - len;
return newsh->buf;
}

惰性空间释放: 只是增加 free ,而并不会 free 空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sds sdstrim(sds s, const char *cset) {
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
char *start, *end, *sp, *ep;
size_t len;

sp = start = s;
ep = end = s+sdslen(s)-1;
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > start && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1);
if (sh->buf != sp) memmove(sh->buf, sp, len);
sh->buf[len] = '\0';
sh->free = sh->free+(sh->len-len);
sh->len = len;
return s;
}

其中 memmove 函数从 src 位置拷贝 n 个字节到 dest

1
void *memmove(void *dest, const void *src, size_t n);

由上可知,只是移动了子串,而并没有 free 多余出来的空间,避免了缩短字符串时所需的内存重分配操作,并为将来可能有的增长提供了优化。

  • 二进制安全: 可以在中间保存 \0 字符
  • 可以使用部分 <string.h> 库中的函数

参考

推荐文章