本节介绍@R_301_196@中的动态数组，数组链表，以及双向链表；
动态数组
说明几点
（1）@R_301_196@中数组和STL中的vector类似，当达到数组的已分配内存的上限时，会自动扩充数组的大小；
动态数组结构体声明
typedef struct {
void *elts; //数组的起始地址
ngx_uint_t nelts; //当前的已经使用元素的个数
size_t size; //一个元素的字节大小
ngx_uint_t nalloc; //最大可容纳元素的个数
ngx_pool_t *pool; //内存池对象
} ngx_array_t;
动态数组初始化
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; //当前的已经使用元素的个数，刚开始为0
array->size = size; //元素的字节大小
array->nalloc = n; //最大可容纳元素的个数
array->pool = pool;
array->elts = ngx_palloc(pool,n * size); //分配内存为n*size，其实是整个数据元素的大小
if (array->elts == NULL) {
return NGX_ERROR;
}
return NGX_OK;
}
动态数组创建
ngx_array_t *
ngx_array_create(ngx_pool_t *p,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;
}
动态数组销毁
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时才会释放
//任何在数组内存申请后调整d.last，会使得数组内存不可以释放
p->d.last -= a->size * a->nalloc; //释放可用的内存，主要是调整d.last
}
if ((u_char *) a + sizeof(ngx_array_t) == p->d.last) { //当此时地址正好等于p->d.last时才会释放
//任何在数组内存申请后调整d.last，会使得数组内存不可以释放
p->d.last = (u_char *) a; //释放可用的内存，主要是调整d.last
}
}
申请1个元素内存
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++; //更新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; //更新nalloc的容量
}
}
elt = (u_char *) a->elts + a->size * a->nelts; //指向添加元素的地址
a->nelts++; //已使用的个数加1
return elt;
}
申请n个元素内存
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; //更新nalloc的容量
} 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->nelts * a->size); //拷贝原内存数据到新的内存
a->elts = new; //更新新的地址
a->nalloc = nalloc; //更新nalloc的容量
}
}
elt = (u_char *) a->elts + a->size * a->nelts; //指向添加元素的地址
a->nelts += n; //已使用的个数加n
return elt;
}
数组链表
说明几点
（1）@R_301_196@中的数组链表，整体元素为一个链表元素，而一个链表元素分为一个数组和一些控制信息，当一个链表元素使用完后，申请另一个链表元素和数组内存，并用控制信息来连接起来；
链表元素声明
//链表元素节点
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;
链表头初始化
static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list,size_t size)
{
list->part.elts = ngx_palloc(pool,n * size); //链表元素节点申请的数据内存大小为n * size
if (list->part.elts == NULL) {
return NGX_ERROR;
}
list->part.nelts = 0; //表示该链表节点数组已经使用了多少个元素，初始为0
list->part.next = NULL; //指向链表的下一个链表元素为NULL
list->last = &list->part; //指向最后一个链表元素，初始化为第一个
list->size = size; //一个元素大小
list->nalloc = n; //数组中存放的元素个数
list->pool = pool;
return NGX_OK;
}
链表创建
ngx_list_t *
ngx_list_create(ngx_pool_t *pool,size_t size)
{
ngx_list_t *list;
list = ngx_palloc(pool,sizeof(ngx_list_t)); //申请一个ngx_list_t（管理）
if (list == NULL) {
return NULL;
}
if (ngx_list_init(list,pool,size) != NGX_OK) { //链表头初始化
return NULL;
}
return list;
}
申请1个数据元素的内存
void *
ngx_list_push(ngx_list_t *l)
{
void *elt;
ngx_list_part_t *last;
last = l->last;
//如果最后一个链表元素已经存满
if (last->nelts == l->nalloc) {
/* the last part is full,allocate a new list part */
last = ngx_palloc(l->pool,sizeof(ngx_list_part_t)); //链表元素
if (last == NULL) {
return NULL;
}
last->elts = ngx_palloc(l->pool,l->nalloc * l->size); //数据大小
if (last->elts == NULL) {
return NULL;
}
last->nelts = 0;
last->next = NULL;
//尾指针调整
l->last->next = last;
l->last = last;
}
elt = (char *) last->elts + l->size * last->nelts; //分配元素的起始地址，通过l->size * last->nelts来定位存放的地址
last->nelts++;
return elt;
}
双向链表
说明几点
（1）@R_301_196@的双向链表提供排序的功能，也支持两个链表的合并
双向链表声明
typedef struct ngx_queue_s ngx_queue_t;
struct ngx_queue_s {
ngx_queue_t *prev; //下一个元素
ngx_queue_t *next; //上一个元素
};
初始化
//初始化
#define ngx_queue_init(q) \
(q)->prev = q; \
(q)->next = q
插入操作
//插入头节点后面
#define ngx_queue_insert_head(h,x) \
(x)->next = (h)->next; \
(x)->next->prev = x; \
(x)->prev = h; \
(h)->next = x
//插入某节点后面
#define ngx_queue_insert_after ngx_queue_insert_head
//插入某节点前面
#define ngx_queue_insert_tail(h,x) \
(x)->prev = (h)->prev; \
(x)->prev->next = x; \
(x)->next = h; \
(h)->prev = x
判空
//判空
#define ngx_queue_empty(h) \
(h == (h)->prev)
其他操作
//获得链表头
#define ngx_queue_head(h) \
(h)->next
//获得链表尾
#define ngx_queue_last(h) \
(h)->prev
//获得链表哨兵
#define ngx_queue_sentinel(h) \
(h)
//获得某节点下一个节点
#define ngx_queue_next(q) \
(q)->next
//获得某节点上一个节点
#define ngx_queue_prev(q) \
(q)->prev
删除节点
#define ngx_queue_remove(x) \
(x)->next->prev = (x)->prev; \
(x)->prev->next = (x)->next; \
(x)->prev = NULL; \
(x)->next = NULL
#else
//删除节点x
#define ngx_queue_remove(x) \
(x)->next->prev = (x)->prev; \
(x)->prev->next = (x)->next
#endif
拆分链表
//拆分链表，分为h和n(q为首元素，q和n形成一个双向链表)
#define ngx_queue_split(h,q,n) \
(n)->prev = (h)->prev; \
(n)->prev->next = n; \
(n)->next = q; \
(h)->prev = (q)->prev; \
(h)->prev->next = h; \
(q)->prev = n;
合并链表
//两个链表连接成一个链表，将n添加到h后面 #define ngx_queue_add(h,n) \ (h)->prev->next = (n)->next; \ (n)->next->prev = (h)->prev; \ (h)->prev = (n)->prev; \ (h)->prev->next = h;
获得原始结构体
//获得原节点，利用偏移
#define ngx_queue_data(q,type,link) \
(type *) ((u_char *) q - offsetof(type,link))
说明几点
（1）q为链表所在的地址，如果真正的结构体地址为a，那么有 q - a =offsetof(type,link))；则a = q -offsetof(type,link))；
寻找中间节点
/*
* find the middle queue element if the queue has odd number of elements
* or the first element of the queue's second part otherwise
*/
//找到中间节点
ngx_queue_t *
ngx_queue_middle(ngx_queue_t *queue)
{
ngx_queue_t *middle,*next;
middle = ngx_queue_head(queue); //获得链表的头元素
if (middle == ngx_queue_last(queue)) { //只有一个元素时或没有元素时，直接返回
return middle;
}
next = ngx_queue_head(queue);
for ( ;; ) {
middle = ngx_queue_next(middle); //走一步
next = ngx_queue_next(next); //走1步
if (next == ngx_queue_last(queue)) {
return middle;
}
next = ngx_queue_next(next); //走2步
if (next == ngx_queue_last(queue)) {
return middle;
}
}
}
直接插入排序
/* the stable insertion sort */
//链表排序
void
ngx_queue_sort(ngx_queue_t *queue,ngx_int_t (*cmp)(const ngx_queue_t *,const ngx_queue_t *))
{
ngx_queue_t *q,*prev,*next;
q = ngx_queue_head(queue); //获得链表头元素
if (q == ngx_queue_last(queue)) { //只有一个元素时或没有元素时，直接返回
return;
}
//类似直接插入法
//要不等于哨兵，即不等于头节点
for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
prev = ngx_queue_prev(q);
next = ngx_queue_next(q);
ngx_queue_remove(q); //删除
do {
if (cmp(prev,q) <= 0) { //比前面的节点元素大，就break;
break;
}
prev = ngx_queue_prev(prev); //否则就一直往前走
} while (prev != ngx_queue_sentinel(queue));
ngx_queue_insert_after(prev,q); //插入到指定的位置
}
} 原文链接：https://www.f2er.com/datastructure/382667.html