Redis source Concise Analysis 02 - SDS String

Yano Nankai 2021-11-25 17:11:42
redis source concise analysis sds

C La fonction chaîne de la langue

C Langues string Fonctions,In C Disponible dans la langue char* Chaîne d'implémentation du tableau de caractères,C Bibliothèque de normes linguistiques string.h Plusieurs fonctions de manipulation de chaînes sont également définies dans.

Les chaînes sont largement utilisées,Besoins à satisfaire:

  • Fonctionnement efficace des chaînes,Comme ajouter、Copie、Comparaison、Obtenir la longueur
  • Capable de stocker des données binaires arbitraires,Comme des photos.
  • Économisez autant de mémoire que possible

Pourquoi Redis Ne pas utiliser directement C La chaîne de la langue?

  • C Langues char* Par '\0'Fin de la chaîne d'identification,Il y a'\0'La chaîne pour ne pas être correctement représentée;C'est pour ça.,Il n'y a aucun moyen de sauvegarder des données binaires comme des images.
  • C Langues char* La complexité temporelle pour obtenir la longueur de la chaîne est O(N);La complexité temporelle des chaînes supplémentaires est également O(N),Et peut - être parce qu'il n'y a pas assez d'espace disponible,Impossible d'ajouter.

Le code suivant montre C Dans la langue '\0' Effet du caractère de fin sur la chaîne.La figure ci - dessous montre une valeur de "Redis" De C String:

#include "stdio.h"
#include "string.h"
int main(void) {
char *a = "red\0is";
char *b = "redis\0";
printf("%lu\n", strlen(a));
printf("%lu\n", strlen(b));
}

Le résultat est 3 Et 5.

SDS Définition

SDS(Simple chaîne dynamique) - Oui. simple dynamic string Abréviations,Redis Utiliser SDS Structure des données en tant que chaîne.Redis Toutes les clés(key)Le rez - de - chaussée est SDS Réalisé.

Par exemple,:

redis> SET msg "hello world"
OK
redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

Redis sds Le code source se trouve principalement dans sds.h Et sds.c Moyenne.On y trouve Redis Voilà. char* Alias.:

typedef char *sds;

SDS Structure interne

SDS Il y a une Métadonnée dans la structure flags,Ça veut dire SDS Type(Minimum 3 Bits).En fait,SDS C'est fait. 5 Type d'espèce,Respectivement. sdshdr5、sdshdr8、sdshdr16、sdshdr32 Et sdshdr64.Voilà. 5 La principale différence entre les types est que,La longueur actuelle du tableau de caractères dans leur structure de données len Et la longueur de l'espace alloué alloc,Les deux métadonnées ont des types de données différents.

/* 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[];
};

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;
}

Obtenir la capacité restante:sdsavail Fonctions,Capacité totale alloc - Longueur utilisée len,La complexité temporelle est O(1).

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 Fonctionnement principal de API

L'approche de base est:

sds sdsnewlen(const void *init, size_t initlen);
sds sdstrynewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t len);
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);
sds sdscatvprintf(sds s, const char *fmt, va_list ap);
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
__attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif
sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdssubstr(sds s, size_t start, size_t len);
void sdsrange(sds s, ssize_t start, ssize_t end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);
/* Callback for sdstemplate. The function gets called by sdstemplate
* every time a variable needs to be expanded. The variable name is
* provided as variable, and the callback is expected to return a
* substitution value. Returning a NULL indicates an error.
*/
typedef sds (*sdstemplate_callback_t)(const sds variable, void *arg);
sds sdstemplate(const char *template, sdstemplate_callback_t cb_func, void *cb_arg);
/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, ssize_t incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);
/* Export the allocator used by SDS to the program using SDS.
* Sometimes the program SDS is linked to, may use a different set of
* allocators, but may want to allocate or free things that SDS will
* respectively free or allocate. */
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

Initialisation des chaînes

Total et Java De StringBuilder C'est très similaire. O_o

/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}

Le premier est de juger l'entrée init Longueur de la chaîne,Puis appelez sdsnewlen Allouer de l'espace mémoire et assigner des valeurs.

sds sdsnewlen(const void *init, size_t initlen) {
return _sdsnewlen(init, initlen, 0);
}

Fonctions de base_sdsnewlen Comme suit,Il s'agit avant tout de s'assurer que l'espace est suffisant、Espace alloué,Puis appelez memcpy Oui. *init Copier dans l'espace mémoire correspondant.

/* 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.
* If SDS_NOINIT is used, the buffer is left uninitialized;
*
* 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, int trymalloc) {
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. */
size_t usable;
assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
sh = trymalloc?
s_trymalloc_usable(hdrlen+initlen+1, &usable) :
s_malloc_usable(hdrlen+initlen+1, &usable);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
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 = usable;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}

Redis Série d'analyse concise du code source

Le plus simple Redis Série d'articles sur l'analyse des sources

Java Idées de programmation-Carte mentale la plus complète-GitHub Télécharger le lien,Les petits partenaires qui en ont besoin peuvent s'en servir.~

L'originalité n'est pas facile,J'espère que vous me contacterez d'abord pour la réimpression.,Et annoter le lien original.

版权声明
本文为[Yano Nankai]所创,转载请带上原文链接,感谢
https://javamana.com/2021/11/20211125165636688h.html

  1. 应急响应入门之Linux分析排查
  2. Twitter如何升级Hadoop+Kafka架构实现实时处理数十亿个事件?
  3. 引人入胜,实战讲解“Java性能调优六大工具”之linux命令行工具
  4. docker 查看实时日志
  5. JFrog Artifactory 7.27 上传应用到私服和从maven私服下载制品
  6. Ces protocoles http simples
  7. [including thesis + source code] JavaWeb hospital triage registration management system SSH [package running successfully]
  8. Java初学者,想知道如何用if语法当条件成立后什么都不执行,否则执行动作
  9. 体验.NET Core使用IKVM对接Java
  10. 深入JavaScript高级语法-coderwhy
  11. 排序算法--Java实例/原理
  12. 停止docker时报错:Warning: Stopping docker.service, but it can still be activated by: docker.socket
  13. 【完整示例】采用jenkins pipeline实现自动构建并部署至k8s
  14. 【Linux】腾讯云服务器,使用FRP内网穿透,端口映射,远程访问内网ubuntu机器
  15. 关于#java#的问题:resultMap type映射不到我想要的类 只能映射java的内部类 加了全路径也映射不了 怎么解决
  16. 排序算法--Java實例/原理
  17. 就这一次,阿里最新出品源码阅读指南,一套搞定JDK+vm源码
  18. 两个小时手写了个Zookeeper分布式服务注册中心
  19. Algorithme de tri - - instance / principe Java
  20. Plongez dans la syntaxe avancée javascript - coderwhy
  21. JavaScript高级程序设计读后感(一)之零碎知识点查漏补缺
  22. 先到先学!Alibaba甩出第四次更新的JDK源码高级笔记(终极版)
  23. Java File类
  24. How To Install MariaDB on linux
  25. #yyds干货盘点# Mybatis 的 XML 配置
  26. Spring认证中国教育管理中心-Spring Data MongoDB教程七
  27. Linux进程和任务管理
  28. Linux文件系统日志分析
  29. Redis-客户端-重点知识
  30. Redis-事件-重点知识
  31. Redis-AOF持久化-重点知识
  32. Redis-RDB持久化-重点知识
  33. http://lx.gongxuanwang.com/sszt/32.htm
  34. 回顾我两个月面试阿里,携程,小红书,美团,网易等等(Java岗)
  35. JavaScript高级程序设计读后感(一)之零碎知识点查漏补缺
  36. Rocketmq source code analysis: message sending process
  37. Rocketmq source code analysis: how does rocketmq store messages?
  38. RocketMQ source analysis: how to debug the RocketMQ source in IDEA
  39. How To Install MariaDB on linux
  40. Comment installer mariadb sur Linux
  41. http://lx.gongxuanwang.com/sszt/7.htm
  42. Classe de fichiers Java
  43. Premier arrivé, premier servi! Alibaba lance la quatrième mise à jour de JDK source Advanced notes (Ultimate)
  44. #yyds干货盘点#设计模式之【工厂模式】
  45. Java * SpringBoot实现万能文件在线预览,已开源,真香
  46. Redis | 第4章 Redis中的数据库《Redis设计与实现》
  47. Liang Tingwei's first variety show of "director, please give advice" reshapes the classic work "spring of a new town"
  48. Redis | 第4章 Redis中的数据库《Redis设计与实现》
  49. 关于centos docker版本过低导致 is not a valid repository/tag: invalid reference format
  50. Redis 源码简洁剖析 02 - SDS 字符串
  51. 回顧我兩個月面試阿裏,攜程,小紅書,美團,網易等等(Java崗)
  52. Rétrospectivement, j'ai passé deux mois à interviewer Ali, ctrip, Little Red Book, meituan, NetEase, etc. (Java post)
  53. Docker + webhook Automation Deployment Front End Project
  54. Java技术之Spring、Hibernate框架整合方法
  55. http://lx.gongxuanwang.com/sszt/32.htm
  56. 亚马逊自己的 Linux 发行版现在完全基于 Fedora 了
  57. Redis 源码简洁剖析 02 - SDS 字符串
  58. Java技術之Spring、Hibernate框架整合方法
  59. Méthode d'intégration des cadres de printemps et d'hibernation de la technologie Java
  60. Redis source Concise Analysis 02 - SDS String