ngx_array_t 動(dòng)態(tài)數(shù)組簡(jiǎn)介
- nginx所包裝的動(dòng)態(tài)數(shù)組和C++STL庫(kù)中的vector容器類(lèi)似,vector容器基于動(dòng)態(tài)數(shù)組寫(xiě)的,即其本質(zhì)也是一個(gè)動(dòng)態(tài)數(shù)組.
- 數(shù)組的優(yōu)點(diǎn)在于隨機(jī)訪(fǎng)問(wèn)數(shù)組中的任意一個(gè)元素的時(shí)間復(fù)雜度為O(1).即常量級(jí).但是唯一的缺點(diǎn)是其大小需要預(yù)先設(shè)定,并且是一塊連續(xù)的內(nèi)存,且這片內(nèi)存的大小是固定的了.
為了克服這個(gè)缺點(diǎn),動(dòng)態(tài)數(shù)組應(yīng)運(yùn)而生了. - ngx_array_t 內(nèi)置了Nginx封裝的內(nèi)存池,因此,它分配的內(nèi)存也是在內(nèi)存池中申請(qǐng)得到.
ngx_array_t容器具備的優(yōu)點(diǎn)
- 訪(fǎng)問(wèn)速度快
- 允許元素個(gè)數(shù)具備不確定性
- 負(fù)責(zé)元素占用內(nèi)存的分配,這些內(nèi)存將由內(nèi)存池統(tǒng)一管理
ngx_array_t數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)
#include <stdio.h>
typedef struct ngx_array_s ngx_array_t;
struct ngx_array_s{
void *elts;//elts指向數(shù)組的首地址
ngx_uint_t nelts;//nelts是數(shù)組中已經(jīng)使用的元素個(gè)數(shù)
size_t size;//每個(gè)元素占用內(nèi)存的大小
ngx_uint_t nalloc;//當(dāng)前數(shù)組中能夠容納元素個(gè)數(shù)的總大小
ngx_pool_t *pool;//內(nèi)存池對(duì)象,管理內(nèi)存分配
};
ngx_array_t 的創(chuàng)建方法
- 調(diào)用ngx_array_init方法初始化動(dòng)態(tài)數(shù)組(已經(jīng)存在一個(gè)該數(shù)據(jù)類(lèi)型的變量)
- 調(diào)用ngx_array_create來(lái)創(chuàng)建一個(gè)動(dòng)態(tài)數(shù)組,前提是這個(gè)數(shù)組還沒(méi)有創(chuàng)建
注意這二者的區(qū)別,即這兩個(gè)函數(shù)的返回值不同,init返回一個(gè)狀態(tài)標(biāo)識(shí),create返回一個(gè)ngx_array_t類(lèi)型的指針
static ngx_inline ngx_int_t
ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
/*
* set "array->nelts" before "array->elts", otherwise MSVC thinks
* that "array->nelts" may be used without having been initialized
*/
array->nelts = 0;
array->size = size;
array->nalloc = n;
array->pool = pool;
array->elts = ngx_palloc(pool, n * size);
if (array->elts == NULL) {
return NGX_ERROR;
}
return NGX_OK;
} //返回一個(gè)整形值
ngx_array_t *
ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size)
{
ngx_array_t *a;
a = ngx_palloc(p, sizeof(ngx_array_t));
if (a == NULL) {
return NULL;
}
if (ngx_array_init(a, p, n, size) != NGX_OK) {
return NULL;
}
return a;
}//返回一個(gè)ngx_array_t的指針
書(shū)中提到
因?yàn)閚gx_array_destroy是在內(nèi)存池中銷(xiāo)毀動(dòng)態(tài)數(shù)組及其分配的元素內(nèi)存的(如果動(dòng)態(tài)數(shù)組的ngx_array_t結(jié)構(gòu)體內(nèi)存時(shí)利用棧等非內(nèi)存池方式分配,那么調(diào)用ngx_array_destroy會(huì)導(dǎo)致不可預(yù)估的錯(cuò)誤),所以它必須與ngx_array_create配對(duì)使用!
動(dòng)態(tài)數(shù)組的擴(kuò)容方式
當(dāng)已經(jīng)使用的元素個(gè)數(shù)達(dá)到動(dòng)態(tài)數(shù)組與分配元素的個(gè)數(shù)時(shí),通過(guò)兩種方式來(lái)進(jìn)行擴(kuò)容
- ngx_array_push 會(huì)申請(qǐng)sizeof(ngx_array_t)大小的內(nèi)存
- ngx_array_push_n 會(huì)申請(qǐng)n * sizeof(ngx_array_t)大小的內(nèi)存
每次擴(kuò)容的大小將受制于內(nèi)存池的以下兩種情況
- 如果當(dāng)前內(nèi)存池中剩余的空間大于本次需要新增的空間的話(huà),那么就是正常擴(kuò)充相應(yīng)大小的內(nèi)存.
- 如果當(dāng)前內(nèi)存池剩余空間不足以擴(kuò)充相應(yīng)大小的內(nèi)存時(shí),那么這個(gè)時(shí)候需要注意,對(duì)于1.來(lái)說(shuō),會(huì)擴(kuò)充原動(dòng)態(tài)數(shù)組的容量的一倍.
對(duì)于2.如果n小于原先動(dòng)態(tài)數(shù)組的容量,將會(huì)擴(kuò)充一倍,如果n大于原先動(dòng)態(tài)數(shù)組的容量,那么會(huì)擴(kuò)充2*n大小的空間,擴(kuò)容超過(guò)了一倍.
這體現(xiàn)了nginx預(yù)估用戶(hù)行為的設(shè)計(jì)思想.
總結(jié)
今天總共看了兩個(gè)數(shù)據(jù)結(jié)構(gòu),而且斗地主也入門(mén)了.如果地主是你的上家,壓死他!!
和同學(xué)一起打斗地主,他當(dāng)參謀,一共打了一萬(wàn)多的歡樂(lè)豆,一個(gè)美好的午休時(shí)光,歡樂(lè)豆都被我敗光了!!
斗地主從入門(mén)到精通啊,我發(fā)現(xiàn)我身邊的人都是斗地主大神.
額,nginx看的效率還是比編程珠璣看的高的,畢竟這本書(shū)值得學(xué)習(xí),如果想在后端發(fā)展以及服務(wù)器這方面發(fā)展的同學(xué),都可以拿點(diǎn)源碼來(lái)看看,邊寫(xiě)邊學(xué)習(xí),效果不錯(cuò).我的markdown還是沒(méi)用出花樣來(lái)啊!繼續(xù)加油..\T*T/
明天試著整理一下紅黑樹(shù),我感覺(jué)得先去復(fù)習(xí)一下二叉樹(shù)了,明天再刷幾道關(guān)于二叉樹(shù)的劍指offer先.
預(yù)知后事如何,且聽(tīng)boomshakalaka.
