通过对《Redis 设计与实现》一书的学习，我打算动手自己实现一份“Redis 源代码”作为自己的学习记录。
对 Redis 感兴趣的同学可以查看我的另一篇文章 造个轮子 | 自己动手写一个 Redis。
本章介绍的是 Redis 源代码中的动态字符串 SDS 的实现。
动态字符串 SDS 的实现
SDS 的 API
（1）创建一个包含给定 c 字符串的 sds
sds sdsnew(char *);
（2）为 sds(也就是 buf 数组) 分配指定空间
sds sdsnewlen(sds,int);
（3）创建一个不包含任何内容的空字符串
sds sdsempty(void);
（4）释放给定的 sds
void sdsfree(sds);
（5）创建一个给定 sds 的副本
sds sdsdup(sds);
（6）清空 sds 保存的字符串内容
sds sdsclear(sds);
（7）将给定 c 字符串拼接到另一个 sds 字符串的末尾
sds sdscat(sds,char *);
（8）将给定 sds 字符串拼接到另一个 sds 字符串的末尾
sds sdscatsds(sds,sds);
（9）将给定的 c 字符串复制到 sds 里面，覆盖原有的字符串
sds sdscpy(sds,char *);
（10）保留 sds 给定区间内的数据
sds sdsrange(sds,int,int);
（11）从 sds 中移除所有在 c 字符串中出现过的字符
sds sdstrim(sds,const char *);
（12）对比两个 sds 字符串是否相同
bool sdscmp(sds,sds);
头文件
#ifndef SDS_H
#define SDS_H
// 实现 Redis 中的动态字符串
//SDS:simple dynamic string
typedef struct sdshdr{
// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度, 不
// 包括最后的 ’\0′;
int len;
// 记录 buf 数组中未使用字节的数量
int free;
// 字节数组，用于保存字符串，以
//’\0’ 结束
char* buf;
}*sds;
// 返回 sds 已使用空间的字节数:len
static inline int sdslen(const sds sh){
return sh->len;
}
// 返回 sds 未使用空间的字节数:free
static inline int sdsavail(const sds sh){
return sh->free;
}
// 创建一个包含给定 c 字符串的 sds
sds sdsnew(char *);
// 为 sds(也就是 buf 数组) 分配指定空间 /len
sds sdsnewlen(sds,int);
// 创建一个不包含任何内容的空字符串
sds sdsempty(void);
// 释放给定的 sds
void sdsfree(sds);
// 创建一个给定 sds 的副本
sds sdsdup(sds);
// 清空 sds 保存的字符串内容
sds sdsclear(sds);
// 将给定 c 字符串拼接到另一个 sds 字符串的末尾
sds sdscat(sds,char *);
// 将给定 sds 字符串拼接到另一个 sds 字符串的末尾
sds sdscatsds(sds,sds);
// 将给定的 c 字符串复制到 sds 里面，覆盖原有的字符串
sds sdscpy(sds,char *);
// 保留 sds 给定区间内的数据，不在区间内的数据会被覆盖或清除
//s = sdsnew(“Hello World”);
//sdsrange(s,1,-1); => “ello World”
sds sdsrange(sds,int,int);
// 接受一个 sds 和一个 c 字符串作为参数，从 sds 中移除所有在 c 字符串中出现过的字符
//s = sdsnew(“AA…AA.a.aa.aHelloWorld :::”);
//s = sdstrim(s,”A. :”);
//printf(“%s\n”, s);
//Output will be just “Hello World”.
// 大小写不敏感
sds sdstrim(sds,const char *);
// 对比两个 sds 字符串是否相同
bool sdscmp(sds,sds);
#endif
SDS API 的实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “sds.h”
// 创建一个包含给定 c 字符串的 sds
sds sdsnew(char *init){
sds sh=(sds)malloc(sizeof(struct sdshdr));
sh->len=strlen(init);
sh->free=0;
sh->buf=(char*)malloc(sizeof(char)*(sh->len+1));
// 将字符串内容进行复制
int i;
for(i=0;i<sh->len;i++){
(sh->buf)[i]=init[i];
}
(sh->buf)[i]=’\0′;
return sh;
}
// 为 sds(也就是 buf 数组) 分配指定空间 /len
sds sdsnewlen(sds sh,int len){
int i;
sh->free=len-1-sh->len;
// 保存之前的 buf 内容
char *str=(char *)malloc(sizeof(char)*(sh->len+1));
for(i=0; i<(sh->len); i++){
str[i]=sh->buf[i];
}
str[i]=’\0′;
//sh->buf=(char*)realloc(sh->buf,len);
sh->buf=(char*)malloc(sizeof(char)*len);
for(i=0; i<(sh->len); i++){
sh->buf[i]=str[i];
}
sh->buf[i]=’\0′;
free(str);
return sh;
}
// 创建一个不包含任何内容的空字符串
sds sdsempty(void){
sds sh=(sds)malloc(sizeof(struct sdshdr));
sh->len=0;
sh->free=0;
sh->buf=(char*)malloc(sizeof(char));
sh->buf[0]=’\0′;
return sh;
}
// 释放给定的 sds
void sdsfree(sds *sh){
(*sh)->free=0;
(*sh)->len=0;
free((*sh)->buf);
free(*sh);
}
// 创建一个给定 sds 的副本
sds sdsdup(sds sh01){
sds sh02=(sds)malloc(sizeof(struct sdshdr));
sh02->free=sh01->free;
sh02->len=sh01->len;
sh02->buf=(char*)malloc(sizeof(char)*(sh02->free+sh02->len+1));
int i;
for(i=0;i<sh01->len;i++){
sh02->buf[i]=sh01->buf[i];
}
sh02->buf[i]=’\0′;
return sh02;
}
// 清空 sds 保存的字符串内容
sds sdsclear(sds sh){
int total=sh->len+sh->free+1;
sh->len=0;
sh->free=total-1;
sh->buf[0]=’\0′;
return sh;
}
// 将给定 c 字符串拼接到另一个 sds 字符串的末尾
// 先检查 sds 的空间是否满足修改所需的要求，如
// 果不满足则自动将 sds 空间扩展至执行修改所需
// 要的大小，然后在执行实际的修改操作——防止
// 缓冲区溢出
// 扩展空间的原则：拼接后的字符串是 n 个字节，则
// 再给其分配 n 个字节的未使用空间，buf 数组的实际长度为 n +n+1
// 当 n 超过 1MB 的时候，则为其分配 1MB 的未使用空间
// 两个字符串 cat，中间使用空格隔开
sds sdscat(sds sh,char *str){
int newlen=strlen(str);
int newfree;
// 剩余的空间不够 cat 操作
if(sh->free<=newlen){
// 超出部分的空间
newfree=newlen-sh->free;
if(newfree<1024){
newfree=newfree+newfree+1+sh->len+sh->free;
sh=sdsnewlen(sh,newfree);
}else{
newfree=newfree+1024+1+sh->len+sh->free;
sh=sdsnewlen(sh,newfree);
}
}
int i;
// 执行 cat 操作
sh->buf[sh->len]=’ ‘;
for(i=0;i<newlen;i++){
sh->buf[sh->len+i+1]=str[i];
}
sh->buf[sh->len+i+1]=’\0′;
sh->len+=(newlen+1);
sh->free-=newlen;
return sh;
}
// 将给定 sds 字符串拼接到另一个 sds 字符串的末尾
sds sdscatsds(sds sh,sds str){
int newlen=str->len;
int newfree;
// 剩余的空间不够 cat 操作
if(sh->free<=newlen){
// 超出部分的空间
newfree=newlen-sh->free;
if(newfree<1024){
newfree=newfree+newfree+1+sh->len+sh->free;
sh=sdsnewlen(sh,newfree);
}else{
newfree=newfree+1024+1+sh->len+sh->free;
sh=sdsnewlen(sh,newfree);
}
}
int i;
// 执行 cat 操作
sh->buf[sh->len]=’ ‘;
for(i=0;i<newlen;i++){
sh->buf[sh->len+i+1]=str->buf[i];
}
sh->buf[sh->len+i+1]=’\0′;
sh->len+=(newlen+1);
sh->free-=newlen;
return sh;
}
// 将给定的 c 字符串复制到 sds 里面，覆盖原有的字符串
// 需要先检查
sds sdscpy(sds sh,char *str){
// 新来的长度
int len=strlen(str);
// 需要使用到的新空间长度
int newlen=len-sh->len;
int total;
// 剩余的空间不够了需要重新分配，在 copy
if(newlen>=sh->free){
// 新空间长度大于 1M, 就只多分配 newlen+1M+1
// 总的空间是 len+newlen+1M+1
if(newlen>=1024){
total=len+newlen+1024+1;
//copy 后使用到的 len, 就是新字符串的长度
sh->len=len;
// 空闲的空间长度
//sh->free=total-len-1;
//sh->buf=(char*)realloc(sh->buf,total);
sh=sdsnewlen(sh,total);
// 分配 newlen+newlen+1
}else{
total=len+newlen+newlen+1;
sh->len=len;
//sh->free=total-len-1;
//sh->buf=(char*)realloc(sh->buf,total);
sh=sdsnewlen(sh,total);
}
if(sh->buf==NULL){
printf(“PIG Redis ERROR : Realloc failed.\n”);
}
}else{
// 剩余的空间够, 不需要分配
// 原来拥有的总空间
total=sh->len+sh->free;
sh->len=len;
sh->free=total-sh->len;
}
// 开始 copy
int i;
for(i=0;i<len;i++){
(sh->buf)[i]=str[i];
}
sh->buf[i]=’\0′;
return sh;
}
// 保留 sds 给定区间内的数据，不在区间内的数据会被覆盖或清除
//s = sdsnew(“Hello World”);
//sdsrange(s,1,-1); => “ello World”
sds sdsrange(sds sh,int start,int end){
int newlen=end-start+1;
char *str=(char*)malloc(sizeof(char)*(sh->len+1));
//sh1->free=sh->len-sh1->len;
int i,j;
for(i=start,j=0;i<=end;i++,j++){
str[j]=sh->buf[i];
}
str[j]=’\0′;
sh->buf=(char*)malloc(sizeof(char)*(sh->len+1));
sh->free=sh->len-newlen;
sh->len=newlen;
for(i=0;i<strlen(str);i++){
sh->buf[i]=str[i];
}
sh->buf[i]=’\0’;
free(str);
return sh;
}
// 接受一个 sds 和一个 c 字符串作为参数，从 sds 中移除所有在 c 字符串中出现过的字符
//s = sdsnew(“AA…AA.a.aa.aHelloWorld :::”);
//s = sdstrim(s,”A. :”);
//printf(“%s\n”, s);
//Output will be just “Hello World”.
// 截断操作需要通过内存重分配来释放字符串中不再使用的空间，否则会造成内存泄漏
// 大小写不敏感
// 使用惰性空间释放优化字符串的缩短操作, 执行缩短操作的时候，不立即使用内存重分
// 配来回收缩短后多出来的字节，而是使用 free 属性记录这些字节，等待将来使用
sds sdstrim(sds s,const char *chstr);
// 对比两个 sds 字符串是否相同
bool sdscmp(sds sh1,sds sh2){
if(sh1->len!=sh2->len){
return false;
}
for(int i=0;i<sh1->len;i++){
if(sh1->buf[i]!=sh2->buf[i]){
return false;
}
}
return true;
}
int main(){
printf(“sdsnew(‘sss’)\n”);
sds sh=sdsnew(“sss”);
printf(“%s\n”,sh->buf);
printf(“%d\n”,sh->len);
printf(“%d\n”,sh->free);
printf(“sdscat(sh,’www’)\n”);
sh=sdscat(sh,”www”);
printf(“%s\n”,sh->buf);
/*for(int i=0;i<sh->len;i++){
printf(“%c”,sh->buf[i]);
}*/
printf(“%d\n”,sh->len);
printf(“%d\n”,sh->free);
sds sh1=sdsnew(“qqqq”);
sh=sdscatsds(sh,sh1);
printf(“%s\n”,sh->buf);
printf(“%d\n”,sh->len);
printf(“%d\n”,sh->free);
sh=sdsrange(sh,1,5);
printf(“%s\n”,sh->buf);
printf(“%d\n”,sh->len);
printf(“%d\n”,sh->free);
sds sh3=sdsnew(“qqqq”);
sds sh4=sdsnew(“qqqq”);
if(sdscmp(sh3,sh4)){
printf(“same\n”);
}else{
printf(“no same\n”);
}
/* printf(“sdscpy(sh,’wwww’)\n”);
sh=sdscpy(sh,”wwww”);
printf(“%s\n”,sh->buf);
printf(“%d\n”,sh->len);
printf(“%d\n”,sh->free);
printf(“sdsnewlen(sh,12)\n”);
sh=sdsnewlen(sh,12);
printf(“%s\n”,sh->buf);
printf(“%d\n”,sh->len);
printf(“%d\n”,sh->free);
printf(“sdsdup(sh)\n”);
sds sh1=sdsdup(sh);
printf(“%s\n”,sh1->buf);
printf(“%d\n”,sh1->len);
printf(“%d\n”,sh1->free);
printf(“sdsclear(sh1)\n”);
sh1=sdsclear(sh1);
printf(“%s\n”,sh1->buf);
printf(“%d\n”,sh1->len);
printf(“%d\n”,sh1->free);
*/
sdsfree(&sh);
sdsfree(&sh1);
//sdsfree(&sh2);
sdsfree(&sh3);
sdsfree(&sh4);
system(“pause”);
return 0;
}