放假在家,本想偷个懒,但还是觉得应该给2018一个交代,就扯扯这个吧~
由于redis是用纯c写的,所以没有string那么高端的东西,所以它就自己实现了一个动态字符串的库,用于字符串处理,就是这个SDSLib了~~~
在sdsalloc.h文件中,使用宏定义转换了如下几个函数
-
#include "zmalloc.h"
-
#define s_malloc zmalloc
-
#define s_realloc zrealloc
-
#define s_free zfree
在这里先定义了一堆结构体sdshdrxx, 其中struct 关键字后面的`__attribute__ ((__packed__))`表示该结构体再存储时,不用考虑字节对齐。除了sdshdr5之外均有len成员表示已经占用的长度,alloc成员表示实际分配给字符串的长度。
注意,这里的len和alloc的类型决定了该类sds最多可以存储多少个字符
-
typedef char *sds;
-
-
/* Note: sdshdr5 is never used, we just access the flags byte directly.
-
* However is here to document the layout of type 5 SDS strings. */
-
struct __attribute__ ((__packed__)) sdshdr5 {
-
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
-
char buf[];
-
};
-
struct __attribute__ ((__packed__)) sdshdr8 {
-
uint8_t len; /* used */
-
uint8_t alloc; /* excluding the header and null terminator */
-
unsigned char flags; /* 3 lsb of type, 5 unused bits */
-
char buf[];
-
};
-
struct __attribute__ ((__packed__)) sdshdr16 {
-
uint16_t len; /* used */
-
uint16_t alloc; /* excluding the header and null terminator */
-
unsigned char flags; /* 3 lsb of type, 5 unused bits */
-
char buf[];
-
};
-
struct __attribute__ ((__packed__)) sdshdr32 {
-
uint32_t len; /* used */
-
uint32_t alloc; /* excluding the header and null terminator */
-
unsigned char flags; /* 3 lsb of type, 5 unused bits */
-
char buf[];
-
};
-
struct __attribute__ ((__packed__)) sdshdr64 {
-
uint64_t len; /* used */
-
uint64_t alloc; /* excluding the header and null terminator */
-
unsigned char flags; /* 3 lsb of type, 5 unused bits */
-
char buf[];
-
};
紧接着,又定义了一些宏来定义如何获取对应结构体里的相关信息,这里遵循的原则就是s指向实际使用的字符串首地址,s的前面就是对应的结构体的头部。这里面比较奇怪(或者说我暂时没看懂)的地方就是结构体里面命名定义了flags成员,但是实际取flags的时候,都是直接用s[-1]来存取,其他的变量倒是都用变量名来获取,要是有大侠知道,还请不吝赐教
-
#define SDS_TYPE_5 0
-
#define SDS_TYPE_8 1
-
#define SDS_TYPE_16 2
-
#define SDS_TYPE_32 3
-
#define SDS_TYPE_64 4
-
#define SDS_TYPE_MASK 7
-
#define SDS_TYPE_BITS 3
-
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
-
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
-
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
下面几个函数分别获取成员变量len、剩余空间,设置len、增加len,获取alloc,设置alloc,套路都差不多,这里仅给出获取len和获取可用空间的代码,其余的非常类似
-
static inline size_t sdslen(const sds s) {
-
unsigned char flags = s[-1];
-
switch(flags&SDS_TYPE_MASK) {
-
case SDS_TYPE_5:
-
return SDS_TYPE_5_LEN(flags);
-
case SDS_TYPE_8:
-
return SDS_HDR(8,s)->len;
-
case SDS_TYPE_16:
-
return SDS_HDR(16,s)->len;
-
case SDS_TYPE_32:
-
return SDS_HDR(32,s)->len;
-
case SDS_TYPE_64:
-
return SDS_HDR(64,s)->len;
-
}
-
return 0;
-
}
-
static inline size_t sdsavail(const sds s) {
-
unsigned char flags = s[-1];
-
switch(flags&SDS_TYPE_MASK) {
-
case SDS_TYPE_5: {
-
return 0;
-
}
-
case SDS_TYPE_8: {
-
SDS_HDR_VAR(8,s);
-
return sh->alloc - sh->len;
-
}
-
case SDS_TYPE_16: {
-
SDS_HDR_VAR(16,s);
-
return sh->alloc - sh->len;
-
}
-
case SDS_TYPE_32: {
-
SDS_HDR_VAR(32,s);
-
return sh->alloc - sh->len;
-
}
-
case SDS_TYPE_64: {
-
SDS_HDR_VAR(64,s);
-
return sh->alloc - sh->len;
-
}
-
}
-
return 0;
-
}
当创建一个新的sds串时,会根据请求大小来分配不同类型,如果传入指针和长度均存在,则memcpy
-
static inline char sdsReqType(size_t string_size) {
-
if (string_size < 1<<5)
-
return SDS_TYPE_5;
-
if (string_size < 1<<8)
-
return SDS_TYPE_8;
-
if (string_size < 1<<16)
-
return SDS_TYPE_16;
-
#if (LONG_MAX == LLONG_MAX)
-
if (string_size < 1ll<<32)
-
return SDS_TYPE_32;
-
#endif
-
return SDS_TYPE_64;
-
}
-
sds sdsnewlen(const void *init, size_t initlen) {
-
void *sh;
-
sds s;
-
char type = sdsReqType(initlen);
-
/* Empty strings are usually created in order to append. Use type 8
-
* since type 5 is not good at this. */
-
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
-
int hdrlen = sdsHdrSize(type);
-
unsigned char *fp; /* flags pointer. */
-
-
sh = s_malloc(hdrlen+initlen+1);
-
if (!init)
-
memset(sh, 0, hdrlen+initlen+1);
-
if (sh == NULL) return NULL;
-
s = (char*)sh+hdrlen;
-
fp = ((unsigned char*)s)-1;
-
switch(type) {
-
case SDS_TYPE_5: {
-
*fp = type | (initlen << SDS_TYPE_BITS);
-
break;
-
}
-
case SDS_TYPE_8: {
-
SDS_HDR_VAR(8,s);
-
sh->len = initlen;
-
sh->alloc = initlen;
-
*fp = type;
-
break;
-
}
-
case SDS_TYPE_16: {
-
SDS_HDR_VAR(16,s);
-
sh->len = initlen;
-
sh->alloc = initlen;
-
*fp = type;
-
break;
-
}
-
case SDS_TYPE_32: {
-
SDS_HDR_VAR(32,s);
-
sh->len = initlen;
-
sh->alloc = initlen;
-
*fp = type;
-
break;
-
}
-
case SDS_TYPE_64: {
-
SDS_HDR_VAR(64,s);
-
sh->len = initlen;
-
sh->alloc = initlen;
-
*fp = type;
-
break;
-
}
-
}
-
if (initlen && init)
-
memcpy(s, init, initlen);
-
s[initlen] = '\0';
-
return s;
-
}
当给一个已知的sds串添加可用空间时,需要考虑扩充之后的类型与原来的类型是否一致
-
sds sdsMakeRoomFor(sds s, size_t addlen) {
-
void *sh, *newsh;
-
size_t avail = sdsavail(s);
-
size_t len, newlen;
-
char type, oldtype = s[-1] & SDS_TYPE_MASK;
-
int hdrlen;
-
-
if (avail >= addlen) return s;
-
-
len = sdslen(s);
-
sh = (char*)s-sdsHdrSize(oldtype);
-
newlen = (len+addlen);
-
if (newlen < SDS_MAX_PREALLOC)
-
newlen *= 2;
-
else
-
newlen += SDS_MAX_PREALLOC;
-
-
type = sdsReqType(newlen);
-
-
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
-
-
hdrlen = sdsHdrSize(type);
-
if (oldtype==type) {
-
newsh = s_realloc(sh, hdrlen+newlen+1);
-
if (newsh == NULL) return NULL;
-
s = (char*)newsh+hdrlen;
-
} else {
-
-
newsh = s_malloc(hdrlen+newlen+1);
-
if (newsh == NULL) return NULL;
-
memcpy((char*)newsh+hdrlen, s, len+1);
-
s_free(sh);
-
s = (char*)newsh+hdrlen;
-
s[-1] = type;
-
sdssetlen(s, len);
-
}
-
sdssetalloc(s, newlen);
-
return s;
-
}
移除空闲空间时,也需要考虑到类型的转换,这里需要注意的是它并没有严格的根据类型来进行realloc,在if里面直接realloc完成copy工作,else里才用memcpy,提升效率~~~
-
sds sdsRemoveFreeSpace(sds s) {
-
void *sh, *newsh;
-
char type, oldtype = s[-1] & SDS_TYPE_MASK;
-
int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
-
size_t len = sdslen(s);
-
sh = (char*)s-oldhdrlen;
-
-
type = sdsReqType(len);
-
hdrlen = sdsHdrSize(type);
-
-
if (oldtype==type || type > SDS_TYPE_8) {
-
newsh = s_realloc(sh, oldhdrlen+len+1);
-
if (newsh == NULL) return NULL;
-
s = (char*)newsh+oldhdrlen;
-
} else {
-
newsh = s_malloc(hdrlen+len+1);
-
if (newsh == NULL) return NULL;
-
memcpy((char*)newsh+hdrlen, s, len+1);
-
s_free(sh);
-
s = (char*)newsh+hdrlen;
-
s[-1] = type;
-
sdssetlen(s, len);
-
}
-
sdssetalloc(s, len);
-
return s;
-
}
其打印函数有两个版本,一版是借助于vsnprintf实现的,相对较慢。
-
sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
-
va_list cpy;
-
char staticbuf[1024], *buf = staticbuf, *t;
-
size_t buflen = strlen(fmt)*2;
-
-
/* We try to start using a static buffer for speed.
-
* If not possible we revert to heap allocation. */
-
if (buflen > sizeof(staticbuf)) {
-
buf = s_malloc(buflen);
-
if (buf == NULL) return NULL;
-
} else {
-
buflen = sizeof(staticbuf);
-
}
-
-
/* Try with buffers two times bigger every time we fail to
-
* fit the string in the current buffer size. */
-
while(1) {
-
buf[buflen-2] = '\0';
-
va_copy(cpy,ap);
-
vsnprintf(buf, buflen, fmt, cpy);
-
va_end(cpy);
-
if (buf[buflen-2] != '\0') {
-
if (buf != staticbuf) s_free(buf);
-
buflen *= 2;
-
buf = s_malloc(buflen);
-
if (buf == NULL) return NULL;
-
continue;
-
}
-
break;
-
}
-
-
/* Finally concat the obtained string to the SDS string and return it. */
-
t = sdscat(s, buf);
-
if (buf != staticbuf) s_free(buf);
-
return t;
-
}
另一个版本比较快,但是仅仅能够处理几个模式
-
sds sdscatfmt(sds s, char const *fmt, ...) {
-
size_t initlen = sdslen(s);
-
const char *f = fmt;
-
long i;
-
va_list ap;
-
-
va_start(ap,fmt);
-
f = fmt; /* Next format specifier byte to process. */
-
i = initlen; /* Position of the next byte to write to dest str. */
-
while(*f) {
-
char next, *str;
-
size_t l;
-
long long num;
-
unsigned long long unum;
-
-
/* Make sure there is always space for at least 1 char. */
-
if (sdsavail(s)==0) {
-
s = sdsMakeRoomFor(s,1);
-
}
-
-
switch(*f) {
-
case '%':
-
next = *(f+1);
-
f++;
-
switch(next) {
-
case 's':
-
case 'S':
-
str = va_arg(ap,char*);
-
l = (next == 's') ? strlen(str) : sdslen(str);
-
if (sdsavail(s) < l) {
-
s = sdsMakeRoomFor(s,l);
-
}
-
memcpy(s+i,str,l);
-
sdsinclen(s,l);
-
i += l;
-
break;
-
case 'i':
-
case 'I':
-
if (next == 'i')
-
num = va_arg(ap,int);
-
else
-
num = va_arg(ap,long long);
-
{
-
char buf[SDS_LLSTR_SIZE];
-
l = sdsll2str(buf,num);
-
if (sdsavail(s) < l) {
-
s = sdsMakeRoomFor(s,l);
-
}
-
memcpy(s+i,buf,l);
-
sdsinclen(s,l);
-
i += l;
-
}
-
break;
-
case 'u':
-
case 'U':
-
if (next == 'u')
-
unum = va_arg(ap,unsigned int);
-
else
-
unum = va_arg(ap,unsigned long long);
-
{
-
char buf[SDS_LLSTR_SIZE];
-
l = sdsull2str(buf,unum);
-
if (sdsavail(s) < l) {
-
s = sdsMakeRoomFor(s,l);
-
}
-
memcpy(s+i,buf,l);
-
sdsinclen(s,l);
-
i += l;
-
}
-
break;
-
default: /* Handle %% and generally %<unknown>. */
-
s[i++] = next;
-
sdsinclen(s,1);
-
break;
-
}
-
break;
-
default:
-
s[i++] = *f;
-
sdsinclen(s,1);
-
break;
-
}
-
f++;
-
}
-
va_end(ap);
-
-
/* Add null-term */
-
s[i] = '\0';
-
return s;
-
}
这边trim函数是用memmove实现的,cset是一个字符集
-
sds sdstrim(sds s, const char *cset) {
-
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 > sp && strchr(cset, *ep)) ep--;
-
len = (sp > ep) ? 0 : ((ep-sp)+1);
-
if (s != sp) memmove(s, sp, len);
-
s[len] = '\0';
-
sdssetlen(s,len);
-
return s;
-
}
剩下的一堆就是通常的cat,split等的一堆函数,列出来太占地方了,就是用之前的一些基本函数来实现的,这里不一一表示了~~~
写在2018年末:
最开始要坚持写博客是因为今年上半年准备换工作的事情,看了好多资料都说要显得逼格高一点最好就要有自己的博客,后来换到帝都当码农之后,觉得有些东西还是要按照自己的理解经常记录下来,没想到,有点懒散的自己还能够坚持一周一更到现在。觉得这种事自己给自己的一种内心的认同吧,越来越觉得构建自己的知识体系是多么的重要,同样一篇文章,两个不同的人读,效果可能就差的非常大,慢慢再努力吧~~~再有就是如果想要熟练某项技能,一定要经常用到(用体育圈的话来说就是“一天不练,自己知道;三天不练,教练知道;一周不练,大家都知道。”)。最后还是要恭祝大家新年快乐~~~
阅读(8026) | 评论(0) | 转发(0) |