General
Type Naming
在头文件 src/core/ngx_core.h 中,有如下的一些类型定义,观察会发现以字母 s 结尾代表结构体,以字母 t 结尾代表使用 typedef 定义后的新类型,ngx 代表 nginx 缩写。
typedef struct ngx_module_s ngx_module_t;
typedef struct ngx_conf_s ngx_conf_t;
typedef struct ngx_cycle_s ngx_cycle_t;
typedef struct ngx_pool_s ngx_pool_t;
typedef struct ngx_chain_s ngx_chain_t;
typedef struct ngx_log_s ngx_log_t;
typedef struct ngx_open_file_s ngx_open_file_t;
typedef struct ngx_command_s ngx_command_t;
typedef struct ngx_file_s ngx_file_t;
typedef struct ngx_event_s ngx_event_t;
typedef struct ngx_event_aio_s ngx_event_aio_t;
typedef struct ngx_connection_s ngx_connection_t;
typedef struct ngx_thread_task_s ngx_thread_task_t;
typedef struct ngx_ssl_s ngx_ssl_t;
typedef struct ngx_proxy_protocol_s ngx_proxy_protocol_t;
typedef struct ngx_ssl_connection_s ngx_ssl_connection_t;
typedef struct ngx_udp_connection_s ngx_udp_connection_t;
代码 1 - 1:typedef
常用功能宏定义代码 1 - 2 所示
#define ngx_abs(value) (((value) >= 0) ? (value) : - (value))
#define ngx_max(val1, val2) ((val1 < val2) ? (val2) : (val1))
#define ngx_min(val1, val2) ((val1 > val2) ? (val2) : (val1))
代码 1 - 2:define
Memory Management
Pool
Core Structure
HTTP 请求过程中,需要读取请求并返回应答,需要大量的内存读、写操作。Nginx 使用 ngx_pool_t 来管理内存,核心数据结构如代码 2 - 1 所示。
typedef struct {
u_char *last;
u_char *end;
ngx_pool_t *next;
ngx_uint_t failed;
} ngx_pool_data_t;
struct ngx_pool_s {
ngx_pool_data_t d;
size_t max;
ngx_pool_t *current;
ngx_chain_t *chain;
ngx_pool_large_t *large;
ngx_pool_cleanup_t *cleanup;
ngx_log_t *log;
};
代码 2 - 1:ngx_pool_s
Creation
接下来,根据内存池创建来具体分析,ngx_pool_t 结构通过方法 ngx_create_pool(代码 2 - 1) 来创建。其中,第 6 行确保分配的内存起始地址是以 16 字节对齐的,17 行确认单次在内存池中分配内存的上限。
ngx_pool_t *
ngx_create_pool(size_t size, ngx_log_t *log)
{
ngx_pool_t *p;
p = ngx_memalign(NGX_POOL_ALIGNMENT, size, log);
if (p == NULL) {
return NULL;
}
p->d.last = (u_char *) p + sizeof(ngx_pool_t);
p->d.end = (u_char *) p + size;
p->d.next = NULL;
p->d.failed = 0;
size = size - sizeof(ngx_pool_t);
p->max = (size < NGX_MAX_ALLOC_FROM_POOL) ? size : NGX_MAX_ALLOC_FROM_POOL;
p->current = p;
p->chain = NULL;
p->large = NULL;
p->cleanup = NULL;
p->log = log;
return p;
}
代码 2 - 2:ngx_create_pool
一个全新的 ngx_pool_t 结构如图 1 所示,last 指向第一个可写入位置,end 指向可用内存地址后,因此,end 位置是不可以写入内容的。注意:虚线框代表该类型变量不存在,或者说代表 NULL。
图 1:ngx_pool_t
一次从 Pool 结构体中分配内存大小不能超过 NGX_MAX_ALLOC_FROM_POOL,这个值为页面尺寸减去一,减一是为什么呢?
#define NGX_MAX_ALLOC_FROM_POOL (ngx_pagesize - 1)
代码 2 - 3:NGX_MAX_ALLOC_FROM_POOL
ngx_page_size 在方法 ngx_os_init 中获取,Linux/Unix 版本如代码 2 - 4 中实现如下所示,在第 20 行,使用系统方法获取内存页面大小。
ngx_int_t
ngx_os_init(ngx_log_t *log)
{
ngx_time_t *tp;
ngx_uint_t n;
#if (NGX_HAVE_LEVEL1_DCACHE_LINESIZE)
long size;
#endif
#if (NGX_HAVE_OS_SPECIFIC_INIT)
if (ngx_os_specific_init(log) != NGX_OK) {
return NGX_ERROR;
}
#endif
if (ngx_init_setproctitle(log) != NGX_OK) {
return NGX_ERROR;
}
ngx_pagesize = getpagesize();
ngx_cacheline_size = NGX_CPU_CACHE_LINE;
for (n = ngx_pagesize; n >>= 1; ngx_pagesize_shift++) { /* void */ }
#if (NGX_HAVE_SC_NPROCESSORS_ONLN)
if (ngx_ncpu == 0) {
ngx_ncpu = sysconf(_SC_NPROCESSORS_ONLN);
}
#endif
if (ngx_ncpu < 1) {
ngx_ncpu = 1;
}
#if (NGX_HAVE_LEVEL1_DCACHE_LINESIZE)
size = sysconf(_SC_LEVEL1_DCACHE_LINESIZE);
if (size > 0) {
ngx_cacheline_size = size;
}
#endif
ngx_cpuinfo();
if (getrlimit(RLIMIT_NOFILE, &rlmt) == -1) {
ngx_log_error(NGX_LOG_ALERT, log, errno,
"getrlimit(RLIMIT_NOFILE) failed");
return NGX_ERROR;
}
ngx_max_sockets = (ngx_int_t) rlmt.rlim_cur;
#if (NGX_HAVE_INHERITED_NONBLOCK || NGX_HAVE_ACCEPT4)
ngx_inherited_nonblocking = 1;
#else
ngx_inherited_nonblocking = 0;
#endif
tp = ngx_timeofday();
srandom(((unsigned) ngx_pid << 16) ^ tp->sec ^ tp->msec);
return NGX_OK;
}
代码 2 - 4:ngx_os_init
Small Allocation
分析完 ngx_pool_t 创建代码后,至少遗留了一个问题:ngx_pool_t 中的 current 与 ngx_pool_data_t 中的 next 是什么作用呢?简单分析一下,这两个指针应该和动态分配内存是关联的,这样不难找到分配方法中修改 next 及 current 的域,关键方法 ngx_palloc_small 在代码 2 - 5 中。
static ngx_inline void *
ngx_palloc_small(ngx_pool_t *pool, size_t size, ngx_uint_t align)
{
u_char *m;
ngx_pool_t *p;
p = pool->current;
do {
m = p->d.last;
if (align) {
m = ngx_align_ptr(m, NGX_ALIGNMENT);
}
if ((size_t) (p->d.end - m) >= size) {
p->d.last = m + size;
return m;
}
p = p->d.next;
} while (p);
return ngx_palloc_block(pool, size);
}
代码 2 - 5:ngx_palloc_small
假设初始化后的 ngx_pool_t 结构,经过有限次分配后,last 指向虚线位置,如果当前池中剩余内存足够分配,那么非常简单,只要向后移动 last 指针即可,如图 2 所示。
图 2:ngx_palloc_small
如果当前内存池中没有足够的内存分配,则需要通过 ngx_palloc_block 方法分配全新的内存池,详见代码 2 - 6。
static void *
ngx_palloc_block(ngx_pool_t *pool, size_t size)
{
u_char *m;
size_t psize;
ngx_pool_t *p, *new;
psize = (size_t) (pool->d.end - (u_char *) pool);
m = ngx_memalign(NGX_POOL_ALIGNMENT, psize, pool->log);
if (m == NULL) {
return NULL;
}
new = (ngx_pool_t *) m;
new->d.end = m + psize;
new->d.next = NULL;
new->d.failed = 0;
m += sizeof(ngx_pool_data_t);
m = ngx_align_ptr(m, NGX_ALIGNMENT);
new->d.last = m + size;
for (p = pool->current; p->d.next; p = p->d.next) {
if (p->d.failed++ > 4) {
pool->current = p->d.next;
}
}
p->d.next = new;
return m;
}
代码 2 - 6:ngx_palloc_block
在 ngx_palloc_block 方法的第 8 行,计算出传入的内存池大小,然后在第 9 行分配同样大小的新内存池。特别注意第 21,22 行,新的 ngx_pool_t 中只有 ngx_pool_data_t 的域是有用的,因此其他域的内存也当作可用内存使用了。最简单情况下,传入的 pool 是第一次内存不足,因此最终分配完内存后的布局如图 3 所示。因为是第一次失败,那么 p->d.next 一定为 NULL,因此 25 行至 29 行的 for 循环直接被跳过,只需要将原内存池的 ngx_pool_data_t 的 next 指针指向新创建的内存池即可,旧内存池的 current 指针不需要变化。
图 3:ngx_palloc_block
内存复用技巧的核心是,在 C 语言里,结构体内存是保证连续的,对于 ngx_pool_t 结构体而言,其内存布局如图 4 所示。
图 4:ngx_pool_t details
Large Allocation
还记得 NGX_MAX_ALLOC_FROM_POOL 常量吗,这个常量用于控制可以直接从内存池中分配内存大小的上限,当需要的内存超过该值时,就要从 ngx_pool_large_t 中直接分配了,结构体定义如代码 2 - 7 所示,显然是一个链表结构,仅保留了指向的下一个元素地址及分配的内存地址。
struct ngx_pool_large_s {
ngx_pool_large_t *next;
void *alloc;
};
代码 2 - 7:ngx_pool_large_s
大内存分配方法在 ngx_palloc_large 方法中实现,详见代码 2 - 8。其中第 8 行 ngx_alloc 是标准 C 方法 malloc 的封装方法。
static void *
ngx_palloc_large(ngx_pool_t *pool, size_t size)
{
void *p;
ngx_uint_t n;
ngx_pool_large_t *large;
p = ngx_alloc(size, pool->log);
if (p == NULL) {
return NULL;
}
n = 0;
for (large = pool->large; large; large = large->next) {
if (large->alloc == NULL) {
large->alloc = p;
return p;
}
if (n++ > 3) {
break;
}
}
large = ngx_palloc_small(pool, sizeof(ngx_pool_large_t), 1);
if (large == NULL) {
ngx_free(p);
return NULL;
}
large->alloc = p;
large->next = pool->large;
pool->large = large;
return p;
}
代码 2 - 8:ngx_palloc_large
代码 2- 8 第 15 行至第 24 行的 for 循环作用是看是否能找到一个可复用的 ngx_pool_large_t 结构体,如果可以复用,只要修改其 alloc 指针即可。从 26 行开始,是根据需要分配新的 ngx_pool_large_t 结构体并将其放入内存池的大内存链表头部。
图 5:ngx_palloc_large
Cleanup Allocation
除了按内存尺寸分类外,ngx_pool_t 还支持一种需要清理的内存管理,其结构如代码 2 - 9 所示,除了链表功能外,额外增加了 handler 清理方法。
struct ngx_pool_cleanup_s {
ngx_pool_cleanup_pt handler;
void *data;
ngx_pool_cleanup_t *next;
};
代码 2 - 9:ngx_pool_cleanup_s
在实际使用时,通过 ngx_pool_cleanup_add 方法来分配内存,注意第 6 行及第 12 行的分配方法中,会根据实际需要的内存大小来进行小内存、大内存的分配,这部分内容已经在前面的章节涵盖,不做详细的描述了。
ngx_pool_cleanup_t *
ngx_pool_cleanup_add(ngx_pool_t *p, size_t size)
{
ngx_pool_cleanup_t *c;
c = ngx_palloc(p, sizeof(ngx_pool_cleanup_t));
if (c == NULL) {
return NULL;
}
if (size) {
c->data = ngx_palloc(p, size);
if (c->data == NULL) {
return NULL;
}
} else {
c->data = NULL;
}
c->handler = NULL;
c->next = p->cleanup;
p->cleanup = c;
ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, p->log, 0, "add cleanup: %p", c);
return c;
}
代码 2 - 10:ngx_pool_cleanup_add
仅考虑小内存时,分配结果入图 6 所示,途中虚线代表原来指向位置,实现代表最终指向位置。
图 6:ngx_pool_cleanup_add
Chanis of Buffers
Buffer
缓存结构 ngx_buf_s 定义如代码 3 - 1 所示,需要关注的大致有四个指针:pos、last、start 和 end。接下来从具体使用中继续深入挖掘这四个指针的含义。15 行开始的类型定义是 C 语言中的位变量定义。
struct ngx_buf_s {
u_char *pos;
u_char *last;
off_t file_pos;
off_t file_last;
u_char *start; /* start of buffer */
u_char *end; /* end of buffer */
ngx_buf_tag_t tag;
ngx_file_t *file;
ngx_buf_t *shadow;
/* the buf's content could be changed */
unsigned temporary:1;
/*
* the buf's content is in a memory cache or in a read only memory
* and must not be changed
*/
unsigned memory:1;
/* the buf's content is mmap()ed and must not be changed */
unsigned mmap:1;
unsigned recycled:1;
unsigned in_file:1;
unsigned flush:1;
unsigned sync:1;
unsigned last_buf:1;
unsigned last_in_chain:1;
unsigned last_shadow:1;
unsigned temp_file:1;
/* STUB */ int num;
};
代码 3 - 1:ngx_buf_s
Temporary Buffer Allocation
临时缓存分配详细过程如代码 3 - 2 所示,内存来自于 ngx_pool_t,第 6 行分配一个 ngx_buf_t 结构体,并将其内容全部清零(使用了 calloc 系方法),第 30 行将 temporary 置位。
ngx_buf_t *
ngx_create_temp_buf(ngx_pool_t *pool, size_t size)
{
ngx_buf_t *b;
b = ngx_calloc_buf(pool);
if (b == NULL) {
return NULL;
}
b->start = ngx_palloc(pool, size);
if (b->start == NULL) {
return NULL;
}
/*
* set by ngx_calloc_buf():
*
* b->file_pos = 0;
* b->file_last = 0;
* b->file = NULL;
* b->shadow = NULL;
* b->tag = 0;
* and flags
*/
b->pos = b->start;
b->last = b->start;
b->end = b->last + size;
b->temporary = 1;
return b;
}
代码 3 - 2:ngx_create_temp_buf
创建完毕后,如图 7 所示:
图 7:ngx_create_temp_buf
Chains of Buffers Allocation
与缓存相关的还有一个 ngx_chain_s 结构体及 ngx_bufs_t 结构体,定义如代码 3 - 3 所示。不难猜出这两个结构体一个的作用是将分配的缓存通过链表的形式拼接起来,另一个的作用是描述链表长度及每个链表上可用的缓存大小,因为只有一个 size 值,因此链表上全部缓存的大小是相同的。
struct ngx_chain_s {
ngx_buf_t *buf;
ngx_chain_t *next;
};
typedef struct {
ngx_int_t num;
size_t size;
} ngx_bufs_t;
代码 3 - 3:ngx_chain
ngx_chain_t *
ngx_create_chain_of_bufs(ngx_pool_t *pool, ngx_bufs_t *bufs)
{
u_char *p;
ngx_int_t i;
ngx_buf_t *b;
ngx_chain_t *chain, *cl, **ll;
p = ngx_palloc(pool, bufs->num * bufs->size);
if (p == NULL) {
return NULL;
}
ll = &chain;
for (i = 0; i < bufs->num; i++) {
b = ngx_calloc_buf(pool);
if (b == NULL) {
return NULL;
}
/*
* set by ngx_calloc_buf():
*
* b->file_pos = 0;
* b->file_last = 0;
* b->file = NULL;
* b->shadow = NULL;
* b->tag = 0;
* and flags
*
*/
b->pos = p;
b->last = p;
b->temporary = 1;
b->start = p;
p += bufs->size;
b->end = p;
cl = ngx_alloc_chain_link(pool);
if (cl == NULL) {
return NULL;
}
cl->buf = b;
*ll = cl;
ll = &cl->next;
}
*ll = NULL;
return chain;
}
代码 3 - 4:ngx_create_chain_of_bufs
分配缓存链通过方法 ngx_create_chain_of_bufs 实现,如代码 3 - 4 所示。缓存相关的结构体内存全部来自于 ngx_pool_t,当然,并不能确保来自一同一个内存池,图 8 是一个内存池可以分配全部内存时的情况。
图 8:ngx_create_chain_of_bufs
代码 3 - 4 的 43 行作用是获取一个已经存在的或者重新分配一个 ngx_chain_t 结构体,特别注意,获取这个结构后,并没有做初始化操作,如代码 3 - 5。
ngx_chain_t *
ngx_alloc_chain_link(ngx_pool_t *pool)
{
ngx_chain_t *cl;
cl = pool->chain;
if (cl) {
pool->chain = cl->next;
return cl;
}
cl = ngx_palloc(pool, sizeof(ngx_chain_t));
if (cl == NULL) {
return NULL;
}
return cl;
}
代码 3 - 5:ngx_alloc_chain_link
Chain Copy
ngx_chain_add_copy 是将两个 ngx_chain_t 结构进行合并,将一个追加到另一个后面。第一个 ngx_chain_t 使用指向指针的指针进行参数传递的原因是为了对它进行修改。 代码 3 - 6 的第 8 行到第 10 行是在找 chain 中的最后一个元素,查找结束之后,ll 指向的是最后一个元素的 next 字段。
ngx_int_t
ngx_chain_add_copy(ngx_pool_t *pool, ngx_chain_t **chain, ngx_chain_t *in)
{
ngx_chain_t *cl, **ll;
ll = chain;
for (cl = *chain; cl; cl = cl->next) {
ll = &cl->next;
}
while (in) {
cl = ngx_alloc_chain_link(pool);
if (cl == NULL) {
*ll = NULL;
return NGX_ERROR;
}
cl->buf = in->buf;
*ll = cl;
ll = &cl->next;
in = in->next;
}
*ll = NULL;
return NGX_OK;
}
代码 3 - 6:ngx_chain_add_copy
接下来的第二个循环,遍历需要复制的 ngx_chain_t 结构,从 pool 中创建新的 ngx_chain_t,这里并不创建新的负载来进行深拷贝,而是直接指向原来的已经存在的内存。接下来将新创建的 ngx_chain_t 附加到第一个循环中找到的最后一个元素后面,当遍历到最后一个元素,就完成了两个结构的合并。整个过程见图 9。
图 9:ngx_chain_add_copy
General Purpose Queue
代码 4 - 1 中第 1 行是告诉编译器后面会定义 ngx_queue_s 结构体,但是,在 ngx_queue_s 中已经可以使用 ngx_queue_t 的指针类型了。
typedef struct ngx_queue_s ngx_queue_t;
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};
代码 4 - 1:ngx_queue_s
通过 ngx_queue_init 宏定义,可以判断这个队列是一个双向循环链表。由于一般情况下,循环链表不需要头节点,因此还可判断,通用队列也是不存在头节点的。通用队列示意图如图 10。
#define ngx_queue_init(q) \
(q)->prev = q; \
(q)->next = q
代码 4 - 2:ngx_queue_init
图 10:ngx_queue_t
通过图 10 及代码 4 - 1 可以发现明显的问题,这个队列是没有负载的,再仔细阅读代码发现一个宏定义:ngx_queue_data,这个宏应该是获取队列负载的,代码 4 - 3。
#define ngx_queue_data(q, type, link) \
(type *) ((u_char *) q - offsetof(type, link))
代码 4 - 3:ngx_queue_data
通过宏定义中的名称猜测及测试代码验证,查找负载的过程大致如图 11 所示。这样的好处有:第一,通用队列的结构体可以在目标结构体中的任意位置出现;第二,一个目标结构可以根据需要,挂载多个通用队列来形成复杂的十字链表等结构,因为每一个队列都有一个独立的结构体,所以完全不会互相影响。
图 11:ngx_queue_data
Binary Radix Tree
代码 5-1 是字典树的结构体,根据节点结构体中的左右两个分支,可以判断这是一个二叉树。一般见到的字典树都是以字符作为建,有 26 个子节点,或者是通过类似于 map 类型的哈希表保存子节点。这个字典树使用二进制数字作为键,左右两个分支分别代表了 0 和 1,图 12 是对于这个字典树的示意图。
struct ngx_radix_node_s {
ngx_radix_node_t *right;
ngx_radix_node_t *left;
ngx_radix_node_t *parent;
uintptr_t value;
};
typedef struct {
ngx_radix_node_t *root;
ngx_pool_t *pool;
ngx_radix_node_t *free;
char *start;
size_t size;
} ngx_radix_tree_t;
代码 5-1:ngx_radix_node_s
图 12:ngx_radix_node_s
mask 在这里表示的是 key 的有效位数,图 13 以上面的字典树为例,插入 key 为 0x08000000,mask = 0xF8000000
ngx_int_t
ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
uintptr_t value)
{
uint32_t bit;
ngx_radix_node_t *node, *next;
bit = 0x80000000;
node = tree->root;
next = tree->root;
while (bit & mask) {
if (key & bit) {
next = node->right;
} else {
next = node->left;
}
if (next == NULL) {
break;
}
bit >>= 1;
node = next;
}
if (next) {
if (node->value != NGX_RADIX_NO_VALUE) {
return NGX_BUSY;
}
node->value = value;
return NGX_OK;
}
while (bit & mask) {
next = ngx_radix_alloc(tree);
if (next == NULL) {
return NGX_ERROR;
}
next->right = NULL;
next->left = NULL;
next->parent = node;
next->value = NGX_RADIX_NO_VALUE;
if (key & bit) {
node->right = next;
} else {
node->left = next;
}
bit >>= 1;xv
node = next;
}
node->value = value;
return NGX_OK;
}
Array
Core Structure
ngx_array_t 数据结构如代码 6 - 1 所示。
typedef struct {
void *elts;
ngx_uint_t nelts;
size_t size;
ngx_uint_t nalloc;
ngx_pool_t *pool;
} ngx_array_t;
代码 6 - 1:ngx_array_t
Creation
接下来,根据数组创建来具体分析,ngx_array_t 结构通过 ngx_array_init(代码 6 - 2)来创建。结合 ngx_array_t 结构可以得出结论,nelts 和 nalloc 分别代表数组中存储的数据 elts 个数和内存池可分配内存个数,size 代表数组和内存分配的每块大小,并且如果仔细观察会发现代表数量的标识符都是以字母 n 开头。
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;
}
代码 6 - 2:ngx_array_init
一个全新的 ngx_array_t 结构图如图 14 所示。
图 14:ngx_array_t
Single Push
分析完 ngx_array_t 创建代码后,下面来研究数组数据的增加,关键代码在代码 6 - 3 中。
void *
ngx_array_push(ngx_array_t *a)
{
void *elt, *new;
size_t size;
ngx_pool_t *p;
if (a->nelts == a->nalloc) {
/* the array is full */
size = a->size * a->nalloc;
p = a->pool;
if ((u_char *) a->elts + size == p->d.last
&& p->d.last + a->size <= p->d.end)
{
/*
* the array allocation is the last in the pool
* and there is space for new allocation
*/
p->d.last += a->size;
a->nalloc++;
} else {
/* allocate a new array */
new = ngx_palloc(p, 2 * size);
if (new == NULL) {
return NULL;
}
ngx_memcpy(new, a->elts, size);
a->elts = new;
a->nalloc *= 2;
}
}
elt = (u_char *) a->elts + a->size * a->nelts;
a->nelts++;
return elt;
}
代码 6 - 3:ngx_array_push
观察代码可以发现 ngx_array_push 函数实际上是为了保证数组中能够存储 1 个 size 大小的数据,并将数组中存储的数据末端指针返回。实现这个功能需要分为两种情况,第一种是存储的数据还未占满数组,这种情况比较简单,直接将 nelts 计数加 1 即可;另一种情况是存储的数据占满数组,这时会根据内存池是否有足够的空间又分为两种情况,当内存池足够大时,将 last 指针向后移动 size 大小并将 nalloc 计数加 1,当内存池不够时,重新分配内存,数组大小变为之前的 2 倍,具体过程如图 15 所示。
图 15:ngx_array_push
Multiple Push
ngx_array_t 的另一种 push 方式是一次性 push 多个,逻辑与 single push 完全相同,有一点需要注意的是数组扩容时不一定扩容数组长度 2 倍,当增加的数据总长度大于等于数组长度时,会扩容增加数据长度的 2 倍,如代码 6 - 4 的 31 行所示。
void *
ngx_array_push_n(ngx_array_t *a, ngx_uint_t n)
{
void *elt, *new;
size_t size;
ngx_uint_t nalloc;
ngx_pool_t *p;
size = n * a->size;
if (a->nelts + n > a->nalloc) {
/* the array is full */
p = a->pool;
if ((u_char *) a->elts + a->size * a->nalloc == p->d.last
&& p->d.last + size <= p->d.end)
{
/*
* the array allocation is the last in the pool
* and there is space for new allocation
*/
p->d.last += size;
a->nalloc += n;
} else {
/* allocate a new array */
nalloc = 2 * ((n >= a->nalloc) ? n : a->nalloc);
new = ngx_palloc(p, nalloc * a->size);
if (new == NULL) {
return NULL;
}
ngx_memcpy(new, a->elts, a->nelts * a->size);
a->elts = new;
a->nalloc = nalloc;
}
}
elt = (u_char *) a->elts + a->size * a->nelts;
a->nelts += n;
return elt;
}
代码 6 - 4:ngx_array_push_n
Destroy
数组的创建和增加都有了,当然少不了删除功能了,下面看一下 ngx_array_t 的删除函数。
void
ngx_array_destroy(ngx_array_t *a)
{
ngx_pool_t *p;
p = a->pool;
if ((u_char *) a->elts + a->size * a->nalloc == p->d.last) {
p->d.last -= a->size * a->nalloc;
}
if ((u_char *) a + sizeof(ngx_array_t) == p->d.last) {
p->d.last = (u_char *) a;
}
}
代码 6 - 5:ngx_array_destroy
删除共分为 2 步,第一步删除数组内容;第二步删除数组结构,如图 16 所示。
图 16:ngx_array_destroy
List
list 的数据结构如代码 7 - 1 所示。ngx_list_t
是 ngx_list_part_s
组成的链表,ngx_list_part_s
是长度特定数组,当数组放满了之后,就会分配新的数组,以链表的形式放在原有数组的后面。这里的 last 指针指向的是最新创建的数组。
struct ngx_list_part_s {
void *elts;
ngx_uint_t nelts;
ngx_list_part_t *next;
};
typedef struct {
ngx_list_part_t *last;
ngx_list_part_t part;
size_t size;
ngx_uint_t nalloc;
ngx_pool_t *pool;
} ngx_list_t;
代码 7 - 1:ngx_list_t
图 17:ngx_list_t
需要稍微注意一下 ngx_list_t
的遍历写法,这一部分没有使用函数进行封装,它最外层是链表的遍历,里层是数组遍历。等数组遍历到末尾之后,会将指针移动到下一个数组,然后将指针的索引置为 0。
/*
*
* the iteration through the list:
*
* part = &list.part;
* data = part->elts;
*
* for (i = 0 ;; i++) {
*
* if (i >= part->nelts) {
* if (part->next == NULL) {
* break;
* }
*
* part = part->next;
* data = part->elts;
* i = 0;
* }
*
* ... data[i] ...
*
* }
*/
代码 7 - 2:ngx_list_t iteration