Nginx自定义数据结构之字符串(String)数组(Array)链表(List)

701人浏览 2023-10-23 15:41:09

今天我们一起看下Nginx常用的数据结构。

Nginx基本数据结构有：

字符串(string)
数组(array)
链表(list)
队列(queue)
散列(hash)
红黑树(rbtree)
基数树(radix_tree)

一、字符串

这是比较简单其实和Redis的SDS设计差不多，用一个len字段来保证字符串的二进制安全，解决字符串被"\0"截断的问题。

typedef struct {
    size_t      len;
    u_char     *data;
} ngx_str_t;

Nginx 为我们提供了字符串处理相关的宏

二、数组

Nginx的数组占用内存池上一块连续的空间，它存放的数据类型是确定的，而且容量可以扩充，这样的数组更为易用。

文件名：ngx_array.h

typedef struct {
    void        *elts;
    ngx_uint_t   nelts;
    size_t       size;
    ngx_uint_t   nalloc;
    ngx_pool_t  *pool;
} ngx_array_t;

字段说明：

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

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

size：每个数据的大小。

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

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

文件名：ngx_array.c

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;
}

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

当存储数组的内存池空间不足时，需要开辟新的内存空间并将数组数据依次赋值到新内存地址上，以此来保证数组数据的连续性。

当数组使用完毕释放时，直接释放内存池上的空间即可，不用将内存交还给操作系统，从而保证申请和释放内存的高效性。

被释放的内存仍可以另作他用，实现内存的重复利用，减少了系统开销。

三、链表

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

我们来看下链表的结构

文件名：ngx_list.h

typedef struct ngx_list_part_s  ngx_list_part_t;
 //链表
struct ngx_list_part_s {
    void             *elts;     // 指向该节点实际的数据区(该数据区中可以存放nalloc个大小为size的元素)
    ngx_uint_t        nelts;    // 实际存放的元素个数(当前节点存放的元素个数)
    ngx_list_part_t  *next;     // 指向下一个节点
};

字段说明：

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

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

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

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

//  nginx链表结构 不是一个单纯的链表, 而是一个数组的链表。
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;

字段说明：

last：链表最后一个节点。

part：链表的第一个节点。

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函数向链表插入数据，函数定义如下：

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;
    }
		// 如果当前节点空间够，那么只会执行这2行
    elt = (char *) last->elts + l->size * last->nelts;
    last->nelts++;

    return elt;
}