Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1879325
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: NOSQL

2018-12-31 20:25:15

放假在家,本想偷个懒,但还是觉得应该给2018一个交代,就扯扯这个吧~
由于redis是用纯c写的,所以没有string那么高端的东西,所以它就自己实现了一个动态字符串的库,用于字符串处理,就是这个SDSLib了~~~
在sdsalloc.h文件中,使用宏定义转换了如下几个函数

点击(此处)折叠或打开

  1. #include "zmalloc.h"
  2. #define s_malloc zmalloc
  3. #define s_realloc zrealloc
  4. #define s_free zfree


在这里先定义了一堆结构体sdshdrxx, 其中struct 关键字后面的`__attribute__ ((__packed__))`表示该结构体再存储时,不用考虑字节对齐。除了sdshdr5之外均有len成员表示已经占用的长度,alloc成员表示实际分配给字符串的长度。注意,这里的len和alloc的类型决定了该类sds最多可以存储多少个字符

点击(此处)折叠或打开

  1. typedef char *sds;

  2. /* Note: sdshdr5 is never used, we just access the flags byte directly.
  3.  * However is here to document the layout of type 5 SDS strings. */
  4. struct __attribute__ ((__packed__)) sdshdr5 {
  5.     unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
  6.     char buf[];
  7. };
  8. struct __attribute__ ((__packed__)) sdshdr8 {
  9.     uint8_t len; /* used */
  10.     uint8_t alloc; /* excluding the header and null terminator */
  11.     unsigned char flags; /* 3 lsb of type, 5 unused bits */
  12.     char buf[];
  13. };
  14. struct __attribute__ ((__packed__)) sdshdr16 {
  15.     uint16_t len; /* used */
  16.     uint16_t alloc; /* excluding the header and null terminator */
  17.     unsigned char flags; /* 3 lsb of type, 5 unused bits */
  18.     char buf[];
  19. };
  20. struct __attribute__ ((__packed__)) sdshdr32 {
  21.     uint32_t len; /* used */
  22.     uint32_t alloc; /* excluding the header and null terminator */
  23.     unsigned char flags; /* 3 lsb of type, 5 unused bits */
  24.     char buf[];
  25. };
  26. struct __attribute__ ((__packed__)) sdshdr64 {
  27.     uint64_t len; /* used */
  28.     uint64_t alloc; /* excluding the header and null terminator */
  29.     unsigned char flags; /* 3 lsb of type, 5 unused bits */
  30.     char buf[];
  31. };
紧接着,又定义了一些宏来定义如何获取对应结构体里的相关信息,这里遵循的原则就是s指向实际使用的字符串首地址,s的前面就是对应的结构体的头部。这里面比较奇怪(或者说我暂时没看懂)的地方就是结构体里面命名定义了flags成员,但是实际取flags的时候,都是直接用s[-1]来存取,其他的变量倒是都用变量名来获取,要是有大侠知道,还请不吝赐教

点击(此处)折叠或打开

  1. #define SDS_TYPE_5 0
  2. #define SDS_TYPE_8 1
  3. #define SDS_TYPE_16 2
  4. #define SDS_TYPE_32 3
  5. #define SDS_TYPE_64 4
  6. #define SDS_TYPE_MASK 7
  7. #define SDS_TYPE_BITS 3
  8. #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
  9. #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
  10. #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
下面几个函数分别获取成员变量len、剩余空间,设置len、增加len,获取alloc,设置alloc,套路都差不多,这里仅给出获取len和获取可用空间的代码,其余的非常类似

