[redis设计与实现][1]基本数据结构——sds

SDS(Simple Dynamic String):对C字符串的封装,可修改、可自动伸缩的字符串实现。Redis默认的字符串实现。

SDS定义:(sds.h)
[cce lang="c"]
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};
[/cce]

与C字符串的区别:

* 常数复杂度获取字符串长度(字符串长度已经记录在结构体中)
* 杜绝缓冲区溢出(每次操作前都会检查空间是否充足,自动扩张和收缩)
* 减少修改字符串带来的内存重分配次数:
*
* 空间预分配(提前预留空间)
* 惰性空间释放(释放的空间暂时保留,防止扩张)
* 二进制安全(不采用\0表示结束)
* 兼容部分C字符串函数(buf数组多保存了一个\0,用于兼容部分C字符串函数)

API:
typedef char *sds;
创建一个字符串:sds sdsnew(const char *init);
[cce lang="c"]
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
//根据sdshdr结构分配内存,多一个用来放\0
if (init) {
sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
} else {
sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
}
if (sh == NULL) return NULL;
sh->len = initlen;
sh->free = 0;
//初始字符串不为NULL,复制过去,然后最后补上\0
if (initlen && init)
memcpy(sh->buf, init, initlen);
sh->buf[initlen] = '\0';
return (char*)sh->buf;
}
[/cce]
拼接字符串:sds sdscat(sds s, const char *t);
[cce lang="c"]
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;
}
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);
//新的空间比最大分配空间小,扩容两倍
//#define SDS_MAX_PREALLOC (1024*1024)
if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; //重新分配空间:sdshdr+字符串长度+1(\0) newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); if (newsh == NULL) return NULL; newsh->free = newlen - len;
return newsh->buf;
}
static inline size_t sdsavail(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->free;
}
[/cce]

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据