我们现在终于要结束分配器部分的内容了，这是 Allocator 的最后一篇文章了。 上次我们还留下了两个函数没有实现: refill() 与 chunk_alloc()。
- refill(std::size_t block_size)
refill()在 free_list 的内存块不足时使用， 用来为 free_list 填充内存块。其中 block_size 代表需要填充的块的大小。我们接下来看一下代码吧：
template<typename T>
T *free_list_allocator<T>::refill(std::size_t block_size)
{
//默认分配16块内存
std::size_t num = 16;
//chunk指向新内存的起始地址
char *chunk = chunk_alloc(block_size, num); //num passed by reference
if (num == 1) {
return reinterpret_cast<T*>(chunk);
}
auto target_free_list = free_list + free_list_index(block_size);
//第一块内存作为结果返回
T *result = reinterpret_cast<T*>(chunk);
--num;
obj *cur_obj, *next_obj;
chunk += block_size;
cur_obj = reinterpret_cast<obj*>(chunk);
cur_obj->free_list_link = nullptr;
--num;
*target_free_list = cur_obj;
while (num > 0)
{
chunk += block_size;
next_obj = reinterpret_cast<obj*>(chunk);
next_obj->free_list_link = nullptr;
--num;
cur_obj->free_list_link = next_obj;
cur_obj = next_obj;
}
return result;
}
refill() 其实并不负责实际的内存申请，而是交给chunk_alloc负责。refill() 只需获取指向新内存的指针就可以了。而 num 由于是引用传递， 在调用 chunk_alloc 后就代表实际上获取的内存块的数量。如果只有1块的话， 我们直接返回就行了。
如果我们成功获取多块内存，就需要将第2块之后的内存插入到对应的 free_list 当中。具体的分块操作就是每次对指针自增 block_size， 这样每次指针就是每块内存的首地址了。
再来看具体代码
obj *cur_obj, *next_obj;
chunk += block_size;
cur_obj = reinterpret_cast<obj*>(chunk);
cur_obj->free_list_link = nullptr;
--num;
*target_free_list = cur_obj;
cur_obj 表示当前块的首指针， next_obj 则指向下一块内存。我们首先对 chunk 加上 block_size， 这时chunk就指向第二块内存 了，再将 chunk 赋值给 cur_obj。同时我们为相应的 free_list 添加 内存块， 将 target_free_list 内的元素设为 cur_obj。注意此时cur_obj是 target_free_list的第一个内存块。
接下来的循环代码：
while (num > 0)
{
chunk += block_size;
next_obj = reinterpret_cast<obj*>(chunk);
next_obj->free_list_link = nullptr;
--num;
cur_obj->free_list_link = next_obj;
cur_obj = next_obj;
}
我们每次都先将 chunk 指针往后移 block_size 个单位， 用 next_obj 指向它。同时将 cur_obj 的 free_list_link 设为 next_obj（前一个内存块指向后一个内存块）。借助这个循环， 我们就将chunk指向的内存全部加入到 free_list 当中了。
- chunk_alloc(std::size_t block_size, std::size_t& num)
template<typename T>
char *
free_list_allocator<T>::chunk_alloc(std::size_t block_size, std::size_t& num)
{
char *result;
/*
total_byte: 总共需要的byte
left_byte: 内存池剩余的byte
*/
std::size_t total_byte = block_size * num;
std::size_t left_byte = end_pool - start_pool;
if (left_byte > total_byte)
{
result = start_pool;
start_pool += total_byte;
return result;
}
else if (left_byte > block_size)
{
//num: 实际分配的块的个数
num = left_byte / block_size;
result = start_pool;
start_pool += num * block_size;
return result;
}
else
{
//内存池新大小
std::size_t byte_to_get = 2 * total_byte + round_up(heap_size >> 4);
if (left_byte > 0) {
//将最后的空间分配出去
obj *new_head = reinterpret_cast<obj*>(start_pool);
auto target_free_list = free_list + free_list_index(left_byte);
new_head->free_list_link = *target_free_list;
*target_free_list = new_head;
start_pool = end_pool = nullptr;
}
start_pool = static_cast<char*>(malloc(byte_to_get));
if (start_pool == nullptr) {
obj **target_free_list;
obj *head; //指向 free_list 的第一个内存块
/*
遍历块大小大于 block_size 的 free_list 以
获取空闲的内存块加入到内存池中
*/
for (std::size_t i = block_size + ALIGN; i <= MAX_BLOCK_SIZE; i += ALIGN) {
target_free_list = free_list + free_list_index(i);
head = *target_free_list;
if (head != nullptr) {
/*
如果有空闲块则加入到内存池中
*/
*target_free_list = head->free_list_link;
start_pool = reinterpret_cast<char*>(head);
end_pool = start_pool + i;
return chunk_alloc(block_size, num);
}
}
start_pool = reinterpret_cast<char*>(
malloc_allocator<T>::allocate(byte_to_get / sizeof(T)));
}
end_pool = start_pool + byte_to_get;
heap_size += byte_to_get;
return chunk_alloc(block_size, num);
}
}
chunk_alloc()可以说是整个分配器中最复杂的函数了，但是耐下心来也是可以理解的。chunk_alloc()负责向系统申请内存， 并且返回其首地址。
还记得在类中之前声明的静态变量吗，现在正是使用它们的时候了
//内存池起始位置
static char *start_pool;
//内存池结束位置
static char *end_pool;
static std::size_t heap_size;
我们先考虑简单的2种情况
if (left_byte > total_byte)
{
result = start_pool;
start_pool += total_byte;
return result;
}
else if (left_byte > block_size)
{
//num: 实际分配的块的个数
num = left_byte / block_size;
result = start_pool;
start_pool += num * block_size;
return result;
}
当有足够的内存时， 便直接分配。将 start_pool 赋值给 result， 同时 start_pool 后移 total_byte 单位。如果内存池剩余空间不足，但是至少还能分配1个块，我们就把剩余的空间尽可能分配出去。通过 left_byte / block_size 计算最多还能分配多少块。
但是当内存池连1个块都分配不了时， 就需要采取一些别的手段重新填充内存池了。
//内存池新大小
std::size_t byte_to_get = 2 * total_byte + round_up(heap_size >> 4);
if (left_byte > 0) {
//将最后的空间分配出去
obj *new_head = reinterpret_cast<obj*>(start_pool);
auto target_free_list = free_list + free_list_index(left_byte);
new_head->free_list_link = *target_free_list;
*target_free_list = new_head;
start_pool = end_pool = nullptr;
}
我们首先计算要重新给内存池分配多少空间(byte_to_get)。其中heap_size用来额外增加新内存池大小，避免内存池频繁重新分配。heap_size的值根据 byte_to_get 逐渐增加。接下来我们将内存池中剩余的内存加入到 free_list 中（不能浪费），这个时候内存池已经空空如也了。下一步就要正式请求内存了。
start_pool = static_cast<char*>(malloc(byte_to_get));
if (start_pool == nullptr) {
obj **target_free_list;
obj *head; //指向 free_list 的第一个内存块
/*
遍历块大小大于 block_size 的 free_list 以
获取空闲的内存块加入到内存池中
*/
for (std::size_t i = block_size + ALIGN; i <= MAX_BLOCK_SIZE; i += ALIGN) {
target_free_list = free_list + free_list_index(i);
head = *target_free_list;
if (head != nullptr) {
/*
如果有空闲块则加入到内存池中
*/
*target_free_list = head->free_list_link;
start_pool = reinterpret_cast<char*>(head);
end_pool = start_pool + i;
return chunk_alloc(block_size, num);
}
}
start_pool = reinterpret_cast<char*>(
malloc_allocator<T>::allocate(byte_to_get / sizeof(T)));
}
我们借助 malloc() 申请空间。如果 malloc 也无法得到内存的话会返回 nullptr。要是malloc也不行，那么我们现在该怎么办呢？ 答案是寻找 free_list 中空闲的内存块。也许 free_list 中还有未被使用的内存，我们可以尝试把它们加入到内存池中。
所以我们寻找大于 block_size 的空闲块，将它加入内存池。再递归调用自身返回。调用自身是为了重新分配内存给用户。因为我们现在只是为内存池重新获取了空间， 还没有返回用户需要的内存。（也就是接下来调用的 chunk_alloc 会执行前2个 if 分支）
那么我们连空闲块都没有的话又该如何？我们这个时候使用 malloc_allocator 来分配内存。malloc_allocator可以借助 oom_handler来处理内存不足的情况（如果有的话），亦或者直接抛出 bad_alloc 异常由用户自己处理。
在最后， 如果内存池分配成功的话，便重新设置 end_pool 与 heap_size，同时递归返回。
end_pool = start_pool + byte_to_get;
heap_size += byte_to_get;
return chunk_alloc(block_size, num);
好了，到现在有关 Alloctor 的所有内容都讲完了。我们已经实现了自己的分配器 free_list_allocator，我们接下来可以借助它为接下来的容器分配内存。下次应该就是要介绍我们的第一个容器 vector 了。
如果喜欢的话可以点个赞啊~
最后附上本篇文章的代码地址：free_list_allocator.h
以及github地址：https://github.com/Puppas/STL-in-Cpp11
