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 

posted on 2012-06-16 18:38 Zero Lee 阅读(233) 评论(0)  编辑 收藏 引用 所属分类: Data structure and algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理