网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
东方程序学习馆吧 关注：60贴子：440

【ダメ】とあるCの内存管理方案

■ 前言
本文内容并非原创，仅仅是对一些现有思路进行整理，使其为己所用。
本文的最终目标是制定一套替代malloc&free的内存管理方案。同时也为接下来在C中践行OOP提供一些基础资源。
直接使用malloc&free的内存管理，在很多情况下都能满足需求（这些情况下不去考虑替代案或许反而是正解），但仍有以下一些遗憾：
1. 使用malloc所获取的内存空间，其大小不可变，不具扩展性。解决方案大致有两种：其一是使用realloc，但这样会产生副作用，具体将在第一节“realloc方案”中讨论；其二是对多次malloc所获取的内存块，按某种方式进行管理，使其从用户视点保持为一个整体。
2. 使用malloc所获取的内存空间，其释放时机并不总是明确的。一般来说为了防止内存泄露，都需要小心翼翼的梳理malloc与对应的free之间的关系。即使如此，在一些执行时间长，对象生存周期跨度大，依赖关系复杂的情况下，也会出现意外的困境。
3. malloc作为泛用内存管理方案，其注重的是在频繁分配释放大小不定的空间时，也不会使内存使用效率降低。但在有些情况下，更为频繁的是分配释放固定大小的结构体。此时，malloc的开销就略显昂贵了。（针对这些情况，比较常见的方案是预先分配较大的结构体数组。）
本文并不打算一次性提出方案的最终形态，而将通过逐步化解这些遗憾以求更好的整理思路。
以下是内容目录：
■ realloc方案
■ 泛用内存池（第一阶段）
■ 泛用内存池（第二阶段）
■ 引用计数
■ 泛用内存池（最终形态）


mark


kram


■ realloc方案
这是一个构思和实现都较为简单的方案，具体做法可以概括为以下三点：
1. 在结构体中声明标记成员，以区分可用与不可用。使用realloc创建（及扩展）该结构体的数组。
2. 始终保存首个可用结构体的下标。当用户请求分配时，将其标记为不可用后返回其下标，同时向后搜索第一个可用结构体。
3. 当用户释放结构体时，将其标记为可用，并视情况调整首个可用元素的下标。
以下是实现的例子：


包含测试部分的完整代码在以下地址：
http://pan.baidu.com/share/link?shareid=316584&uk=2986345329
[Sample01_realloc.c]
由于采用了较为简单的机制，该方案在效率上还算不错，在一些场合直接应用也能够满足需求。
当然，此方案也有以下一些明显的缺憾，使笔者无法满足于此：
1. 用户必须使用下标对结构体进行访问，这会造成用户的不适应，以及代码冗长。需要特别指出，这一点是由realloc的副作用所造成的。由于使用realloc后，内存区域可能发生移动，用户无法以指针方式保持对结构体的访问，因此只能选择下标方式。
2. 只对具体结构体有效，不具有泛用性。当然，这并非绝对，如果应用本文后面章节中所提到的手法，结论将是可以泛用化。不过，由于有1.的硬伤，勉强泛用化也只会让访问方式越发冗长，使人难以接受。
3. 在分配函数中进行了线性搜索。
...
总体来说，这只能算一个初级方案。不过，通过该方案，能够看出一些改进方向。接下来可以朝着这些方向继续挖掘。


■ realloc方案
这是一个构思和实现都较为简单的方案，具体做法可以概括为以下三点：
1. 在结构体中声明标记成员，以区分可用与不可用。使用realloc创建（及扩展）该结构体的数组。
2. 始终保存首个可用结构体的下标。当用户请求分配时，将其标记为不可用后返回其下标，同时向后搜索第一个可用结构体。
3. 当用户释放结构体时，将其标记为可用，并视情况调整首个可用元素的下标。
以下是实现的例子：


