nginx--可扩展数组和数组排序

旧城等待， 2022-01-26 07:45 193阅读 0赞

一、引言

之前了解到C++中的vector的时候没有怎么在意。现在阅读nginx源码时，发现了nginx中很多利用C语言对一些数据结构的实现，很不错。本文主要总结一下，nginx中可扩展数组的实现以及一个相关的sort接口。

二、数据结构

C中数据结构是所有高级操作的基础，这里也不例外。

![复制代码][copycode.gif]

typedef struct {
        void        *elts;                      // 所有成员占用的总空间(n * sizeof(type))，会通过内存池分配
        ngx_uint_t   nelts;                     // 已经存在的成员的个数
        size_t       size;                      // 成员的sizeof
        ngx_uint_t   nalloc;                    // 数组容量的大小
        ngx_pool_t  *pool;                      // 数组相关的内存池的指针
    } ngx_array_t;

![复制代码][copycode.gif]

其实从数据结构基本就可以了解如何实现。

三、相关接口

ngx\_array\_create：创建一个array，这里包括两步：

1、创建一个ngx\_array\_t结构对象；

2、根据初始设置的array容量、数据类型赋值nalloc和size，然后创建一个初始数组空间；

ngx\_array\_push\_n和ngx\_array\_push：向array中插入元素。如果空间可用就直接插入数据即可；如果空间不够那么就创建新的空间更大的array，然后将旧的数据memcpy到新的空间中。

四、其他

该设计中涉及到nginx中比较巧妙的内存池设计，后面再说明。当然我们在实现时，不一定要采用内存池模式。ps：内存池的好处，都了解。

五、数组排序

采用动态分配哨兵的插入排序法。

![复制代码][copycode.gif]

/*******************************************************************************
    * 函数名称: ngx_sort
    * 输入参数: base--数组的首地址；n--成员个数；size---元素空间的大小
    * 输出参数: 
    * 返 回 值: 
    * 时    间: 2015-06-03
    * 说    明: 排序操作接口，具体的比较条件和结果入参函数接口cmp决定
    * 其    它: 为动态数组中的元素执行排序，排序法为: 插入排序法
    *******************************************************************************/
    void
    ngx_sort(void *base, size_t n, size_t size,
        ngx_int_t (*cmp)(const void *, const void *))
    {
        u_char  *p1, *p2, *p;
    
        p = ngx_alloc(size, ngx_cycle->log);        // 动态分配内存，作为哨兵节点
        if (p == NULL) {
            return;
        }
    
        /* 插入排序法: 将一条记录插入到一个有序的序列中 */
        for (p1 = (u_char *) base + size;           // 假设第一个元素就是有序表，所以从第二个开始
             p1 < (u_char *) base + n * size;       // 直到最后一个
             p1 += size)
        {
            ngx_memcpy(p, p1, size);        // 哨兵作为临时存储
    
            for (p2 = p1;
                 p2 > (u_char *) base && cmp(p2 - size, p) > 0;     // 哨兵作为判断边界
                 p2 -= size)
            {                       // 将
                ngx_memcpy(p2, p2 - size, size);
            }
    
            ngx_memcpy(p2, p, size);
        }
    
        ngx_free(p);
    }

![复制代码][copycode.gif]

[copycode.gif]: /images/20220126/dada743f5ebf420a883b454a557c23c8.png