开发工具:
文件大小: 3kb
下载次数: 0
上传时间: 2018-08-08
详细说明： 这个内存分配器需要是非入侵式的，即不在要分配的内存块中写 cookie 。 而我的需求中，需要被管理的内存块都是很规则的，成 2 的整数次幂的长度。buddy memory allocation 刚好适用。 算法很简单，就是每次把一个正内存块对半切分，一直切到需要的大小分配出去。回收的时候，如果跟它配对的块也是未被使用的，就合并成一个大的块。标准算法下，分配和释放的时间复杂度都是 O(log N) ，N 不会特别大。算法的优点是碎片率很小。而且很容易做成非入侵式的，不用在被管理的内存上保存 cookie 。只需要额外开辟一个二叉树记录内存使用状态即可。 我吃完饭简单 google 了一下，没有立刻找到满足我要求的现成代码。心里估算了一下，C 代码量应该在 200 行以下，我大概可以在 1 小时内写完。所以就毫不犹豫的实现了一份。 然后，自然是开源了。有兴趣的同学可以去 github 拿一份。这样就省得到再需要时再造轮子了。嘿嘿。 btw, 当然这块代码有许多值得优化的地方，比如可以把里面的递归优化成循环回溯。这个算法我读初中时经常写。因为初一那个时候参加信息学奥赛时用的 basic 不支持局部变量，全部变量都是全局的，很难实现递归。所以早期我 都不用递归遍历二叉树的，感觉写起来好麻烦。 不过循环回溯遍历树应该是比递归快不少的，因为减少了许多不必要的环境变量压栈，对不支持 closure 的 C 语言尤其是。 这个库用起来很简单。它并不实际管理内存（它不侵入被管理的内存）。你可以设想你另外有一大块内存是由许多最小单位块合起来的。你可以假设最小单位是 1K 。那么用 buddy_new(10) 就可以帮你管理 1024K 内存。 buddy_alloc 可以请求若干个最小单位块，返回一个序号。然后用户可以自己去大内存上索引出来用。用完调用 buddy_free 归还即可。 为了调试方便，我还提供了 buddy_dump 打印二叉树的细节，可以直观的看出那些内存区域未被使用，哪些已经被占用。 ps. 果然，写这篇 blog 花掉的时间比完成这些代码时间更长。代码也如我所料的没有超过 200 行。看看，把东西描述清楚就是比实现一个东西要花更长的时间，这就是项目人多反而做的慢的原因之一吧。 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