包含测试部分的完整代码在以下地址：
[Sample01_realloc.c]
http://pan.baidu.com/share/link?shareid=316584&uk=2986345329
由于采用了较为简单的机制，该方案在效率上还算不错，在一些场合直接应用也能够满足需求。
当然，此方案也有以下一些明显的缺憾，使笔者无法满足于此：
1. 用户必须使用下标对结构体进行访问，这会造成用户的不适应，以及代码冗长。需要特别指出，这一点是由realloc的副作用所造成的。由于使用realloc后，内存区域可能发生移动，用户无法以指针方式保持对结构体的访问，因此只能选择下标方式。
2. 只对具体结构体有效，不具有泛用性。当然，这并非绝对，如果应用本文后面章节中所提到的手法，结论将是可以泛用化。不过，由于有1.的硬伤，勉强泛用化也只会让访问方式越发冗长，使人难以接受。
3. 在分配函数中进行了线性搜索。
...
总体来说，这只能算一个初级方案。不过，通过该方案，能够看出一些改进方向。接下来可以朝着这些方向继续挖掘。


■ realloc方案
这是一个构思和实现都较为简单的方案，具体做法可以概括为以下三点：
1. 在结构体中声明标记成员，以区分可用与不可用。使用realloc创建（及扩展）该结构体的数组。
2. 始终保存首个可用结构体的下标。当用户请求分配时，将其标记为不可用后返回其下标，同时向后搜索第一个可用结构体。
3. 当用户释放结构体时，将其标记为可用，并视情况调整首个可用元素的下标。
以下是实现的例子：


包含测试部分的完整代码（Sample01_realloc.c）在以下地址：
pan.baidu.com/share/link?shareid=316584&uk=2986345329
由于采用了较为简单的机制，该方案在效率上还算不错，在一些场合直接应用也能够满足需求。
当然，此方案也有以下一些明显的缺憾，使笔者无法满足于此：
1. 用户必须使用下标对结构体进行访问，这会造成用户的不适应，以及代码冗长。需要特别指出，这一点是由realloc的副作用所造成的。由于使用realloc后，内存区域可能发生移动，用户无法以指针方式保持对结构体的访问，因此只能选择下标方式。
2. 只对具体结构体有效，不具有泛用性。当然，这并非绝对，如果应用本文后面章节中所提到的手法，结论将是可以泛用化。不过，由于有1.的硬伤，勉强泛用化也只会让访问方式越发冗长，使人难以接受。
3. 在分配函数中进行了线性搜索。
...
总体来说，这只能算一个初级方案。不过，通过该方案，能够看出一些改进方向。接下来可以朝着这些方向继续挖掘。


■ 泛用内存池（第一阶段）
正如realloc方案中所看到的，虽然数组的优势在于可以一次性分配较多内存，但不可避免的会发生线性搜索。
另一种方式是使用链表来管理可用内存对象。这种方式的优点是，无论分配或是释放，都只需要操作链表的首元素。
这里我们取双方之长，采用数组模拟链表的方式来构造一个新的内存池。通过下图可以直观的理解其结构：

既然名为内存池，就必须良好支持不同大小的内存分配需求，即具有泛用性。在内存对象的声明中，我们利用C99的新特性，让结构体大小可变。（C89中亦可通过声明大小为1的数组来实现，这种方法被称作“struct hack”）

更进一步的，我们让用户获取指向memBlock部分的指针，这样用户操作这部分内存时就与使用malloc的情况近乎一致。
当用户释放该部分内存时，我们使用以下手法将其转换回指向内存对象的指针。

理解该宏的要点在于理解“(int)&((struct MemItem*)0)->memBlock”部分。通过将0强转为指向struct MemItem的指针，我们可以获取memBlock相对struct MemItem起始地址的偏移量。
有了这些准备工作，我们可以开始具体实现，以下为第一阶段的代码：
※第一阶段只分配固定长度的数组，重点在于链表部分的操作。



