Ningx代码研究（三）

ngx的基本容器

ngx_array

对应的文件为 core/ngx_array.{c|h}

ngx_array是nginx内部封装的使用 ngx_pool_t对内存池进行分配的数组容器，其中的数据是在一整片内存区中连续存放的。更新数组时只能在尾部压入1个或多个元素。

数组的实现结构为

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

其中 elts 为具体的数据区域的指针， nelts 为数组实际包含的元素数量， size为数组单个元素的大小， nalloc为数组容器预先（或者重新）分配的内存大小， pool 为分配基于的内存池

常用的操作有

// 创建一个新的数组容器
ngx_array_t *ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size);

// 销毁数组容器
void ngx_array_destroy(ngx_array_t *a);

// 将新的元素加入数组容器
void *ngx_array_push(ngx_array_t *a);
void *ngx_array_push_n(ngx_array_t *a, ngx_uint_t n);　//返回ｎ个元素的指针

这里需要注意的是，和之前的ngx_pool_cleanup_add一样， ngx_array_push只是进行内存分配的操作，我们需要对返回的指针指向的地址进行赋值等操作来实现实际数组值的添加。

具体一点的push操作的实现为，

1. 首先判断　nalloc是否和nelts相等，即数组预先分配的空间已经满了，如果没满则计算地址直接返回指针
2. 如果已经满了则先判断是否我们的pool中的当前链表节点还有剩余的空间，如果有则直接在当前的pool链表节点中分配内存，并返回
3. 如果当前链表节点没有足够的空间则使用ngx_palloc重新分配一个2倍于之前数组空间大小的数组，然后将数据转移过来，并返回新地址的指针

下面是一个array的例子:

demo/basic_types/array_and_hash.c

#include <stdio.h>
#include "ngx_config.h"
#include "ngx_conf_file.h"
#include "nginx.h"
#include "ngx_core.h"
#include "ngx_string.h"
#include "ngx_palloc.h"
#include "ngx_array.h"

volatile ngx_cycle_t  *ngx_cycle;

void
ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,
            const char *fmt, ...)
{
}

int main()
{
   ngx_pool_t* pool;
   ngx_array_t* arr;
   int n;
   int* ele;
   pool = ngx_create_pool(4000, NULL);
   arr = ngx_array_create(pool, 10, sizeof(ngx_uint_t));
   for (n=0; n < 5; n++) {
      ele = (int*) ngx_array_push(arr);
      *ele = n;
      printf("new element %d added\n", n);
   }

   printf("arr->nelts is %d, arr->nalloc = %d\n", arr->nelts, arr->nalloc);

   for (n=5; n < 15; n++) {
      ele = (int*) ngx_array_push(arr);
      *ele = n;
      printf("new element %d added\n", n);
   }
   printf("arr->nelts is %d, arr->nalloc = %d\n", arr->nelts, arr->nalloc);

   ngx_array_destroy(arr);
   ngx_destroy_pool(pool);
   return 0;
}

编译运行

gcc  -c -O -pipe  -O -W -Wall -Wpointer-arith -Wno-unused-parameter -Wunused-function -Wunused-variable -Wunused-value -Werror -g -I ../../../objs/ -I ../../os/unix array_and_hash.c -I../../core/ -I../../event/ -I../../os/ -o array_and_hash.o
gcc -o array_and_hash array_and_hash.o ../../../objs/src/core/ngx_{string,palloc,array}.o ../../../objs/src/os/unix/ngx_alloc.o -lcrypt -lpcre -lcrypto -lz
rainx@rainx-laptop:~/land/nginx-0.7.61/src/demo/basic_types$ ./array_and_hash 
new element 0 added
new element 1 added
new element 2 added
new element 3 added
new element 4 added
arr->nelts is 5, arr->nalloc = 10
new element 5 added
new element 6 added
new element 7 added
new element 8 added
new element 9 added
new element 10 added
new element 11 added
new element 12 added
new element 13 added
new element 14 added
arr->nelts is 15, arr->nalloc = 15

ngx_queue

ngx_queue.{c,h} 实现了一个队列的操作逻辑，队列的基本结构为一个双向队列

基础的数据结构为

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

注意nginx的队列操作和结构只进行指针的操作，不负责节点内容空间的分配和保存，所以在定义自己的队列节点的时候，需要自己定义数据结构以及分配空间， 并包含一个ngx_queue_t类型的成员, 需要获得原始的数据节点的时候需要使用ngx_queue_data宏