点击(此处)折叠或打开

  1. static inline size_t sdslen(const sds s) {
  2.     unsigned char flags = s[-1];
  3.     switch(flags&SDS_TYPE_MASK) {
  4.         case SDS_TYPE_5:
  5.             return SDS_TYPE_5_LEN(flags);
  6.         case SDS_TYPE_8:
  7.             return SDS_HDR(8,s)->len;
  8.         case SDS_TYPE_16:
  9.             return SDS_HDR(16,s)->len;
  10.         case SDS_TYPE_32:
  11.             return SDS_HDR(32,s)->len;
  12.         case SDS_TYPE_64:
  13.             return SDS_HDR(64,s)->len;
  14.     }
  15.     return 0;
  16. }
  17. static inline size_t sdsavail(const sds s) {
  18.     unsigned char flags = s[-1];
  19.     switch(flags&SDS_TYPE_MASK) {
  20.         case SDS_TYPE_5: {
  21.             return 0;
  22.         }
  23.         case SDS_TYPE_8: {
  24.             SDS_HDR_VAR(8,s);
  25.             return sh->alloc - sh->len;
  26.         }
  27.         case SDS_TYPE_16: {
  28.             SDS_HDR_VAR(16,s);
  29.             return sh->alloc - sh->len;
  30.         }
  31.         case SDS_TYPE_32: {
  32.             SDS_HDR_VAR(32,s);
  33.             return sh->alloc - sh->len;
  34.         }
  35.         case SDS_TYPE_64: {
  36.             SDS_HDR_VAR(64,s);
  37.             return sh->alloc - sh->len;
  38.         }
  39.     }
  40.     return 0;
  41. }
当创建一个新的sds串时,会根据请求大小来分配不同类型,如果传入指针和长度均存在,则memcpy

点击(此处)折叠或打开

  1. static inline char sdsReqType(size_t string_size) {
  2.     if (string_size < 1<<5)
  3.         return SDS_TYPE_5;
  4.     if (string_size < 1<<8)
  5.         return SDS_TYPE_8;
  6.     if (string_size < 1<<16)
  7.         return SDS_TYPE_16;
  8. #if (LONG_MAX == LLONG_MAX)
  9.     if (string_size < 1ll<<32)
  10.         return SDS_TYPE_32;
  11. #endif
  12.     return SDS_TYPE_64;
  13. }
  14. sds sdsnewlen(const void *init, size_t initlen) {
  15.     void *sh;
  16.     sds s;
  17.     char type = sdsReqType(initlen);
  18.     /* Empty strings are usually created in order to append. Use type 8
  19.      * since type 5 is not good at this. */
  20.     if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
  21.     int hdrlen = sdsHdrSize(type);
  22.     unsigned char *fp; /* flags pointer. */

  23.     sh = s_malloc(hdrlen+initlen+1);
  24.     if (!init)
  25.         memset(sh, 0, hdrlen+initlen+1);
  26.     if (sh == NULL) return NULL;
  27.     s = (char*)sh+hdrlen;
  28.     fp = ((unsigned char*)s)-1;
  29.     switch(type) {
  30.         case SDS_TYPE_5: {
  31.             *fp = type | (initlen << SDS_TYPE_BITS);
  32.             break;
  33.         }
  34.         case SDS_TYPE_8: {
  35.             SDS_HDR_VAR(8,s);
  36.             sh->len = initlen;
  37.             sh->alloc = initlen;
  38.             *fp = type;
  39.             break;
  40.         }
  41.         case SDS_TYPE_16: {
  42.             SDS_HDR_VAR(16,s);
  43.             sh->len = initlen;
  44.             sh->alloc = initlen;
  45.             *fp = type;
  46.             break;
  47.         }
  48.         case SDS_TYPE_32: {
  49.             SDS_HDR_VAR(32,s);
  50.             sh->len = initlen;
  51.             sh->alloc = initlen;
  52.             *fp = type;
  53.             break;
  54.         }
  55.         case SDS_TYPE_64: {
  56.             SDS_HDR_VAR(64,s);
  57.             sh->len = initlen;
  58.             sh->alloc = initlen;
  59.             *fp = type;
  60.             break;
  61.         }
  62.     }
  63.     if (initlen && init)
  64.         memcpy(s, init, initlen);
  65.     s[initlen] = '\0';
  66.     return s;
  67. }

当给一个已知的sds串添加可用空间时,需要考虑扩充之后的类型与原来的类型是否一致