包含测试部分的完整代码（Sample01_mempool_1.c）在以下地址：
pan.baidu.com/share/link?shareid=316584&uk=2986345329
显然，比起realloc方案，已经有了明显的进步。在下一节中，我们将使数组长可变，以适应不同程度的分配请求。


■ 泛用内存池（第二阶段）
本节的主要目的是让数组长可变。
链表的特性是各元素在空间上不必连续，因此我们可以多次使用malloc分配较大的内存块。下面是该构思的示意图：

左右分别以链表形式管理，这是本方案的关键。接下来是第二阶段的代码，只贴出较第一阶段有变化的部分。
MemPool中增加了指向内存对象簇链表的指针，并将固定容量替换为扩容增量。

MemItem部分并无变化。
新增MemCluster。

新增扩容处理，以向内存池中添加MemCluster。

内存池创建函数变得十分简洁。

获取函数增加了扩容处理。

释放函数无变化。
这样一来，我们的泛用内存池就基本成型了。再完善一些检查和错误处理，投入实际使用应该也无问题。
即使如此，到这里依然存在两点不满：
1. 前言中所提到遗憾之2，在这个阶段仍未着手解决。而且在这个阶段如果用户代码存在重复释放，对内存对象链表造成的影响是毁灭性的。
2. 依然需要针对不同的类型生成专有内存池。本文的目标是制定一套替代malloc&free的内存管理方案，自然也需要一对统一的接口。
对于以上两点，将依次在后两节中提出解决方案。


■ 泛用内存池（第二阶段）
本节的主要目的是让数组长可变。
链表的特性是各元素在空间上不必连续，因此我们可以多次使用malloc分配较大的内存块。下面是该构思的示意图：

左右分别以链表形式管理，这是本方案的关键。接下来是第二阶段的代码，只贴出较第一阶段有变化的部分。
MemPool中增加了指向内存对象簇链表的指针，并将固定容量替换为扩容增量。

MemItem部分并无变化。
新增MemCluster。

新增扩容处理，以向内存池中添加MemCluster。

内存池创建函数变得十分简洁。

获取函数增加了扩容处理。

释放函数无变化。
包含测试部分的完整代码（Sample01_mempool_2.c）在以下地址：
pan.baidu.com/share/link?shareid=316584&uk=2986345329
这样一来，我们的泛用内存池就基本成型了。再完善一些检查和错误处理，投入实际使用应该也无问题。
即使如此，到这里依然存在两点不满：
1. 前言中所提到遗憾之2，在这个阶段仍未着手解决。而且在这个阶段如果用户代码存在重复释放，对内存对象链表造成的影响是毁灭性的。
2. 依然需要针对不同的类型生成专有内存池。本文的目标是制定一套替代malloc&free的内存管理方案，自然也需要一对统一的接口。
对于以上两点，将依次在后两节中提出解决方案。


■ 泛用内存池（第二阶段）
本节的主要目的是让数组长可变。
链表的特性是各元素在空间上不必连续，因此我们可以多次使用malloc分配较大的内存块。下面是该构思的示意图：

左右分别以链表形式管理，这是本方案的关键。接下来是第二阶段的代码，只贴出较第一阶段有变化的部分。
MemPool中增加了指向内存对象簇链表的指针，并将固定容量替换为扩容增量。

MemItem部分并无变化。
新增MemCluster。

新增扩容处理，以向内存池中添加MemCluster。

内存池创建函数变得十分简洁。

获取函数增加了扩容处理。

释放函数无变化。
包含测试部分的完整代码（Sample01_mempool_2.c）在以下地址：
pan.baidu.com/share/link?shareid=316584&uk=2986345329
这样一来，我们的泛用内存池就基本成型了。再完善一些检查和错误处理，投入实际使用应该也无问题。
即使如此，到这里依然存在两点不满：
1. 前言中所提到遗憾之2，在这个阶段仍未着手解决。而且在这个阶段如果用户代码存在重复释放，对内存对象链表造成的影响是毁灭性的。
2. 依然需要针对不同的类型生成专有内存池。本文的目标是制定一套替代malloc&free的内存管理方案，自然也需要一对统一的接口。
对于以上两点，将依次在后两节中提出解决方案。


