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

推荐订阅源

博客园 - 三生石上(FineUI控件)
WordPress大学
WordPress大学
S
SegmentFault 最新的问题
小众软件
小众软件
T
Tailwind CSS Blog
博客园 - 聂微东
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
人人都是产品经理
人人都是产品经理
V
Visual Studio Blog
罗磊的独立博客
有赞技术团队
有赞技术团队
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
Jina AI
Jina AI
量子位
云风的 BLOG
云风的 BLOG
Recent Announcements
Recent Announcements
Hugging Face - Blog
Hugging Face - Blog
P
Proofpoint News Feed
N
Netflix TechBlog - Medium
GbyAI
GbyAI
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
腾讯CDC
美团技术团队

博客园 - 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