惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

博客园 - Franky
雷峰网
雷峰网
The Cloudflare Blog
WordPress大学
WordPress大学
博客园 - 聂微东
人人都是产品经理
人人都是产品经理
IT之家
IT之家
V
V2EX
博客园 - 司徒正美
小众软件
小众软件
博客园_首页
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
酷 壳 – CoolShell
酷 壳 – CoolShell
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
Hugging Face - Blog
Hugging Face - Blog
T
Tailwind CSS Blog
Last Week in AI
Last Week in AI
Jina AI
Jina AI
博客园 - 叶小钗
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
阮一峰的网络日志
阮一峰的网络日志
爱范儿
爱范儿

博客园 - Zero Lee

调用栈(call stack) 关于STL allocator Calculate maximum sum of any subarray set Calcuate power n of x recursively Convert one binary search tree to double-linked list 设计包含min函数的栈 类模板的模板友元函数定义 一道百度的面试题解答 非printf形式的十六进制和二进制打印(雅虎面试题) 一道腾讯面试题 (转)C++中extern “C”含义深层探索 selection algorithm to select nth small elements based on partition 删除与某个字符相邻且相同的字符 产生全排列的方法解析 一组数的全排列和组合程序实现 求一个正整数的平方根程序实现 [转]多线程队列的算法优化 [转载] STL allocator的介绍和一个基于malloc/free的allocator的简单实现 One simple counted object pointer
如何将一片内存链接成链表
Zero Lee · 2012-06-17 · via 博客园 - Zero Lee

假设有一片内存,大小为m*n, m是每个单元的大小,而且>=8,共有n个这样的单元,如何将它们链接成n个节点的链表,要求不再使用任何其它内存空间。

这里给出SGI STL内存分配器的一个简单实现:
首先定义一个union数据结构:

1 union obj {
2     union obj* free_list_link;
3     char client_data[1];
4 };

这个union结构体的最大大小为4bytes (在32bits 平台上),8bytes (在64bits平台上)。

假设那片内存的地址为chunk,那么我们可以这样做:  

 1  obj* current_obj, *next_obj;
 2  next_obj = (obj*)chunk;
 3  for (int i = 0; ; i++) {
 4      current_obj = next_obj;
 5      next_obj = (obj*)((char*)next_obj + m);
 6      if (n - 1 == i) {
 7          current_obj -> free_list_link = 0;
 8          break;
 9      } else {
10          current_obj -> free_list_link = next_obj;
11      }
12  }
13