■ 引用计数
针对前言中所提到的遗憾之2，要寻求一个令人满意的解决方案可谓难题，在这里笔者选择尝试引用计数方式。
该方式使用引用计数器记录散布于程序各处的，指向该对象的引用数量，当引用计数器归0时释放该对象。
[伪代码]
----------------------------------------------------------------
Obj* a = alloc(Obj); // 对象分配时，引用a拥有所有权，refCount = 1
Obj* b = retain(a); // 引用b声明所有权，refCount = 2
free(a); // 引用a放弃所有权，refCount = 1，对象未被释放
free(b); // 引用b放弃所有权，refCount = 0，对象被释放
----------------------------------------------------------------
如上例所示，若一个引用使引用计数器自增，则表示该引用对其指向的对象拥有所有权，除非其放弃所有权（使引用计数器自减），否则其他处理无法释放该对象。
简单介绍之后，首先请看这部分的实现。仅在上一节代码的基础上追加了引用计数功能。
MemItem追加了两个成员。由于使用引用计数方式，导致对象真正被释放的时机不再由用户把握，因此由内存管理一方执行析构函数是有必要的。至于析构函数是否应该保存于MemItem内则有待商榷。

获取函数增加了对引用计数器和析构函数的设定。

释放函数除需增加对引用计数器的操作以外，检查引用是否有效也是必要的。

retain函数用于对已有对象声明所有权。

包含测试部分的完整代码（Sample03_refcount.c）在以下地址：
pan.baidu.com/share/link?shareid=316584&uk=2986345329
虽然概念与实现均不深奥，但实际操作起来却意外麻烦，这里举两个较为常见的问题：
1. 循环引用
即引用（直接或间接的）重复声明了所有权，导致对象不可释放的情况。下面是一个极为简单的循环链表，以模拟这种情况：
[伪代码]
----------------------------------------------------------------
Obj* a = alloc(Obj); // refCount = 1
a->next = a, a->refCount++; // refCount = 2
free(a); // ！refCount = 1，无法释放对象
----------------------------------------------------------------
然而，在实际情况中则不会如此显而易见，由多个对象相互保有引用所造成的循环将更为隐蔽。这时需要仔细梳理所有权关系，分清强引用（具有所有权的引用）与弱引用（不具所有权的引用），斩断循环。
以刚才的循环链表为例，链表中的各元素应仅保有对下一元素的弱引用（即不改变引用计数器），而由封装好的容器来保有各元素的所有权：
[伪代码]
----------------------------------------------------------------
void insertFirst(list, obj); // 该接口中对obj声明所有权（refCount++）
Obj* removeFirst(list); // 该接口中对obj放弃所有权（refCount--）
----------------------------------------------------------------
2. 所有权移交
具体来说就是所有权移交时的顺序问题，使用上例循环链表的removeFirst接口，考虑以下代码：
[伪代码]
----------------------------------------------------------------
Obj* a = removeFirst(list); // 假设放弃所有权使refCount归0，对象被释放
a->someOpt(); // ！a是无效引用
----------------------------------------------------------------
在不更改接口实现的前提下，正确的顺序是：
[伪代码]
----------------------------------------------------------------
Obj* a = getFirst(list); // 获取对象
retain(a); // 声明所有权，refCount++
removeFirst(list); // 删除对象
a->someOpt();
----------------------------------------------------------------
又如常见的setter函数：
[伪代码]
----------------------------------------------------------------
// ！假设mb与obj->member指向同一对象，free若造成对象释放，后果不言自明
// 正确的顺序是L1与L2互换。
void setMember(obj, mb) {
L1: free(obj->member);
L2: retain(mb);
L3: obj->member = mb;
}
----------------------------------------------------------------
总结：
以上只列举了使用引用计数方式可能直面的两个问题，而在实际情况中，细节上的注意点还有很多。由于没有运算符重载，操作需要显式执行，如果不能确立一套用户容易接受与践行的规范，很容易造成失败。
在下一节的最终形态中，笔者还将尝试加入半自动释放的方式。这种方式的特点是在放弃所有权时，并不会立即操作引用计数器，而实际操作将会在用户指定的时机发生。针对引用计数器始终为1的局部变量，以及在引用计数器为1的状态下所进行的所有权移交来说，这种方式将一定程度缓解用户的压力。


