SDS 链表

发布时间:2017-7-1 11:21:19编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SDS 链表 ",主要涉及到SDS 链表 方面的内容,对于SDS 链表 感兴趣的同学可以参考一下。

sds定义

struct sdshdr{

int len

int free

char buf[]

}

sds和c语言类似,仍然把字符串的末尾加上一个‘、0’,但是不会计入总长度,也就是不会对len造成影响,属于默认的,对使用者来说是透明的

根据这个数据的定义,我们可以判断出sds和c字符串的区别

(1)获取len长度的时间复杂度不一样,一个是O(N),一个是O(1),

(2)杜绝缓冲区的溢出:对于c字符串,由于不会记录长度,所有可以造成溢出,比如我们说的strcat之类的,必须事先由使用者malloc出足够的空间,但是sds在追加的时候,会自动检查长度,如果长度不够的话,会自动扩展空间,类似vector,这样就杜绝了缓冲区溢出的情况

(3)减少了字符穿改变时候重新分配内部的次数,比如我们在c中,如果加长一个字符串或则缩短一个字符串的话,我们都需要重新分配空间但是sds对字符串的修改做了一些优化

 

sds字符串的冲分配优化

(1)空间预分配:如果增加字符串的时候,我们的空间不够用了,我们会重新分配,如果sds的长度小雨1MB,如果字符串的长度为len的话,我们我们将len=free=len,buf的长度为2×len+1

如果字符串大于1MB,那么我们的free设置为1mb,则buf=len+1mb+1

综上所述,我们可以减少redis字符串增加长度的分配次数

(2惰性空间释放):如果需要缩短字符串的话,我们不会将空间释放,而是将这些记录到free中,这样的话以以后可以使用

二进制安全:

c字符串只能保存文本,但是sds可以保存视频图片之类的二进制数据,不会因为遇到终止符而停止传输,因为sds是通过len的长度判断终止的,不是针对‘\0’

 

typedef struct list {    // 表头节点    listNode *head;    // 表尾节点    listNode *tail;    // 链表所包含的节点数量    unsigned long len;    // 节点值复制函数    void *(*dup)(void *ptr);    // 节点值释放函数    void (*free)(void *ptr);    // 节点值对比函数    int (*match)(void *ptr, void *key);} list;s
上面就是链表的定义,
根据定义我们可以总结几个特点
1:双端:自带后置和前置节点,这样或者前后node的时间复杂度就是1,大大的降低了时间复杂度
2:无环:第一个节点的前置和最后一个节点的后置指向的都是NULL,所以他不是一个环
3:带有表头指针和表尾指针(见定义)
4:带len:和sds类似,获得长度的时间复杂度为1
5:多态:节点通过上面三个void×类型的处理节点,复制,释放,对比,可以处理多种类型
typedef struct listNode {    // 前置节点    struct listNode *prev;    // 后置节点    struct listNode *next;    // 节点的值    void *value;} listNode;
链表的应用地方很多,比如列表键的底层实现就是链表,
链表的节点数据结构定义就是上面的定义,每一个节点都有一个前置后置指针,



上一篇:Systemed systemctl 创建服务 详解
下一篇:第0课 从0开始

相关文章

关键词: SDS 链表

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款