SGI STL二级空间适配器源码分析
为什么要使用空间适配器
要知道为什么要使用空间适配器，我们先看一下下面这段代码
#include <iostream>
using namespace std;
template<typename T>
class Vector
{
public:
// 按指定size进行构造，size个空间，没有元素
Vector(int size = 0):mSize(size),mCur(0)
{
if(size != 0)
{
mpVec = new T[size];
}
}
~Vector()
{
delete []mpVec;
}
// 按指定size进行构造,添加size个元素，元素值是val
Vector(int size, const T &val = T()):mSize(size),mCur(size)
{
mpVec = new T[size];
for(int i = 0; i < size; i++)
{
mpVec[i] = val;
}
}
// 按[first, last)区间的元素来构造Vector
Vector(T *first, T *last)
{
mCur = 0;
mpVec = new T[last-first];
mSize = last-first;
T *p = first;
for(; p != last; p++)
{
mpVec[mCur++] = *p;
}
}
// 从末尾添加元素
void push_back(const T &val)
{
if(full())
{
resize();
}
mpVec[mCur++] = val;
}
// 从末尾删除元素
void pop_back()
{
if(empty())
{
return ;
}
--mCur;
}
bool full()const
{
return mCur == mSize;
}
bool empty()const
{
return mCur == 0;
}
// 返回容器元素的个数
int size()const
{
return mCur;
}
// Vector的迭代器
class iterator
{
public:
iterator(T *p):_iter(p){}
bool operator != (const iterator &val)
{
return _iter != val._iter;
}
T& operator *()
{
return *_iter;
}
void operator++ ()
{
++_iter;
}
private:
T *_iter;
};
iterator begin()
{
return iterator(mpVec);
}
iterator end()
{
return iterator(mpVec+mCur);
}
private:
T *mpVec;
int mCur;
int mSize;
// 容器内存2倍扩容
void resize()
{
if(mSize != 0)
{
T *newdata = new T[mSize*2];
for(int i = 0; i < mCur; i++)
{
newdata[i] = mpVec[i];
}
delete []mpVec;
mpVec = newdata;
mSize *= 2;
}
else
{
mpVec = new T[1];
mSize = 1;
}
}
};
这里我们实现了一个简单的vector 类，假如我们需要一个长度为1000的A类型的数组，用该容器申请一块sizeof(A)*1000的内存块，并且调用1000次A的构造函数，有时候我们开辟一块内存并不希望调用对象的构造函数。这时候我们可以把内存的开辟与对象的构造分开，对象的析构与内存的释放分开，使得在一定程度上使容器更加高效。
所以可以将空间适配器实现为这样
template<typename T>
class Allocator
{
public:
T* allocate(size_t size) // 开辟内存
{
return (T*)malloc(size);
}
void deallocate(void *ptr) // 释放内存
{
free(ptr);
}
void construct(T *ptr, const T &val) // 构造对象
{
new (ptr) T(val);
}
void destroy(T *ptr) // 析构对象
{
ptr->~T();
}
};
这样内存的开辟与对象的构造分开，内存的释放与析构函数分开，一级的空间适配器只是简单地将malloc 与free 封装了一下，
二级空间适配器
二级空间适配器用来管理stl容器对内存的申请与释放
如果用户申请的内存大于128字节，直接调用一级适配器给用户分配内存，如果小于128字节，先遍历free-list 链表，二级空间适配器维护着一个free-list 的结构，该结构如下图所示，适配器按8字节对齐，将内存块的大小按8字节为单位分成一些固定大小的块，8字节大小的在第一个链表中，16字节在第二个链表中… 一次类推，知道128字节为止。
如果用户申请的内存字节数不是8的倍数，则按能够满足用户需求的最小的内存块进行分配，例如，用户要10字节的内存，直接分配给用户16字节
以 24 字节为例
如果用户索要一块24字节的内存，free-list中24字节的内存块分配完了，这时候，free-list 会向内存池中申请大小为24字节的内存块，如果内存池中有内存能够满足，则除了给用户分配一个24字节的内存块之外，还会给free-list中链接一部分24字节的内存块以供用户的使用。
如果内存池中的内存大小不能满足用户的申请，则内存池将自身剩余的内存挂入free-list的相应位置，然后向系统申请一块内存。申请成功，则分配给用户和free-list ,若失败，则遍历free-list 大于24字节的部分，找到一块分配给用户，并将剩余内存挂入相应free-list 的位置。
如果没找到则调用一级适配器。
源码分析
allocate
从源码中我们可以看出
static void* allocate(size_t __n)
{
void* __ret = 0;
/* 如果申请的内存大小大于 _MAX_BYTES 直接调用一级适配器*/
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
/* 计算__n大小的内存块所在的free-list 的位置 */
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif
_Obj* __RESTRICT __result = *__my_free_list;
/* 如果当前free-list中没有相应的内存块 就从内存池申请一块内存，
返回一块大小为__n的内存块 */
if (__result == 0)
__ret = _S_refill(_S_round_up(__n));
else {
/*否则直接返回一个内存块 */
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
};
_S_refill
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20;
/* 从内存池请求一大块内存放入free-list中 */
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
/* 如果只返回了一个内存块 直接返回*/
if (1 == __nobjs) return(__chunk);
__my_free_list = _S_free_list + _S_freelist_index(__n);
/* Build free list in chunk */
__result = (_Obj*)__chunk;
/* __my_free_list 指向 __chunk 位置开始向后的 __n个字节处 */
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
/* 如果__nobjs 的值大于 1 的情况*/
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
/* __next_obj 指向下一个内存块 */
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - 1 == __i) {
/* 如果当前内存块时最后一个内存块，就将链接地址置为 0 */
__current_obj -> _M_free_list_link = 0;
break;
} else {
/* 将当前内存块与后继的内存块建立链接 */
__current_obj -> _M_free_list_link = __next_obj;
}
}
return(__result);
}
_S_chunk_alloc
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{
char* __result;
/* 计算所需要的字节数 */
size_t __total_bytes = __size * __nobjs;
/* 计算当前内存池的剩余的字节数 */
size_t __bytes_left = _S_end_free - _S_start_free;
/* 如果剩余字节数大于所需要的字节数 就直接切割处__total_bytes个字节*/
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
/* 内存池的首地址指向切割后的位置 */
_S_start_free += __total_bytes;
return(__result);
/* 如果剩余字节数小于所需要的字节数 但是大于一个内存块的大小 ，就尽可能
多的切割处__size 大小的内存块 */
} else if (__bytes_left >= __size) {
/* 计算出最多能分配多少个大小为 __size 的内存块*/
__nobjs = (int)(__bytes_left/__size);
/* 计算出实际分配的内存大小 */
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
/*如果剩余的内存不够一个大小为 __size 的内存块*/
} else {
/* 计算出向系统申请的内存资源的大小 */
size_t __bytes_to_get =
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
// Try to make use of the left-over piece.
/* 如果内存池中有剩余的内存 */
if (__bytes_left > 0) {
/* 根据剩余内存的大小计算出该放到free-list的哪个位置 */
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
/* 将内存池中剩余的内存放到free-list 的相应的位置*/
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
/* 重新开辟一块内存 */
_S_start_free = (char*)malloc(__bytes_to_get);
/* 如果内存开辟失败 */
if (0 == _S_start_free) {
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
// Try to make do with what we have. That can't
// hurt. We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
/* 遍历从free-list 中较大的内存块中取出一块进行分配 */
for (__i = __size;
__i <= (size_t) _MAX_BYTES;
__i += (size_t) _ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p) {
/* 找到一块大于 __size 的内存块 __my_free_list 指向找到的这个内存块*/
*__my_free_list = __p -> _M_free_list_link;
/* 内存池的首地址指向这个内存块 */
_S_start_free = (char*)__p;
/* 内存池的尾地址指向这个内存块的结束位置 */
_S_end_free = _S_start_free + __i;
/* 递归调用，重新分配*/
return(_S_chunk_alloc(__size, __nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
/* 如果free-list中找不到比__size 大的内存块 */
_S_end_free = 0; // In case of exception.
/* 一级空间适配器分配内存 */
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
_S_heap_size += __bytes_to_get;
/* 内存池的尾指针指向新开辟内存的结尾 */
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));
}
}
deallocate
static void deallocate(void* __p, size_t __n)
{
/*如果申请的内存大小大于 _MAX_BYTES 就世界调用一级适配器的释放函数 */
if (__n > (size_t) _MAX_BYTES)
malloc_alloc::deallocate(__p, __n);
else {
/* 如果小于 _MAX_BYTES 则回收到free-list 的 计算出在自由链表中的位置 */
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
/*__q 指向了需要回收的内存块 */
_Obj* __q = (_Obj*)__p;
// acquire lock
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif /* _NOTHREADS */
/*类似于链表中的头插法，将需要回收的资源放入链表中*/
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;
// lock is released here
}
}