■ 引用计数
针对前言中所提到的遗憾之2，要寻求一个令人满意的解决方案可谓难题，在这里笔者选择尝试引用计数方式。
该方式使用引用计数器记录散布于程序各处的，指向该对象的引用数量，当引用计数器归0时释放该对象。
[伪代码]
----------------------------------------------------------------
Obj* a = alloc(Obj); // 对象分配时，引用a拥有所有权，refCount = 1
Obj* b = retain(a); // 引用b声明所有权，refCount = 2
free(a); // 引用a放弃所有权，refCount = 1，对象未被释放
free(b); // 引用b放弃所有权，refCount = 0，对象被释放
----------------------------------------------------------------
如上例所示，若一个引用使引用计数器自增，则表示该引用对其指向的对象拥有所有权，除非其放弃所有权（使引用计数器自减），否则其他处理无法释放该对象。
简单介绍之后，首先请看这部分的实现。仅在上一节代码的基础上追加了引用计数功能。
MemItem追加了两个成员。由于使用引用计数方式，导致对象真正被释放的时机不再由用户把握，因此由内存管理一方执行析构函数是有必要的。至于析构函数是否应该保存于MemItem内则有待商榷。

获取函数增加了对引用计数器和析构函数的设定。

释放函数除需增加对引用计数器的操作以外，检查引用是否有效也是必要的。

retain函数用于对已有对象声明所有权。

包含测试部分的完整代码（Sample03_refcount.c）在以下地址：
pan.baidu.com/share/link?shareid=316584&uk=2986345329
虽然概念与实现均不深奥，但实际操作起来却意外麻烦，这里举两个较为常见的问题：
1. 循环引用
即引用（直接或间接的）重复声明了所有权，导致对象不可释放的情况。下面是一个极为简单的循环链表，以模拟这种情况：
[伪代码]
----------------------------------------------------------------
Obj* a = alloc(Obj); // refCount = 1
a->next = a, a->refCount++; // refCount = 2
free(a); // ！refCount = 1，无法释放对象
----------------------------------------------------------------
然而，在实际情况中则不会如此显而易见，由多个对象相互保有引用所造成的循环将更为隐蔽。这时需要仔细梳理所有权关系，分清强引用（具有所有权的引用）与弱引用（不具所有权的引用），斩断循环。
以刚才的循环链表为例，链表中的各元素应仅保有对下一元素的弱引用（即不改变引用计数器），而由封装好的容器来保有各元素的所有权：
[伪代码]
----------------------------------------------------------------
void insertFirst(list, obj); // 该接口中对obj声明所有权（refCount++）
Obj* removeFirst(list); // 该接口中对obj放弃所有权（refCount--）
----------------------------------------------------------------
2. 所有权移交
具体来说就是所有权移交时的顺序问题，使用上例循环链表的removeFirst接口，考虑以下代码：
[伪代码]
----------------------------------------------------------------
Obj* a = removeFirst(list); // 假设放弃所有权使refCount归0，对象被释放
a->someOpt(); // ！a是无效引用
----------------------------------------------------------------
在不更改接口实现的前提下，正确的顺序是：
[伪代码]
----------------------------------------------------------------
Obj* a = getFirst(list); // 获取对象
retain(a); // 声明所有权，refCount++
removeFirst(list); // 删除对象
a->someOpt();
----------------------------------------------------------------
又如常见的setter函数：
[伪代码]
----------------------------------------------------------------
// ！假设mb与obj->member指向同一对象，free若造成对象释放，后果不言自明
// 正确的顺序是L1与L2互换。
void setMember(obj, mb) {
L1: free(obj->member);
L2: retain(mb);
L3: obj->member = mb;
}
----------------------------------------------------------------
总结：
以上只列举了使用引用计数方式可能直面的两个问题，而在实际情况中，细节上的注意点还有很多。由于没有运算符重载，操作需要显式执行，如果不能确立一套用户容易接受与践行的规范，很容易造成失败。
在下一节的最终形态中，笔者还将尝试加入半自动释放的方式。这种方式的特点是在放弃所有权时，并不会立即操作引用计数器，而实际操作将会在用户指定的时机发生。针对引用计数器始终为1的局部变量，以及在引用计数器为1的状态下所进行的所有权移交来说，这种方式将一定程度缓解用户的压力。