点击(此处)折叠或打开

  1. sds sdsMakeRoomFor(sds s, size_t addlen) {
  2.     void *sh, *newsh;
  3.     size_t avail = sdsavail(s);
  4.     size_t len, newlen;
  5.     char type, oldtype = s[-1] & SDS_TYPE_MASK;
  6.     int hdrlen;

  7.     if (avail >= addlen) return s;

  8.     len = sdslen(s);
  9.     sh = (char*)s-sdsHdrSize(oldtype);
  10.     newlen = (len+addlen);
  11.     if (newlen < SDS_MAX_PREALLOC)
  12.         newlen *= 2;
  13.     else
  14.         newlen += SDS_MAX_PREALLOC;

  15.     type = sdsReqType(newlen);

  16.     if (type == SDS_TYPE_5) type = SDS_TYPE_8;

  17.     hdrlen = sdsHdrSize(type);
  18.     if (oldtype==type) {
  19.         newsh = s_realloc(sh, hdrlen+newlen+1);
  20.         if (newsh == NULL) return NULL;
  21.         s = (char*)newsh+hdrlen;
  22.     } else {

  23.         newsh = s_malloc(hdrlen+newlen+1);
  24.         if (newsh == NULL) return NULL;
  25.         memcpy((char*)newsh+hdrlen, s, len+1);
  26.         s_free(sh);
  27.         s = (char*)newsh+hdrlen;
  28.         s[-1] = type;
  29.         sdssetlen(s, len);
  30.     }
  31.     sdssetalloc(s, newlen);
  32.     return s;
  33. }
移除空闲空间时,也需要考虑到类型的转换,这里需要注意的是它并没有严格的根据类型来进行realloc,在if里面直接realloc完成copy工作,else里才用memcpy,提升效率~~~

点击(此处)折叠或打开

  1. sds sdsRemoveFreeSpace(sds s) {
  2.     void *sh, *newsh;
  3.     char type, oldtype = s[-1] & SDS_TYPE_MASK;
  4.     int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
  5.     size_t len = sdslen(s);
  6.     sh = (char*)s-oldhdrlen;

  7.     type = sdsReqType(len);
  8.     hdrlen = sdsHdrSize(type);

  9.     if (oldtype==type || type > SDS_TYPE_8) {
  10.         newsh = s_realloc(sh, oldhdrlen+len+1);
  11.         if (newsh == NULL) return NULL;
  12.         s = (char*)newsh+oldhdrlen;
  13.     } else {
  14.         newsh = s_malloc(hdrlen+len+1);
  15.         if (newsh == NULL) return NULL;
  16.         memcpy((char*)newsh+hdrlen, s, len+1);
  17.         s_free(sh);
  18.         s = (char*)newsh+hdrlen;
  19.         s[-1] = type;
  20.         sdssetlen(s, len);
  21.     }
  22.     sdssetalloc(s, len);
  23.     return s;
  24. }

其打印函数有两个版本,一版是借助于vsnprintf实现的,相对较慢。

点击(此处)折叠或打开

  1. sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
  2.     va_list cpy;
  3.     char staticbuf[1024], *buf = staticbuf, *t;
  4.     size_t buflen = strlen(fmt)*2;

  5.     /* We try to start using a static buffer for speed.
  6.      * If not possible we revert to heap allocation. */
  7.     if (buflen > sizeof(staticbuf)) {
  8.         buf = s_malloc(buflen);
  9.         if (buf == NULL) return NULL;
  10.     } else {
  11.         buflen = sizeof(staticbuf);
  12.     }

  13.     /* Try with buffers two times bigger every time we fail to
  14.      * fit the string in the current buffer size. */
  15.     while(1) {
  16.         buf[buflen-2] = '\0';
  17.         va_copy(cpy,ap);
  18.         vsnprintf(buf, buflen, fmt, cpy);
  19.         va_end(cpy);
  20.         if (buf[buflen-2] != '\0') {
  21.             if (buf != staticbuf) s_free(buf);
  22.             buflen *= 2;
  23.             buf = s_malloc(buflen);
  24.             if (buf == NULL) return NULL;
  25.             continue;
  26.         }
  27.         break;
  28.     }

  29.     /* Finally concat the obtained string to the SDS string and return it. */
  30.     t = sdscat(s, buf);
  31.     if (buf != staticbuf) s_free(buf);
  32.     return t;
  33. }
另一个版本比较快,但是仅仅能够处理几个模式

