STL::空间配置器
程序员文章站
2022-03-23 12:54:13
...
//我们知道空间配置器在实现的时候其实是封装了一层malloc,如果定义了__USE_MALLOC宏就用一级空间配置器,
//没有的话就是二级空间配置器.
///////////////////////////////////////////
//////////一级空间配置器(内存大于128b)
//1、申请空间,利用allocate,释放空间使用deallocate
//2、申请空间失败调用异常处理函数
//二级空间配置器就是负责小块内存的分配
template<int inst>
class __DefaultAllocTemplate
{
//二级空间配置器中首先包含一个内存池,其次就是一个*链表
public:
static void* Allocate(size_t bytes)
{
if (bytes > (size_t)_MAX_BYTES)
{
//这是内存池中空间数量的最大值,所以必须向一级空间配置器申请
}
//先在*链表中找出对应bytes的位置,看此位置下面有没有挂空间
size_t index = FREE_LIST_INDEX(bytes);
Obj* result;
result = _free_list[index];
if (result == 0){
//对应位置没有空间,这是就应该去内存池中申请
//bytes个空间,但是注意拿下来应该也要是8的倍数
void* res = Refill(ROUND_UP(bytes);
}
//拿走一个bytes大小的空间,相当于头删
_free_list[index] = result->free_list_link;
return result;
}
size_t FREE_LIST_INDEX(size_t bytes){
//算出Bytes在*链表中映射的下标
return (bytes + _ALIGIN - 1) / _ALIGIN - 1;
}
size_t ROUND_UP(size_t bytes){
//计算给定的bytes取整到_ALIGIN的整数倍,此处_ALIGIN是8,所以处理成8的倍数就是保证处理
//后的第三位都为0,其他任意就都可以被8整除
return (bytes + _ALIGIN - 1)&~(_ALIGIN - 1);
}
static void* Refill(size_t bytes)
{
//此时系统默认一次取出20个对象的空间(这是因为一些容器在插入元素时就会增容申请空间,
//本来他们的这种操作就是线程不安全的,所以就要尽量的避免频繁的去取,假如一个正在insert申请空间,
//另外一个也要申请空间就会产生死锁)
size_t nobjs = 20;
char* chunk = ChunkAllocate(bytes, nobjs);
if (nobjs == 1){
//如果只有一个那就直接返回
return chunk;
}
//20个对象成功申请到,就返回一个,将剩余的19个直接挂在*链表的对应位置处
size_t index = FREE_LIST_INDEX(bytes);
Obj** myfreelist = _free_list + index;
//本来一个格子里面就是一个Obj*,因为要头插用一个二级指针来保存当前格子的地址。
Obj* result = (Obj*)chunk;//返回的空间的地址
Obj* next_obj = (Obj*)(chunk + bytes);
Obj* cur_obj;
for (size_t i = 0; i < 19; i++){
cur_obj = next_obj;
next_obj = (Obj*)((char*)(next_obj + bytes));
cur_obj->free_list_link = next_obj;
}
cur_obj->free_list_link = 0;
return result;
}
//bytes:一个对象的大小,nobjs:对象的个数
static char* ChunkAllocate(size_t bytes, size_t nobjs)
{
//本来是想要20个对象的空间,此处处理的时候如果够20个就拿走20个,
//如果不够再看够不够至少一个对象的,假如向够的话就返回一个对象,
//连一个对象也分配不出来了此时有两种解决方法
//1、直接向系统申请
//2、在*链表中index后面的位置去找
size_t totalbytes = bytes*nobjs;
size_t bytesleft = _end_free - _start_free;
if (bytesleft > totalbytes){
//说明空间足以分配出20个对象。
return _start_free;
_start_free += totalbytes;
}
//不足以分配20个对象,但起码够一个对象,有多少拿多少
if (bytesleft >= bytes){
nobjs = (_end_free - _start_free) / bytes;
_start_free += nobjs*bytes;
return _start_free;
}
//此时内存池已经没有办法分配出一个对象的空间了,
//此时要做两件事首先将内存池中剩余的空间挂到*链表上,避免了内存碎片
if (bytesleft > 0){
Obj** myfreelist = _free_list + FREE_LIST_INDEX(bytesleft);
((Obj*)_start_free)->free_list_link = *myfreelist;
*myfreelist = (Obj*)_start_free
}
//其次就是重新向系统申请内存,这时就要求申请2*totalbytes再多一点(8个字节)相当于40倍的bytes
size_t bytes_to_get = 2 * totalbytes + ROUND_UP(heap_size >> 4);
_start_free = (char*)malloc(bytes_to_get);
if (_start_free == NULL){
//说明向堆申请空间的时候也失败了,尝试向*链表Bytes对应位置后面的空间
Obj** myfreelist = _free_list + FREE_LIST_INDEX(bytes);
Obj* p;
for (int i = index + 1; i < 15; i++){
myfreelist = _free_list + i;
p = *myfreelist;
if (p != NULL){
*myfreelist = p->free_list_link;
_start_free = (char)* p;
_end_free = _start_free + (i+1)*_ALIGIN;
return (ChunkAllocate(bytes, nobjs));
}
}
//说明链表中也没有了可以申请的空间,此时就要依赖我们的一级空间配置器
heap_size += bytes_to_get;
_start_free += bytes_to_get;
return (ChunkAllocate(bytes, nobjs));
}
}
private:
char* _start_free;
char* _end_free;
enum{_ALIGIN = 8};//这是*链表每一格代表的空间数
enum{_MAX_BYTES = 128};//*链表总共空间的大小
enum{_FREE_LIST_SIZE=_MAX_BYTES/_ALIGIN};
typedef union Obj{
union Obj* free_list_link;
char client_data[1];
}Obj;//将*链表想象成哈希表,下面还会挂链表
Obj* _free_list[_FREE_LIST_SIZE];//顺序表,每个元素是一个Obj*的对象
};