動的文字列SDSの実装|自己実装Redisソースコード(1)
10262 ワード
『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)c文字列に出現したすべての文字をsdsから除去する
sds sdstrim(sds,const char *);
(12)2つのsds文字列が同じかどうかを比較する
bool sdscmp(sds,sds);
ヘッダファイル
SDS APIの実装
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)c文字列に出現したすべての文字をsdsから除去する
sds sdstrim(sds,const char *);
(12)2つの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
", s);
//Output will be just "Hello World".
//
sds sdstrim(sds,const char *);
// sds
bool sdscmp(sds,sds);
#endif
SDS APIの実装
#include
#include
#include
#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;ilen;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; ilen); 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; ilen); 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;ilen;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;ibuf[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;ibuf[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.
");
}
}else{
// ,
//
total=sh->len+sh->free;
sh->len=len;
sh->free=total-sh->len;
}
// copy
int i;
for(i=0;ibuf)[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;ibuf[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
", 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;ilen;i++){
if(sh1->buf[i]!=sh2->buf[i]){
return false;
}
}
return true;
}
int main(){
printf("sdsnew('sss')
");
sds sh=sdsnew("sss");
printf("%s
",sh->buf);
printf("%d
",sh->len);
printf("%d
",sh->free);
printf("sdscat(sh,'www')
");
sh=sdscat(sh,"www");
printf("%s
",sh->buf);
/*for(int i=0;ilen;i++){
printf("%c",sh->buf[i]);
}*/
printf("%d
",sh->len);
printf("%d
",sh->free);
sds sh1=sdsnew("qqqq");
sh=sdscatsds(sh,sh1);
printf("%s
",sh->buf);
printf("%d
",sh->len);
printf("%d
",sh->free);
sh=sdsrange(sh,1,5);
printf("%s
",sh->buf);
printf("%d
",sh->len);
printf("%d
",sh->free);
sds sh3=sdsnew("qqqq");
sds sh4=sdsnew("qqqq");
if(sdscmp(sh3,sh4)){
printf("same
");
}else{
printf("no same
");
}
/* printf("sdscpy(sh,'wwww')
");
sh=sdscpy(sh,"wwww");
printf("%s
",sh->buf);
printf("%d
",sh->len);
printf("%d
",sh->free);
printf("sdsnewlen(sh,12)
");
sh=sdsnewlen(sh,12);
printf("%s
",sh->buf);
printf("%d
",sh->len);
printf("%d
",sh->free);
printf("sdsdup(sh)
");
sds sh1=sdsdup(sh);
printf("%s
",sh1->buf);
printf("%d
",sh1->len);
printf("%d
",sh1->free);
printf("sdsclear(sh1)
");
sh1=sdsclear(sh1);
printf("%s
",sh1->buf);
printf("%d
",sh1->len);
printf("%d
",sh1->free);
*/
sdsfree(&sh);
sdsfree(&sh1);
//sdsfree(&sh2);
sdsfree(&sh3);
sdsfree(&sh4);
system("pause");
return 0;
}