首页 > 其他 > 详细

redis设计与实现总结--简单动态字符串和链表

时间:2021-05-08 16:32:42      阅读:12      评论:0      收藏:0      [点我收藏+]

简单动态字符串(SDS)

技术分享图片

 

struct sdshdr {
    //记录buf数组中已使用字节的数量
    //等于SDS所保存字符串的长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组,用于保存字符串
    char buf[];
}
一般会留最后一个字节来保存‘\0‘,不计算再len中,方便使用c字符串函数
 
为了防止缓冲区异常,每次SDS扩展会先看预留空间是否够,否则另外申请大空间复制,再扩展。
但如果缩短并不会变,只有free的值变。
 
为了避免缓冲区溢出(增长)和内存泄露(缩短)
SDS的空间分配策略
1.空间预分配
当需要增加字符串长度时:
    修改后SDS长度小于1MB,则程序分配和len属性相同大小的未使用空间,这时len=free。
    修改后SDS长度大于1MB,则分配1MB未分配空间。
2.惰性空间释放
    但如果缩短并不会变,只有free的值变。而且提供了相应的API(sdsfree,sdsrange)防止内存浪费。
 
SDSbuf数组内可以保存的是二进制数据,因为不是根据‘\0‘判断,而是根据len长度来判断。
 
对比C字符串,SDS有如下优点:
1.常数复杂度获取字符串长度。
2.杜绝缓冲区溢出。
3.减少修改字符串长度时所需的内存重分配次数。
4.二进制安全。
5.兼容部分C字符串函数。
 

链表

双向无环链表
应用:列表键,发布与订阅,慢查询,监视器等。
技术分享图片

 

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
}listNode;
typedef struct list {
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表所包含的节点数
    unsigned long len;
    //节点复制函数
    void *(*dup)(void *ptr);
        //节点释放函数
        void *(free)(void *ptr);
        //节点对比函数
        inr  *(*match)(void *ptr,void *key);
}list;

技术分享图片

三个函数去实现多态。

redis设计与实现总结--简单动态字符串和链表

原文:https://www.cnblogs.com/2462478392Lee/p/14744944.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!