■ 泛用内存池（最终形态）
首先是代码。虽然冠以“最终”二字，不过无论在构思上还是实现上，都仅仅是个开始（线程安全也未考虑）。因此如果存在问题与建议，还望大家不吝赐教。
包含测试代码的所有文件在以下地址：
pan.baidu.com/share/link?shareid=322472&uk=2986345329
通过头文件注释以及测试代码，大致的用法已然不言自明。这里主要介绍一下新加入的自动释放池的用法。
与自动释放池相关的有以下3个函数和1个宏。


其中ndmem_pond与ndmem_drain必须成对调用，其功能正如注释所述。在一对pond/drain之间，可以嵌套另一对pond/drain。以下通过伪代码来演示池内对象的变化过程：
[伪代码]
----------------------------------------------------------------
// 第1层创建
pond(); // {}
auto(a), auto(b); // {a, b}
// 第2层创建
pond(); // {}, {a, b}
auto(c), auto(d); // {c, d}, {a, b}
// 第2层排放
drain(); // {a, b}
// 第1层排放
drain(); //
----------------------------------------------------------------
可以看出池是以FILO方式被创建和释放的。
关于自动释放池的用武之地，这里举两个简单的例子：
1. 上一节提到过的容器元素的删除
[伪代码]
----------------------------------------------------------------
void removeFirst(list) {
return autoFree(first);
}
// 用户代码
Obj* a = removeFirst(list);
a->someOpt(); // OK，a依然有效
----------------------------------------------------------------
2. 字符串生成函数（便利店函数）
[伪代码]
----------------------------------------------------------------
StrObj getStrObj(cstr) {
return autoFree(init(alloc(StrObj), cstr));
}
// 用户代码
writeConsole(getStrObj("test")); // 用户无需保持引用
----------------------------------------------------------------
通过例子很难涵盖各类情况，而这部分其实可以参照Objective-C的内存管理模式（Mac Developer Library里可以找到很多原则性约定），事实上本文很多思路也来源于彼处。
接下来简单介绍一下实现部分。实现主要由三部分构成：
1. 内存池
该部分大致与上一阶段的成果物相同。
内存池中追加了统计所需的成员（池容量、当前分配数、最高分配数）以及相关处理。
此外，内存对象中新加入了memBlockSize成员，其用途与接下来的“2.散列表”有关。（当用户释放内存对象时，内存管理一方可以通过该成员找到存放于散列表中的内存池。）
2. 散列表（改造版）
散列表在这里被用于存放各种尺寸的内存池。该部分的存在理由，主要是为了能向用户提供一套统一的接口，使用户在分配对象时不必指定专有内存池。
出于一些考虑，最终形态中所提供的内存池，内存块大小均为4的倍数。因此散列函数也异常简单：(objSize - 1) / 4。为了消除冲突，散列函数中并未取余，因此必须使散列表可扩展。这里为了兼顾空间，笔者尝试使用Iliffe vector方式管理散列桶，每个一维数组均可存放64个指向内存池的指针。
这部分实现略显怪异，如有兴趣可参阅代码。
3. 自动释放池
该部分实现很简单，释放池中保有一个用于积蓄待释放对象的循环链表。之所以采用循环链表，是为了通过next成员的值判断其是否已在池中，避免重复插入。
释放池本身也是单链表结构，与内存池内的链表相同，只进行FILO操作。
以上就是对最终形态的介绍。


