Redis 设计与实现读书笔记一 Redis字符串

1 Redis 是C语言实现的

2 C字符串是 /0 结束的字符数组

3 Redis具体的动态字符串实现

/*
* 保存字符串对象的结构
*/
struct sdshdr { // buf 中已占用空间的长度 使求字符串长度操作变成0(1)
int len; // buf 中剩余可用空间的长度 对字符串字符增加修改时 不大于len+free不用重新分配内存(初始化一个字符串时free为0 当修改字符串时会对free进行赋值)
int free; // 数据空间
char buf[];
};
sdshdr
free 5
len 5
buf

--->

'R' 'e' 'd' 'i' 's' '/0'          

4 感觉更像 Java 中的 StringBuffer 的设计

5 源码初始化一个字符串

/*
* 根据给定的初始化字符串 init 和字符串长度 initlen
* 创建一个新的 sds
*
* 参数
* init :初始化字符串指针
* initlen :初始化字符串的长度
*
* 返回值
* sds :创建成功返回 sdshdr 相对应的 sds
* 创建失败返回 NULL
*
* 复杂度
* T = O(N)
*/
/* Create a new sds string with the content specified by the 'init' pointer
* and 'initlen'.
* If NULL is used for 'init' the string is initialized with zero bytes.
*
* The string is always null-termined (all the sds strings are, always) so
* even if you create an sds string with:
*
* mystring = sdsnewlen("abc",3");
*
* You can print the string with printf() as there is an implicit \0 at the
* end of the string. However the string is binary safe and can contain
* \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) { struct sdshdr *sh; // 根据是否有初始化内容,选择适当的内存分配方式
// T = O(N)
if (init) {
// zmalloc 不初始化所分配的内存
sh = zmalloc(sizeof(struct sdshdr)+initlen+);
} else {
// zcalloc 将分配的内存全部初始化为 0
sh = zcalloc(sizeof(struct sdshdr)+initlen+);
} // 内存分配失败,返回
if (sh == NULL) return NULL; // 设置初始化长度
sh->len = initlen;
// 新 sds 不预留任何空间
sh->free = ;
// 如果有指定初始化内容,将它们复制到 sdshdr 的 buf 中
// T = O(N)
if (initlen && init)
memcpy(sh->buf, init, initlen);
// 以 \0 结尾
sh->buf[initlen] = '\0'; // 返回 buf 部分,而不是整个 sdshdr
return (char*)sh->buf;
}

6 修改字符串之前对free操作

/*
* 在不释放 SDS 的字符串空间的情况下,
* 重置 SDS 所保存的字符串为空字符串。
*
* 复杂度
* T = O(1)
*/
/* Modify an sds string on-place to make it empty (zero length).
* However all the existing buffer is not discarded but set as free space
* so that next append operations will not require allocations up to the
* number of bytes previously available. */
void sdsclear(sds s) { // 取出 sdshdr
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); // 重新计算属性
sh->free += sh->len;
sh->len = ; // 将结束符放到最前面(相当于惰性地删除 buf 中的内容)
sh->buf[] = '\0';
} /* Enlarge the free space at the end of the sds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
/*
* 对 sds 中 buf 的长度进行扩展,确保在函数执行之后,
* buf 至少会有 addlen + 1 长度的空余空间
* (额外的 1 字节是为 \0 准备的)
*
* 返回值
* sds :扩展成功返回扩展后的 sds
* 扩展失败返回 NULL
*
* 复杂度
* T = O(N)
*/
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
// 那么为它分配两倍于所需长度的空间
newlen *= ;
else
// 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+); // 内存不足,分配失败,返回
if (newsh == NULL) return NULL; // 更新 sds 的空余长度
newsh->free = newlen - len; // 返回 sds
return newsh->buf;
}
上一篇:fab 菜单实现之前传-钟表表盘


下一篇:C++智能指针初学小结