我们在之前的文章学习了编写malloc_allocator，它是一个借助malloc分配内存的分配器，并且实现了在C++11标准中的接口。同时malloc_allocator可以帮助我们实现另一个分配器free_list_allocator。
free_list_allocator是我们整个项目真正要使用的分配器。在说明具体的代码之前，先来说说为什么要用分配器而不直接使用 new 与 delete 进行内存的分配与释放。如果有学习过操作系统的相关知识的话应该有所了解: 频繁的进行内存申请时将产生大量的内存碎片且降低性能。
举个例子， 假设我们有10个单位的连续内存区域，范围 0 - 9。我们首先申请 4 个单位的空间， 那么将分配区域 0 - 3。然后我们再申请 4 单位内存， 分配区域 4 - 7。现在我们只有8 - 9的位置是空闲的， 然而如果以后申请的内存都大于 2 个单位, 那么只能从别的内存段分配内存，区域 8 - 9永远用不上了，成为碎片。
为了避免碎片的产生，我们才使用分配器定义容器的分配策略。那么分配器采用什么方法避免内存碎片的产生呢？malloc_alloctor虽说是分配器，但它只是简单的封装了malloc()函数进行内存分配而已.。 malloc()对偶发的大量内存分配做了优化，所以此时malloc_alloctor的效率良好。然而在需要频繁分配少量内存的情况下效率低下，且容易产生内存碎片。
有鉴于此，在这一情况下，人们常使用基于内存池的分配器来解决频繁少量分配问题。与默认的“按需分配”方式不同，在使用基于内存池的分配器时，程序会预先为之分配大块内存（即“内存池”），而后在需要分配内存时，自定义分配器只需向请求方返回一个指向池内内存的指针即可；而在对象析构时，并不需实际解除分配内存，而是延迟到内存池的生命周期完结时才真正解除分配。这样不仅能减少内存碎片的产生也避免了对系统频繁的内存申请。
我们要实现free_list_allocator正是此类分配器。free_list_allocator的整体思想是: 如果要分配的内存大于 128 bytes（即分配大量内存) ，就交给malloc_allocator处理。否则由 memory pool(内存池) 负责分配与回收。
我们先来了解free_list_allocator的声明:
template<typename T>
class free_list_allocator
{
private:
static const std::size_t ALIGN = 8;
static const std::size_t MAX_BLOCK_SIZE = 128;
static const std::size_t FREE_LIST_NUM = MAX_BLOCK_SIZE / ALIGN;
struct obj
{
obj *free_list_link;
};
static obj *free_list[FREE_LIST_NUM];
//内存池起始位置
static char *start_pool;
//内存池结束位置
static char *end_pool;
static std::size_t heap_size;
//将byte上调至8的倍数
static std::size_t round_up(std::size_t byte)
{
return ((byte) + ALIGN - 1) & ~(ALIGN - 1);
}
//由所需内存大小决定free_list的索引
static std::size_t free_list_index(std::size_t byte)
{
return byte / (ALIGN + 1);
}
//为free_list加入新的块
static T *refill(std::size_t block_size);
//分配 num 个 block_size 的空间
static char *chunk_alloc(std::size_t block_size, std::size_t& num);
public:
typedef T value_type;
free_list_allocator() {}
template<typename U>
free_list_allocator(const free_list_allocator<U>&) {}
static T *allocate(std::size_t num);
static void deallocate(T *p, std::size_t num);
};
template<typename T>
typename free_list_allocator<T>::obj *
free_list_allocator<T>::free_list[FREE_LIST_NUM] = {
0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0
};
template<typename T>
char *free_list_allocator<T>::start_pool = nullptr;
template<typename T>
char *free_list_allocator<T>::end_pool = nullptr;
template<typename T>
std::size_t free_list_allocator<T>::heap_size = 0;
free_list_allocator的核心有两部分： free_list 与 memory pool， free_list 从 memory pool 中获取空间并添加内存块。那么所谓的free_list到底是什么？
struct obj
{
obj *free_list_link;
};
static obj *free_list[FREE_LIST_NUM];
free_list 被声明为一个大小为 FREE_LIST_NUM 的数组， 且数组元素为一个指向 struct obj 的指针。实际上每个 free_list 的元素分别指向区块大小为 8, 16, 24, 32, 40, 48 ..... 120, 128 的链表。
上图只显示了8个free_list（实际有16个）。按照之前所说，3号free_list 指向大小为 32 bytes 的内存块。其中每个内存块的开始部分储存一个 obj 结构，每个 obj 都有一个指向下一个内存块的指针（即 free_list_link）。每当用户需要申请内存时， free_list_allocator 便从free_list中找到相应大小的块并且以返回内存块首地址的方式分配出去（即 obj 的地址）。
再了解了 free_list_allocator 的基本原理后，我们终于能看看具体实现了。
- free_list_index(std::size_t byte)
//由所需内存大小决定free_list的索引
static std::size_t free_list_index(std::size_t byte)
{
return byte / (ALIGN + 1);
}
free_list_index 用来查找目标 free_list 的索引。比如需要 20 字节的内存时我们应该去 free_list[ 2 ] 中取得内存块。
- allocate(std::size_t num)
template<typename T>
T *free_list_allocator<T>::allocate(std::size_t num)
{
if (num * sizeof(T) > MAX_BLOCK_SIZE) {
return malloc_allocator<T>::allocate(num);
}
obj *result;
auto target_free_list = free_list + free_list_index(num * sizeof(T));
result = *target_free_list;
if (result == nullptr) {
return refill(round_up(num * sizeof(T)));
}
//将free_list内的元素指向第2个内存块
*target_free_list = result->free_list_link;
return reinterpret_cast<T*>(result);
}
同样， allocate(num) 负责分配 num 个元素的内存。 它首先计算所需总内存是否大于最大块的大小（128 bytes），如果是的话就调用 malloc_allocator<T>::allocate 分配内存。想想之前提过的， malloc 适合进行大量内存的分配。然后借助 free_list_index 找到具有合适大小的块的 free_list。
接着对target_free_list解除引用获取第一个内存块的地址。如果 result == nullptr, 则说明此 free_list 为空，没有指向的内存块。此时我们需要调用 refill() 重新为这个 free_list 添加内存块。（refill 的具体实现要留到下次了）
如果我们成功获取第一个内存块的地址话， 我们还需要将 free_list 的指针重新设置为第二个内存块的地址（这个时候第二个内存块就变成第一个了）。最后再类型转换返回结果就行了。
- deallocate(T *p, std::size_t num)
template<typename T>
void free_list_allocator<T>::deallocate(T *p, std::size_t num)
{
/*
p为需要回收的内存区域的首指针，num代表区域内元素的个数
*/
std::size_t size = num * sizeof(T);
if (size > MAX_BLOCK_SIZE) {
malloc_allocator<T>::deallocate(p, num);
return;
}
//被回收的内存将被加入target_free_list指向的链表
auto target_free_list = free_list + free_list_index(size);
obj *target_block = reinterpret_cast<obj*>(p);
target_block->free_list_link = *target_free_list;
*target_free_list = target_block;
}
deallocate 的思想与 allocate 对应：allocate 是获取第一个内存块，将 free_list 指向第二个内存块。而 deallocate 把需要回收的内存块指向当前第一个内存块，将free_list 指向这个被回收的块。
我们现在已经可以使用 allocate 与 deallocate 分配释放内存，但还有 refill(）和 chunk_alloc() 没有实现。限于文章的篇幅，那就只能等到下次了。再见~
下一篇： STL in C++11 (Allocator 5)
最后附上本篇文章的代码地址：free_list_allocator.h
以及github地址：https://github.com/Puppas/STL-in-Cpp11
