AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

STL内存管理的C实现

2012-01-10 856
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： //STL 内存管理器的C实现 #include stdio.h> #include stdlib.h> #define __ALIGN 8    //小型区块上调边界 #define __MAX_BYTES 128    //小型区块大小的上限 ...
  1. //STL 内存管理器的C实现

  3. #include stdio.h>
  4. #include stdlib.h>

  6. #define __ALIGN 8    //小型区块上调边界
  7. #define __MAX_BYTES 128    //小型区块大小的上限
  8. #define __NFREELISTS (__ALIGN/__MAX_BYTES)    //free-lists的个数

  10. typedef union obj{
  11.     union obj *free_list_link;
  12.     char client_data[1];
  13. }obj;
  14. obj *free_list[__NFREELISTS];
  15. char *start_free;    //mempool开始位置
  16. char *end_free;    //mempool结束位置
  17. size_t heapsize;

  19. size_t ROUND_UP(size_t bytes);
  20. size_t FREELIST_INDEX(size_t bytes);
  21. void *stl_malloc(size_t nbytes);
  22. void stl_free(void *p, size_t nbytes);
  23. void *refill(size_t n);
  24. char *chunk_alloc(size_t bytes, size_t *nobjs);


  27. int main(){
  28.     int len= 65;
  29.     void *ptr = stl_malloc(len);
  30.     printf("%p\n", ptr);
  31.     stl_free(ptr, len);
  32.     return 0;
  33. }

  35. //将bytes上调到__ALIGN的倍数
  36. size_t ROUND_UP(size_t bytes){
  37.     return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
  38. }
  39. //返回bytes所对应的freelist索引号
  40. size_t FREELIST_INDEX(size_t bytes){
  41.     return ((bytes + __ALIGN - 1) / __ALIGN - 1);
  42. }
  43. void *stl_malloc(size_t nbytes){
  44.     if(nbytes > 128){
  45.         return malloc(nbytes);
  46.     }
  47.     obj **my_free_list;
  48.     obj *result;
  49.     my_free_list = free_list + FREELIST_INDEX(nbytes);
  50.     result = *my_free_list;
  51.     if(result == NULL){
  52.         void *r = refill(ROUND_UP(nbytes));
  53.         return r;
  54.     }
  55.     //取出空闲块
  56.     *my_free_list = result->free_list_link;
  57.     return result;
  58. }
  59. void stl_free(void *p, size_t nbytes){
  60.     obj *q = (obj *)p;
  61.     obj **my_free_list;
  62.     if(nbytes > (size_t)__MAX_BYTES){
  63.         free(p);
  64.         return;
  65.     }
  66.     my_free_list = free_list + FREELIST_INDEX(nbytes);
  67.     q->free_list_link = *my_free_list;
  68.     *my_free_list = q;
  69. }
  70. void *refill(size_t n){
  71.     //默认从内存池取得20个块，多个块构成一个chunk
  72.     size_t nobjs = 20;    //值-结果参数
  73.     char *chunk = chunk_alloc(n, &nobjs);    
  74.     if(!chunk){
  75.         return NULL;
  76.     }
  77.     obj **my_free_list;
  78.     obj *result, *cur_obj, *next_obj;
  79.     int i;
  80.     //内存池空间告急仅返回一个块，则直接返回给用户
  81.     if(nobjs == 1){
  82.         return chunk;
  83.     }
  84.     //否则准备向free_list中纳入新的节点
  85.     my_free_list = free_list + FREELIST_INDEX(n);
  86.     //以下在chunk的连续空间上建立free_list
  87.     result = (obj *)chunk;    //此块返回给用户
  88.     *my_free_list = next_obj = (obj *)(chunk + n);
  89.     for(i = 1; ; i++){
  90.         cur_obj = next_obj;
  91.         next_obj = (obj *)((char *)next_obj + n);
  92.         if(nobjs - 1 == i){
  93.             cur_obj->free_list_link = NULL;
  94.             break;
  95.         }else{
  96.             cur_obj->free_list_link = next_obj;    
  97.         }
  98.     }
  99.     return result;
  100. }
  101. //从内存池取连续的块空间
  102. char *chunk_alloc(size_t bytes, size_t *nobjs){
  103.     char *result;
  104.     size_t total_bytes = bytes * (*nobjs);    //要求的字节数
  105.     size_t bytes_left = end_free - start_free;    //

  107.     //内存池空间宽裕
  108.     if(bytes_left >= total_bytes){
  109.         result = start_free;
  110.         start_free += total_bytes;
  111.         return result;
  112.     }else if(bytes_left >= bytes){
  113.         //不够分配全部的，但是还可以分配一个或多个块
  114.         *nobjs = bytes_left/bytes;
  115.         total_bytes = *nobjs * bytes;
  116.         result = start_free;
  117.         start_free += total_bytes;
  118.         return result;
  119.     }else{
  120.         //内存池黔驴技穷了，连一个块的空间都没有了
  121.         size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heapsize >> 4);
  122.         if(bytes_left > 0){
  123.             //内存池中还有一些零头，先配给适当的free-list
  124.             obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
  125.             ((obj *)start_free)->free_list_link = *my_free_list;
  126.             *my_free_list = (obj *)start_free;
  127.         }
  128.         start_free = (char *)malloc(bytes_to_get);
  129.         if(start_free == NULL){
  130.             //看看更大块的free_list有无可用块
  131.             int i;
  132.             obj **my_free_list, *p;
  133.             for(i = bytes; i = __MAX_BYTES; i += __ALIGN){
  134.                 my_free_list = free_list + FREELIST_INDEX(i);
  135.                 p = *my_free_list;
  136.                 if(p){
  137.                     *my_free_list = p->free_list_link;
  138.                     start_free = (char *)p;
  139.                     end_free = start_free + i;
  140.                     //递归调用自己，按新的状态重新分配，并修正nobjs;
  141.                     return chunk_alloc(bytes, nobjs);
  142.                 }
  143.             }
  144.             //实在没有空间了
  145.             end_free = 0;
  146.             return NULL;
  147.         }
  148.         heapsize += bytes_to_get;
  149.         end_free = start_free + bytes_to_get;
  150.         return chunk_alloc(bytes, nobjs);
  151.     }
  152.     
  153. }
