内存池数据结构

内存池（定长）

内存池是由一个个固定大小的内存块组成，所以应用每次获取的内存块长度是固定的。

常见内存池形状：

此内存池方案参考来源为 RT-Thread 的内存管理方案，同时也是市面上大部分的内存池解决类似方案。

             内存块1                            内存块2                                            内存块n
       +----------------+                +----------------+                                  +----------------+
pool1  | 指针位 | 数据块 |---物理连续----> | 指针位 | 数据块 |--物理连续-->   ...  --物理连续--> | 指针位 | 数据块 |     
       +----------------+                +----------------+                                  +----------------+

             内存块1                            内存块2                                            内存块n
       +----------------+                +----------------+                                  +----------------+
pool2  | 指针位 | 数据块 |---物理连续----> | 指针位 | 数据块 |--物理连续-->   ...  --物理连续--> | 指针位 | 数据块 |     
       +----------------+                +----------------+                                  +----------------+
       

pooln  ...
1
2
3
4
5
6
7
8
9
10
11
12

一般用户只会使用到一个内存池，也就是上图中的 pool1。

一个池子内的所有内存块都是物理上连续的，但常常会出现**“使用中”与“空闲中”**的内存块并不刚好是物理有序的前后状态。比如内存块1使用中，内存块2空闲，内存块3使用中……

上述情况下，当用户需要获取一个空闲的内存块时，若是按物理连续的逻辑来找**“空闲中”的内存块，无论使用任何搜索办法，都无法达到 O(1) 的查找效率。那么，内存块中的指针位在这时就发挥作用了，我们可以将一个池子中的“空闲中”**内存块用一个链表串起来。程序某时刻链表的形象图如下：

                               +-----------------------+
                               |                       |
            block 4            |     block 1           v     block x
       +----------------+      +----------------+      +----------------+
pool1  | 指针位 | 数据块 |      | 指针位 | 数据块 |      | 指针位 | 数据块 |          NULL
       +----------------+      +----------------+      +----------------+           ^
       |                       ^                       |                            |
       |                       |                       |                            |
       +-----------------------+                       +----------------------------+
1
2
3
4
5
6
7
8
9

这样一来，每次获取空闲块直接从表头拿就行了，时间复杂的是明确的 O(1)。被分离出的空闲块指针位指向 pool 对象本体，便于后续“物归”时找到“原主”