点击(此处)折叠或打开

  1. sds sdscatfmt(sds s, char const *fmt, ...) {
  2.     size_t initlen = sdslen(s);
  3.     const char *f = fmt;
  4.     long i;
  5.     va_list ap;

  6.     va_start(ap,fmt);
  7.     f = fmt; /* Next format specifier byte to process. */
  8.     i = initlen; /* Position of the next byte to write to dest str. */
  9.     while(*f) {
  10.         char next, *str;
  11.         size_t l;
  12.         long long num;
  13.         unsigned long long unum;

  14.         /* Make sure there is always space for at least 1 char. */
  15.         if (sdsavail(s)==0) {
  16.             s = sdsMakeRoomFor(s,1);
  17.         }

  18.         switch(*f) {
  19.         case '%':
  20.             next = *(f+1);
  21.             f++;
  22.             switch(next) {
  23.             case 's':
  24.             case 'S':
  25.                 str = va_arg(ap,char*);
  26.                 l = (next == 's') ? strlen(str) : sdslen(str);
  27.                 if (sdsavail(s) < l) {
  28.                     s = sdsMakeRoomFor(s,l);
  29.                 }
  30.                 memcpy(s+i,str,l);
  31.                 sdsinclen(s,l);
  32.                 i += l;
  33.                 break;
  34.             case 'i':
  35.             case 'I':
  36.                 if (next == 'i')
  37.                     num = va_arg(ap,int);
  38.                 else
  39.                     num = va_arg(ap,long long);
  40.                 {
  41.                     char buf[SDS_LLSTR_SIZE];
  42.                     l = sdsll2str(buf,num);
  43.                     if (sdsavail(s) < l) {
  44.                         s = sdsMakeRoomFor(s,l);
  45.                     }
  46.                     memcpy(s+i,buf,l);
  47.                     sdsinclen(s,l);
  48.                     i += l;
  49.                 }
  50.                 break;
  51.             case 'u':
  52.             case 'U':
  53.                 if (next == 'u')
  54.                     unum = va_arg(ap,unsigned int);
  55.                 else
  56.                     unum = va_arg(ap,unsigned long long);
  57.                 {
  58.                     char buf[SDS_LLSTR_SIZE];
  59.                     l = sdsull2str(buf,unum);
  60.                     if (sdsavail(s) < l) {
  61.                         s = sdsMakeRoomFor(s,l);
  62.                     }
  63.                     memcpy(s+i,buf,l);
  64.                     sdsinclen(s,l);
  65.                     i += l;
  66.                 }
  67.                 break;
  68.             default: /* Handle %% and generally %<unknown>. */
  69.                 s[i++] = next;
  70.                 sdsinclen(s,1);
  71.                 break;
  72.             }
  73.             break;
  74.         default:
  75.             s[i++] = *f;
  76.             sdsinclen(s,1);
  77.             break;
  78.         }
  79.         f++;
  80.     }
  81.     va_end(ap);

  82.     /* Add null-term */
  83.     s[i] = '\0';
  84.     return s;
  85. }
这边trim函数是用memmove实现的,cset是一个字符集

点击(此处)折叠或打开

  1. sds sdstrim(sds s, const char *cset) {
  2.     char *start, *end, *sp, *ep;
  3.     size_t len;

  4.     sp = start = s;
  5.     ep = end = s+sdslen(s)-1;
  6.     while(sp <= end && strchr(cset, *sp)) sp++;
  7.     while(ep > sp && strchr(cset, *ep)) ep--;
  8.     len = (sp > ep) ? 0 : ((ep-sp)+1);
  9.     if (s != sp) memmove(s, sp, len);
  10.     s[len] = '\0';
  11.     sdssetlen(s,len);
  12.     return s;
  13. }

剩下的一堆就是通常的cat,split等的一堆函数,列出来太占地方了,就是用之前的一些基本函数来实现的,这里不一一表示了~~~










写在2018年末:

最开始要坚持写博客是因为今年上半年准备换工作的事情,看了好多资料都说要显得逼格高一点最好就要有自己的博客,后来换到帝都当码农之后,觉得有些东西还是要按照自己的理解经常记录下来,没想到,有点懒散的自己还能够坚持一周一更到现在。觉得这种事自己给自己的一种内心的认同吧,越来越觉得构建自己的知识体系是多么的重要,同样一篇文章,两个不同的人读,效果可能就差的非常大,慢慢再努力吧~~~再有就是如果想要熟练某项技能,一定要经常用到(用体育圈的话来说就是“一天不练,自己知道;三天不练,教练知道;一周不练,大家都知道。”)。最后还是要恭祝大家新年快乐~~~
阅读(8026) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~