文章标签：
C++
xumaojun
目录
相关文章
AIGC小王子
|
数据采集 自然语言处理 大数据
​「Python大数据」LDA主题分析模型
使用Python进行文本聚类，流程包括读取VOC数据、jieba分词、去除停用词，应用LDA模型（n_components=5）进行主题分析，并通过pyLDAvis生成可视化HTML。关键代码涉及数据预处理、CountVectorizer、LatentDirichletAllocation以及HTML文件的本地化处理。停用词和业务术语列表用于优化分词效果。
AIGC小王子
823 0
​「Python大数据」LDA主题分析模型
bug菌
|
安全 Java 测试技术
🌟Java零基础-反射：从入门到精通
【10月更文挑战第4天】本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，希望能够助你一臂之力，帮你早日登顶实现财富自由🚀；同时，欢迎大家关注&&收藏&&订阅！持续更新中，up！up！up！！
bug菌
187 2
杀死一只知更鸟debug
|
Python
anaconda下载安装，镜像源配置修改及虚拟环境的创建
这篇文章介绍了Anaconda的下载安装过程，包括Anaconda的简介、安装步骤、配置修改、创建虚拟环境以及一些常用命令的使用方法。文章还提供了如何修改conda的镜像源为国内镜像源以加速下载的步骤。
杀死一只知更鸟debug
9896 0
anaconda下载安装，镜像源配置修改及虚拟环境的创建
boxti
|
安全 数据库 数据安全/隐私保护
大麦网数据泄露致用户被骗，我们该如何防范“撞库”攻击
boxti
2321 0
2025「AI安全」全球攻防赛小编
|
1天前
|
云安全 人工智能 自然语言处理
AI说的每一句话，都靠谱吗？
阿里云提供AI全栈安全能力，其中针对AI输入与输出环节的安全合规挑战，我们构建了“开箱即用”与“按需增强”相结合的多层次、可配置的内容安全机制。
2025「AI安全」全球攻防赛小编
1628 1
2025「AI安全」全球攻防赛小编
|
5天前
|
存储 人工智能 安全
AI 越智能，数据越危险？
阿里云提供AI全栈安全能力，为客户构建全链路数据保护体系，让企业敢用、能用、放心用
2025「AI安全」全球攻防赛小编
1304 10
阿里云万网官方
|
8天前
|
域名解析 人工智能
【实操攻略】手把手教学，免费领取.CN域名
即日起至2025年12月31日，购买万小智AI建站或云·企业官网，每单可免费领1个.CN域名首年！跟我了解领取攻略吧~
阿里云万网官方
1119 9
阿里云云原生
|
3天前
|
消息中间件 安全 NoSQL
阿里云通过中国信通院首批安全可信中间件评估
近日，由中国信通院主办的 2025（第五届）数字化转型发展大会在京举行。会上，“阿里云应用服务器软件 AliEE”、“消息队列软件 RocketMQ”、“云数据库 Tair”三款产品成功通过中国信通院“安全可信中间件”系列评估，成为首批获此认证的中间件产品。此次评估覆盖安全可信要求、功能完备性、安全防护能力、性能表现、可靠性与可维护性等核心指标，标志着阿里云中间件产品在多架构适配与安全能力上达到行业领先水平。
阿里云云原生
301 192

热门文章

最新文章

  • 1
    AliOS Things+阿里云 10分钟搭建智慧农业解决方案
  • 2
    从校招生到核心架构师，支付宝研究员李俊奎谈如何成为一名优秀的程序员
  • 3
    Claude官网中文版：在国内使用claude AI的最佳选择！
  • 4
    解决:bash: syntax error near unexpected token `(‘ ...【亲测有效】
  • 5
    上云就上阿里云背后：云计算已成为新旧动能转换关键
  • 6
    58快狗打车基于Hologres的实时离线统一数据服务
  • 7
    Data truncation: Out of range value
  • 8
    【Linux】关于Linux的部分细节与配置文件
  • 9
    Silverlight MMORPG《窝窝世界》游戏视频
  • 10
    Django之admin
  • 1
    基于springboot的智慧家园物业管理系统
    47
  • 2
    Traefik：Go 实现的云原生反向代理，微服务路由自动化利器
    165
  • 3
    货拉拉用户画像基于 Apache Doris 的数据模型设计与实践
    48
  • 4
    程序员的出路：30岁，我们聊聊那些真实的选择
    184
  • 5
    Apache Doris 4.0 版本正式发布：全面升级 AI 与搜索能力，强化离线计算
    65
  • 6
    《游戏测评工具宝典：告别主观评判，用技术逻辑定义专业标准》
    33
  • 7
    从 Snowflake 到 Apache Doris：Planet 实时分析成本直降 80%、查询加速 90 倍
    30
  • 8
    《游戏测评进阶手册：核心工具应用技巧，打造有深度的技术分析》
    42
  • 9
    Doris MCP Server v0.6.0 正式发布
    32
  • 10
    【阿里云安全小贴士】创建ECS后，这3个配置千万别漏过
    95

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    让AI单次生成4万字！WriteHERE：开源AI长文写作框架，单次生成超长文本，小说报告一键搞定！