#define ngx_queue_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))

另外，整个queue结构中包含一个 sentinel（哨兵） 节点， 他指向队列的头和尾

下面是一个queue操作的例子

#include <stdio.h>
#include "ngx_config.h"
#include "ngx_conf_file.h"
#include "nginx.h"
#include "ngx_core.h"
#include "ngx_string.h"
#include "ngx_palloc.h"
#include "ngx_queue.h"

volatile ngx_cycle_t  *ngx_cycle;
void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err, const char *fmt, ...) { }

// 用雅虎的成员列表作为一个简单的例子
typedef struct yahoo_s {
    ngx_queue_t   queue;
} yahoo_t;

typedef struct yahoo_guy_s {
    ngx_uint_t    id;
    u_char*       name;
    ngx_queue_t   queue;
} yahoo_guy_t;

// 排序使用的比较函数, 按照id的大小排序，id大放到到前面
ngx_int_t yahoo_no_cmp(const ngx_queue_t* p, const ngx_queue_t* n)
{
    yahoo_guy_t *pre, *next;
    pre  = (yahoo_guy_t*) ngx_queue_data(p, yahoo_guy_t, queue);
    next = (yahoo_guy_t*) ngx_queue_data(n, yahoo_guy_t, queue);
    return ((pre->id > next->id) ? 1:0);
}

int main()
{
    ngx_pool_t*     pool;
    yahoo_guy_t*    guy;
    ngx_queue_t*    q;
    yahoo_t*        yahoo;
    pool            = ngx_create_pool(1024*10, NULL); //初始化内存池
    int             i;
    // 构建队列
    const ngx_str_t   names[] = {
        ngx_string("rainx"), ngx_string("xiaozhe"), ngx_string("zhoujian")
    } ;
    const int       ids[]   = {4611, 8322, 6111};

    yahoo = ngx_palloc(pool, sizeof(yahoo_t));
    ngx_queue_init(&yahoo->queue); //初始化queue

    for(i = 0; i < 3; i++)
    {
      guy = (yahoo_guy_t*) ngx_palloc(pool, sizeof(yahoo_guy_t));
      guy->id   = ids[i];
      //guy->name = (char*) ngx_palloc(pool, (size_t) (strlen(names[i]) + 1) );
      guy->name = (u_char*) ngx_pstrdup(pool, (ngx_str_t*) &(names[i]) );

      ngx_queue_init(&guy->queue);
      // 从头部进入队列
      ngx_queue_insert_head(&yahoo->queue, &guy->queue);
    }

    // 从尾部遍历输出
    for(q = ngx_queue_last(&yahoo->queue);
        q != ngx_queue_sentinel(&yahoo->queue);
        q = ngx_queue_prev(q) ) {

        guy = ngx_queue_data(q, yahoo_guy_t, queue);
        printf("No. %d guy in yahoo is %s \n", guy->id, guy->name);
    }

    // 排序从头部输出
    ngx_queue_sort(&yahoo->queue, yahoo_no_cmp);
    printf("sorting....\n");
    for(q = ngx_queue_prev(&yahoo->queue);
        q != ngx_queue_sentinel(&yahoo->queue);
        q = ngx_queue_last(q) ) {

        guy = ngx_queue_data(q, yahoo_guy_t, queue);
        printf("No. %d guy in yahoo is %s \n", guy->id, guy->name);
    }

    ngx_destroy_pool(pool);
    return 0;
}

运行结果为

rainx@rainx-laptop:~/land/nginxsrp/src/demo/basic_types$ ./queue_op 
No. 4611 guy in yahoo is rainx 
No. 8322 guy in yahoo is xiaozhe 
No. 6111 guy in yahoo is zhoujian 
sorting....
No. 8322 guy in yahoo is xiaozhe 
No. 6111 guy in yahoo is zhoujian 
No. 4611 guy in yahoo is rainx 

ngx_hash

ngx_hash.{c|h} 实现了nginx里面比较重要的一个hash结构， 这个在模块配置解析里经常被用到。该 hash 结构是只读的，即仅在初始创建时可以给出保存在其中的 key-val 对，其后就只能查询而不能进行增删改操作了。

下面是简单 hash 结构的内存布局：

link: http://www.flickr.com/photos/chaoslawful/3780810336/sizes/o/