■ 泛用内存池（最终形态）
首先是代码。虽然冠以“最终”二字，不过无论在构思上还是实现上，都仅仅是个开始（线程安全也未考虑）。因此如果存在问题与建议，还望大家不吝赐教。
包含测试代码的所有文件在以下地址：
pan.baidu.com/share/link?shareid=322472&uk=2986345329
通过头文件注释以及测试代码，大致的用法已然不言自明。这里主要介绍一下新加入的自动释放池的用法。
与自动释放池相关的有以下3个函数和1个宏。


其中ndmem_pond与ndmem_drain必须成对调用，其功能正如注释所述。
在一对pond/drain之间，可以嵌套另一对pond/drain。以下通过伪代码来演示池内对象的变化过程：
[伪代码]
----------------------------------------------------------------
// 第1层创建
pond(); // {}
auto(a), auto(b); // {a, b}
// 第2层创建
pond(); // {}, {a, b}
auto(c), auto(d); // {c, d}, {a, b}
// 第2层排放
drain(); // {a, b}
// 第1层排放
drain(); //
----------------------------------------------------------------
可以看出池是以FILO方式被创建和释放的。
关于自动释放池的用武之地，这里举两个简单的例子：
1. 上一节提到过的容器元素的删除
[伪代码]
----------------------------------------------------------------
void* removeFirst(list) {
...
return autoFree(first));
}
// 用户代码
Obj* a = removeFirst(list);
a->someOpt(); // OK，a依然有效
----------------------------------------------------------------
2. 字符串生成函数（便利店函数）
[伪代码]
----------------------------------------------------------------
StrObj* getStrObj(cstr) {
return autoFree(init(alloc(StrObjSize), cstr));
}
// 用户代码
writeConsole(getStrObj("test")); // 用户无需保持引用
----------------------------------------------------------------
通过例子很难涵盖各类情况，而这部分其实可以参照Objective-C的内存管理模式（Mac Developer Library里可以找到很多原则性约定），事实上本文很多思路也来源于彼处。
接下来简单介绍一下实现部分。实现主要由三部分构成：
1. 内存池
该部分大致与上一阶段的成果物相同。
内存池中追加了统计所需的成员（池容量、当前分配数、最高分配数）以及相关处理。
此外，内存对象中新加入了memBlockSize成员，其用途与接下来的“2.散列表”有关。（当用户释放内存对象时，内存管理一方可以通过该成员找到存放于散列表中的内存池。）
2. 散列表（改造版）
散列表在这里被用于存放各种尺寸的内存池。该部分的存在理由，主要是为了能向用户提供一套统一的接口，使用户在分配对象时不必指定专有内存池。
出于一些考虑，最终形态中所提供的内存池，内存块大小均为4的倍数。因此散列函数也异常简单：(objSize - 1) / 4。为了消除冲突，散列函数中并未取余，因此必须使散列表可扩展。这里为了兼顾空间，笔者尝试使用Iliffe vector方式管理散列桶，每个一维数组均可存放64个指向内存池的指针。
这部分实现略显怪异，如有兴趣可参阅代码。
3. 自动释放池
该部分实现很简单，释放池中保有一个用于积蓄待释放对象的循环链表。之所以采用循环链表，是为了通过next成员的值判断其是否已在池中，避免重复插入。
释放池本身也是单链表结构，与内存池内的链表相同，只进行FILO操作。
以上就是对最终形态的介绍。


修订了一些放到别馆去了
http://tieba.baidu.com/p/2199326785


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
分享到: