[redis设计与实现][1]基本数据结构——sds

SDS(Simple Dynamic String):对C字符串的封装,可修改、可自动伸缩的字符串实现。Redis默认的字符串实现。

SDS定义:(sds.h)
[cce lang=”c”]
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};
[/cce]

与C字符串的区别:

* 常数复杂度获取字符串长度(字符串长度已经记录在结构体中)
* 杜绝缓冲区溢出(每次操作前都会检查空间是否充足,自动扩张和收缩)
* 减少修改字符串带来的内存重分配次数:
*
* 空间预分配(提前预留空间)
* 惰性空间释放(释放的空间暂时保留,防止扩张)
* 二进制安全(不采用\0表示结束)
* 兼容部分C字符串函数(buf数组多保存了一个\0,用于兼容部分C字符串函数)

API:
typedef char *sds;
创建一个字符串:sds sdsnew(const char *init);
[cce lang=”c”]
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
//根据sdshdr结构分配内存,多一个用来放\0
if (init) {
sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
} else {
sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
}
if (sh == NULL) return NULL;
sh->len = initlen;
sh->free = 0;
//初始字符串不为NULL,复制过去,然后最后补上\0
if (initlen && init)
memcpy(sh->buf, init, initlen);
sh->buf[initlen] = ‘\0′;
return (char*)sh->buf;
}
[/cce]
拼接字符串:sds sdscat(sds s, const char *t);
[cce lang=”c”]
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
size_t curlen = sdslen(s);

s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
sh = (void*) (s-(sizeof(struct sdshdr)));
memcpy(s+curlen, t, len);
sh->len = curlen+len;
sh->free = sh->free-len;
s[curlen+len] = ‘\0′;
return s;
}
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s);
size_t len, newlen;

//仍然有空闲,直接返回
if (free >= addlen) return s;
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
newlen = (len+addlen);
//新的空间比最大分配空间小,扩容两倍
//#define SDS_MAX_PREALLOC (1024*1024)
if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; //重新分配空间:sdshdr+字符串长度+1(\0) newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); if (newsh == NULL) return NULL; newsh->free = newlen – len;
return newsh->buf;
}
static inline size_t sdsavail(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->free;
}
[/cce]

转载自:https://coolex.info/blog/434.html

时间: 2024-10-26 09:17:05

[redis设计与实现][1]基本数据结构——sds的相关文章

[redis设计与实现][7]基本数据结构——对象

Redis对基础数据类型进行了封装,构建出上层的对象系统,这个系统包含:字符串对象.列表对象.哈希对象.集合对象和有序集合对象. Redis对象结构: [cce lang="c"] typedef struct redisObject { //类型 unsigned type:4; //编码 unsigned encoding:4; //LRU时间 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock

[redis设计与实现][4]基本数据结构——跳跃表

Redis使用跳跃表和字典共同来实现有序集合键(sorted set). 定义: 跳跃表节点: [cce lang="c"] typedef struct zskiplistNode { //成员对象 robj *obj; //分值 double score; //后退指针 struct zskiplistNode *backward; //层结构 struct zskiplistLevel { //前进指针 struct zskiplistNode *forward; //跨度 un

[redis设计与实现][3]基本数据结构——字典

Redis字典采用哈希表实现. 哈希表: [cce lang="c"] typedef struct dictht { //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表掩码,用于计算索引值,总是等于size – 1 unsigned long size mask; //已有的节点数量 unsigned long used; } dictht; [/cce] 哈希表节点: [cce lang="c"

[redis设计与实现][6]基本数据结构——压缩列表

压缩列表(ziplist)是列表键和哈希键的底层实现之一. 压缩列表结构: 属性 类型 长度 用途 zlbytes uint32_t 4字节 记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配,或者计算zlend的位置时使用 zltail uint32_t 4字节 记录压缩列表尾节点记录压缩列表的起始地址便宜:用于快速定位尾节点 zllen uint16_t 2字节  记录压缩列表包含的节点数量:当这个值小于UINT64_MAX(65535)时,这个属性的值就是压缩列表包含的节点数量:

[redis设计与实现][5]基本数据结构——整数集合

整数集合(intset)用于集合键.当一个集合只包含整数值元素,并且数量不多的时候,会使用整数集合作为集合键的底层实现.相对于直接保存字符串,整数集合能够很好地节约内存,但是由于是数组保存,需要特别关注数组长度. 定义:(intset.h) [cce lang="c"] typedef struct intset { //编码方式 uint32_t encoding; //集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[]; }

《Redis设计与实现》阅读:Redis底层研究之简单动态字符串SDS

        除仅用于字符串字面量的情况外,对于可以被修改值的字符串的表示,Redis底层并没有采用C语言传统的字符串表示,即以空字符结尾的字符数组,而是采用专门为其设计的简单动态字符串作为其默认字符串表示,其英文全称为Simple Dynamic String,简称SDS.除了用于保存数据库中字符串值外,SDS也可以用于缓冲区buffer,比如AOF中的缓冲区.客户端输入缓冲区等.本文,我们将详细研究简单动态字符串SDS的实现及其在性能等方面的独特之处.             注:内容总结

[redis设计与实现][9]复制

复制(Redis2.8) 设置主服务器的地址和端口(SLAVE OF命令) SLAVEOF host port Redis的主从复制设置非常方便,只需要在从服务器上设置主服务器的IP和端口即可.如果需要关闭主从同步,只需要执行SLAVEOF NO ONE即可. 该命令的具体描述见官方文档 void slaveofCommand(redisClient *c) { // 先处理no one,解除现有的主从同步 if (!strcasecmp(c->argv[1]->ptr,"no&qu

[redis设计与实现][10]sentinel——简介和启动

Sentinel(Redis 3.0.0-rc1) Sentinel是Redis HA方案,一个或多个Sentinel实例组成的Sentinel系统,可以监视任意多个主服务器(master), 以及这些主服务器属下的所有从服务器(slave),并在被监视的主服务器进入下线状态时,自动在将被下线主服务器属下的某个从服务器升级为新的主服务器, 然后由新的主服务器代替已下线的主服务器继续处理命令请求. 基础数据结构 typedef struct sentinelRedisInstance { // 当

《Redis设计与实现》阅读:Redis底层研究之哈希表hashtable

        字典是一种存储键值对的抽象数据结构,其又被称为符号表(symbol table).关联数组(associative array)或映射(map).Redis使用字典存储键值对,而Redis在底层是通过自定义的哈希表来实现字典这一数据结构的.本文,我们将研究Redis中哈希表的实现.         结构         一个哈希表包含多个哈希表节点,每个哈希表节点保存了字典中的一个键值对.在Redis中,哈希表用dictht表示,其结构如下:         其中,