上一篇我們介紹了STL對象的構(gòu)造與析構(gòu)，這篇介紹STL內(nèi)存的配置與釋放。
STL有兩級空間配置器，默認是使用第二級。第二級空間配置器會在某些情況下去調(diào)用第一級空間配置器。空間配置器都是在allocate函數(shù)內(nèi)分配內(nèi)存，在deallocate函數(shù)內(nèi)釋放內(nèi)存。
第一級空間配置器
第一級配置器只是對malloc函數(shù)和free函數(shù)的簡單封裝，在allocate內(nèi)調(diào)用malloc，在deallocate內(nèi)調(diào)用free。同時第一級配置器的oom_malloc函數(shù)，用來處理malloc失敗的情況。如下所示：
allocate對malloc函數(shù)簡單封裝 :
static void *allocate(size_t n)
{ void *result = malloc(n); if (NULL == result)
result = oom_malloc(n); return result;
}
deallocate對free函數(shù)簡單封裝 :
static void deallocate(void *p, size_t) { free(p); }
oom_malloc調(diào)用外部提供的malloc失敗處理函數(shù)，然后重新試著再次調(diào)用malloc。重復執(zhí)行此過程，直到malloc成功為止 :
template <int inst>void* __malloc_alloc<inst>::oom_malloc(size_t n)
{ void (*my_malloc_handler)(); void *result; for (;;)
{
my_malloc_handler = malloc_alloc_oom_handler; if (NULL == my_malloc_handler)
__THROW_BAD_ALLOC;
(*my_malloc_handler)();
result = malloc(n); if (result) return result;
}
}
第二級空間配置器
第一級配置器直接調(diào)用malloc和free帶來了幾個問題：
1.內(nèi)存分配/釋放的效率低。2. 當配置大量的小內(nèi)存塊時，會導致內(nèi)存碎片比較嚴重。3. 配置內(nèi)存時，需要額外的部分空間存儲內(nèi)存塊信息，所以配置大量的小內(nèi)存塊時，還會導致額外內(nèi)存負擔。
第二級配置器維護了一個自由鏈表數(shù)組，每次需要分配內(nèi)存時，直接從相應的鏈表上取出一個內(nèi)存節(jié)點就完成工作，效率很高。
自由鏈表數(shù)組
自由鏈表數(shù)組其實就是個指針數(shù)組，數(shù)組中的每個指針元素指向一個鏈表的起始節(jié)點。數(shù)組大小為16，即維護了16個鏈表，鏈表的每個節(jié)點就是實際的內(nèi)存塊，相同鏈表上的內(nèi)存塊大小都相同，不同鏈表的內(nèi)存塊大小不同，從8一直到128。如下所示，obj為鏈表上的節(jié)點，free_list就是鏈表數(shù)組。
//自由鏈表union obj
{
union obj *free_list_link; char data[1];
};//自由鏈表數(shù)組static obj *volatile free_list[__NFREELISTS];
內(nèi)存分配
allocate函數(shù)內(nèi)先判斷要分配的內(nèi)存大小，若大于128字節(jié)，直接調(diào)用第一級配置器，否則根據(jù)要分配的內(nèi)存大小從16個鏈表中選出一個鏈表，取出該鏈表的第一個節(jié)點。若相應的鏈表為空，則調(diào)用refill函數(shù)填充該鏈表。如下：
template <bool threads>void *__default_alloc<threads>::allocate(size_t n)
{
obj *volatile *my_free_list;
obj *result; if (n > (size_t)__MAX_BYTES) //調(diào)用第一級配置器
return malloc_alloc::allocate(n);
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list; if (result == NULL)
{ //第n號鏈表無內(nèi)存塊，則準備重新填充該鏈表
void *r = refill(ROUND_UP(n)); return r;
} *my_free_list = result->free_list_link; return result;
}
填充鏈表
若allocate函數(shù)內(nèi)要取出節(jié)點的鏈表為空，則會調(diào)用refill函數(shù)填充該鏈表。
refill函數(shù)內(nèi)會先調(diào)用chunk_alloc函數(shù)從內(nèi)存池分配一大塊內(nèi)存，該內(nèi)存大小默認為20個鏈表節(jié)點大小，當內(nèi)存池的內(nèi)存也不足時，返回的內(nèi)存塊節(jié)點數(shù)目會不足20個。接著refill的工作就是將這一大塊內(nèi)存分成20份相同大小的內(nèi)存塊，并將各內(nèi)存塊連接起來形成一個鏈表。如下：
template <bool threads>void *__default_alloc<threads>::refill(size_t n)
{ int nobjs = __NOBJS; char *chunk = chunk_alloc(n, nobjs); //從內(nèi)存池獲取內(nèi)存
if (nobjs == 1) //只能分配一塊，則直接返回給調(diào)用者
return chunk;
obj *volatile *my_free_list;
obj *result, *next_obj, *current_obj;
result = (obj *)chunk;
my_free_list = free_list + FREELIST_INDEX(n); *my_free_list = next_obj = (obj *)(chunk + n); for (int i = 1; i < nobjs - 1; i++) //將剩下的區(qū)塊添加進鏈表 {
current_obj = next_obj;
next_obj = (obj *)(char *)(next_obj + n);
current_obj->free_list_link = next_obj;
} //最后一塊
current_obj = next_obj;
current_obj->free_list_link = NULL; return result;
}
內(nèi)存池
chunk_alloc函數(shù)內(nèi)管理了一塊內(nèi)存池，當refill函數(shù)要填充鏈表時，就會調(diào)用chunk_alloc函數(shù)，從內(nèi)存池取出相應的內(nèi)存。
在chunk_alloc函數(shù)內(nèi)首先判斷內(nèi)存池大小是否足夠填充一個有20個節(jié)點的鏈表，若內(nèi)存池足夠大，則直接返回20個內(nèi)存節(jié)點大小的內(nèi)存塊給refill。如下：
if (size_left >= total_size) //內(nèi)存池剩余空間滿足需求 {
result = start_free;
start_free += total_size; return result;
}
若內(nèi)存池大小無法滿足20個內(nèi)存節(jié)點的大小，但至少滿足1個內(nèi)存節(jié)點，則直接返回相應的內(nèi)存節(jié)點大小的內(nèi)存塊給refill；
else if (size_left >= size) //剩余空間不能全部滿足，但至少滿足一塊 {
nobjs = size_left / size;
result = start_free;
start_free += nobjs * size; return result;
若內(nèi)存池連1個內(nèi)存節(jié)點大小的內(nèi)存塊都無法提供，則chunk_alloc函數(shù)會將內(nèi)存池中那一點點的內(nèi)存大小分配給其他合適的鏈表，然后去調(diào)用malloc函數(shù)分配的內(nèi)存大小為所需的兩倍。若malloc成功，則返回相應的內(nèi)存大小給refill；若malloc失敗，會先搜尋其他鏈表的可用的內(nèi)存塊，添加到內(nèi)存池，然后遞歸調(diào)用chunk_alloc函數(shù)來分配內(nèi)存，若其他鏈表也無內(nèi)存塊可用，則只能調(diào)用第一級空間配置器，因為第一級空間配置器有malloc失敗的出錯處理函數(shù)，最終的希望只能寄托在那里了。
如下是整個chunk_alloc函數(shù)：
template <bool threads>char *__default_alloc<threads>::chunk_alloc(size_t size, int& nobjs)
{
size_t total_size = size * nobjs; char *result;
size_t size_left = end_free - start_free; if (size_left >= total_size) //內(nèi)存池剩余空間滿足需求 {
result = start_free;
start_free += total_size; return result;
} else if (size_left >= size) //剩余空間不能全部滿足，但至少滿足一塊 {
nobjs = size_left / size;
result = start_free;
start_free += nobjs * size; return result;
} else //連一個區(qū)塊都無法滿足 { if (size_left > 0) //將殘余內(nèi)存分配給其他合適的鏈表 {
obj *volatile *my_free_list = free_list + FREELIST_INDEX(size_left);
((obj *)start_free)->free_list_link = *my_free_list; //在頭部插入
*my_free_list = (obj *)start_free;
}
size_t bytes_to_get = 2 * total_size + ROUND_UP(heap_size >> 4);
start_free = (char *)malloc(bytes_to_get); if (start_free == NULL) //堆空間不足 { int i;
obj *volatile *my_free_list;
obj *p; for (i = size; i < __MAX_BYTES; i++)
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list; if (p != NULL)
{ *my_free_list = p->free_list_link;
start_free = (char *)p;
end_free = start_free + i; return chunk_alloc(size, nobjs);
}
}
end_free = NULL; //調(diào)用第一級配置器
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
}
heap_size += bytes_to_get;
end_free = start_free + heap_size; return chunk_alloc(size, nobjs);
}
}
內(nèi)存釋放
第二級配置器的deallocate函數(shù)并不會直接釋放內(nèi)存塊。當內(nèi)存塊大小大于128字節(jié)時才會直接釋放，否則會將內(nèi)存塊回收到相應的鏈表當中。如下：
void __default_alloc<threads>::deallocate(void *p, size_t n)
{ //大于__MAX_BYTES，則釋放該內(nèi)存
if (n > (size_t)__MAX_BYTES)
malloc_alloc::deallocate(p, n);
obj *q = (obj *)p;
obj *volatile *my_free_list;
my_free_list = free_list + FREELIST_INDEX(n); //小于__MAX_BYTES，則回收區(qū)塊,并未釋放
q->free_list_link = *my_free_list; *my_free_list = q;
}
內(nèi)存對外接口
STL對外提供了一個simple_alloc類，該類提供統(tǒng)一的接口：allocate函數(shù)、deallocate函數(shù)，使得外部無需關心使用的是幾級內(nèi)存配置器。另外simple_alloc類將外部所需的對象個數(shù)轉(zhuǎn)換為字節(jié)。如下。
template <typename T, typename Alloc>class simple_alloc
{public: static T *allocate(size_t n) // 個數(shù) { return n == 0 ? 0 : (T*)Alloc::allocate(n * sizeof(T)); // 將個數(shù)轉(zhuǎn)換為字節(jié) } static T *allocate(void)
{ return (T*)Alloc::allocate(sizeof(T));
} static void deallocate(T *p, size_t n) // 個數(shù) { if (n != 0)
Alloc::deallocate(p, n * sizeof(T));
} static void deallocate(T *p)
{
Alloc::deallocate(p, sizeof(T));
}
};
一款簡易版STL的實現(xiàn)，項目地址：https://github.com/zinx2016/MiniSTL/tree/master/MiniSTL
http://www.cnblogs.com/zxiner/p/7197054.html
延伸閱讀
- 擴展entity framework core 實現(xiàn)默認字符串長度,decimal精度,entity自動注冊和配置 2017-07-26
- 富文本編輯器UEditor自定義工具欄（一、基礎配置與字體、背景色、行間距、超鏈接實現(xiàn)） 2017-07-26
- 【.net 深呼吸】在運行階段修改應用配置文件 2017-07-26
- gradle的安裝，配置，構(gòu)建，研究，初體驗......（入職一周研究的第一個大知識點） 2017-07-25
- 編寫一個可配置的網(wǎng)頁信息提取組件 （二）—— 優(yōu)雅的.net core 配置系統(tǒng) 2017-07-25
- vue.js移動端app實戰(zhàn)1：初始配置 2017-07-24
- Python內(nèi)存管理機制 2017-07-21
- LINUX系統(tǒng)安全配置基線 2017-07-21
- 編寫一個可配置的網(wǎng)頁信息提取組件 2017-07-21
- c#通用配置文件讀寫類（xml,ini,json） 2017-07-21
擴展entity framework core 實現(xiàn)默認字符串長度,decimal精度,entity自動注冊和配置