其实Nginx自定义数据结构字符串（String）数组（Array）链表（List）的问题并不复杂，但是又很多的朋友都不太了解，因此呢，今天小编就来为大家分享Nginx自定义数据结构字符串（String）数组（Array）链表（List）的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！

字符串（string）数组（array）链表（list）队列（queue）哈希（hash）红黑树（rbtree）基数树（radix_tree）

一、字符串

这个比较简单。其实和Redis的SDS设计类似。使用len字段保证字符串的二进制安全，解决字符串被’\0’截断的问题。

typedef 结构体{ size_t len; u_char *data;} ngx_str_t;Nginx为我们提供了字符串处理相关的宏

二、数组

Nginx 数组占用内存池上的连续空间。它存储的数据类型是确定的，容量是可以扩展的。这样的数组更容易使用。

文件名：ngx_array.h

typedef 结构{ void *elts; ngx_uint_t 内尔茨； size_t 尺寸； ngx_uint_t 分配； ngx_pool_t *池；} ngx_array_t;字段说明：

elts：数据块，指向实际存储的数据。

nelts：当前数组中存储的数据数量。

size：每个数据的大小。

nalloc：分配区域的大小，即当前数组可以存储的数据量。

pool：存储当前数组的内存池。

文件名：ngx_array.c

void * ngx_array_push(ngx_array_t *a){ void *elt, *new; size_t 尺寸； ngx_pool_t *p; if (a-nelts==a-nalloc) { /* 数组已满*/size=a-size * a -nalloc; p=池； if ((u_char *) a-elts + size==p-d.last p-d.last + a-size=p-d.end) { /* * 数组分配是池中的最后一个* 并且有空间用于新分配* /p-d.last +=a-size; a-nalloc++； } else { /* 分配一个新数组*/new=ngx_palloc(p, 2 * size); if (new==NULL) { 返回NULL; ngx_memcpy（新，a-elts，大小）； a-elts=新的； a-nalloc *=2; } } elt=(u_char *) a-elts + a-size * a-nelts ; a-nelts++；返回埃尔特；}

当存放数组的内存池有剩余空间时，插入的数据直接在当前内存池中向后扩展；

当存储数组的内存池空间不足时，需要开辟新的内存空间，将数组数据分配到新的内存地址，以保证数组数据的连续性。

当数组使用完毕释放时，可以直接释放内存池上的空间，而不需要将内存返回给操作系统，从而保证了内存申请和释放的效率。

释放的内存仍然可以用于其他目的，实现内存复用，减少系统开销。

三、链表

链表和数组的区别在于它的数据在内存中不连续，但是它的插入动作的时间复杂度只有O(1)。

我们先看一下链表的结构

文件名：ngx_list.h

typedef struct ngx_list_part_s ngx_list_part_t; //链表struct ngx_list_part_s { void *elts; //指向节点的实际数据区域（该数据区域可以存储size大小的nalloc元素） ngx_uint_t nelts; //实际存储的元素数量（当前节点存储的元素数量） ngx_list_part_t *next; //指向下一个节点};字段说明：

elts：指向节点数据的实际存储区域。

nelts：当前链表节点上分配的数据数量。

next：指向链表的下一个节点。

一般链表每个Node存储一条数据，但是Nginx的链表在一个Node上存储多条数据。

//nginx链表结构不是简单的链表，而是数组的链表。 typedef 结构{ ngx_list_part_t *last; //指向链表的最后一个数组元素。 ngx_list_part_t 部分； //链表第一个数组元素size_t size; //每个元素的大小ngx_uint_t nalloc; //每个节点包含的数据数量ngx_pool_t *pool; //链表所在内存池} ngx_list_t;字段说明：

last：链表的最后一个节点。

部分：链表的第一个节点。

size：每个数据的大小。

nalloc：链表每个节点所包含的数据数量。

pool：链表头所在的内存池。

链表相关操作API包括：

//创建链表ngx_list_t * ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size) //向链表插入数据void * ngx_list_push(ngx_list_t *l) 在ngx_list_create 中，会调用ngx_list_init 来初始化链表。

链表初始化后，通过ngx_list_push函数将数据插入到链表中。该函数定义如下：

无效*ngx_list_push(ngx_list_t *l){ 无效*elt; ngx_list_part_t *最后；最后=l-最后； if (last-nelts==l-nalloc) { /* 最后一部分已满，分配新的列表部分*/last=ngx_palloc(l-pool, sizeof(ngx_list_part_t));如果（最后==NULL）{返回NULL；最后elts=ngx_palloc(l-pool, l-nalloc * l-size); if (last-elts==NULL) { return NULL; }最后-nelts=0;上一个-下一个=NULL； l-最后一个-下一个=最后一个； l-最后=最后； }//如果当前节点有足够的空间，则只执行这2行Line elt=(char *) last-elts + l-size * last-nelts;最后-nelts++； return elt;} 不知道大家有没有注意到，插入链表时只传入一个链表指针，插入数组时也只传入一个链表指针。传入了数组指针，但没有传入要插入的数据。

这是因为上层的数据类型不确定，可以是任意数据类型，所以数据的拷贝分配就交给了上层，下层只负责分配空间。所以我们可以看到ngx_list_push和ngx_array_push的返回值都是void *来适应上层数据类型。