解码Nginx:列表(List)

梁涛(@无锋之刃)
2012-11-25

nginx-1.2.5

源码文件

src/core/ngx_list.h
src/core/ngx_list.c

设计思路

Nginx实现的列表接近于数组,但有三点区别:

  1. 可以在指定内存块上创建列表数据结构;
  2. 储备元素区中无空闲元素时,分配新的储备元素区,挂到单向链表中,而不是替换掉旧的,在扩充容量的同时减少内存处理次数;
  3. 不提供ngx_list_destroy(),完全依靠底层内存池管理内存。

列表适用于元素较大、或元素生命周期较长,扩充储备元素区会跨越内存池中多个ngx_pool_data_t结构体的场景。

数据结构

        ngx_list_create(pool, n, size)           ngx_list_push()                 ...
         |                                        |
         +- ngx_palloc()---------\                +- ngx_palloc()--\
         |                       |                |                |
         \- ngx_palloc()----------------\         \- ngx_palloc()---------\
                                 |      |                          |      |
          ngx_list_t             V      |                          |      |
         +-----------------------+      |                          |      |
         | last                  | --\  |                          |      |
         +-----------------------+   |  |                          |      |
         | ngx_list_part_t part  |   |  |        ngx_list_part_t   V      |
         |  +--------------------+   +--------> +------------------+      |  /-> ...
  /------+- | elts               |   |  |   /-- | elts             |      |  |
  |      |  +--------------------+   |  |   |   +------------------+      |  |
  |      |  | netls              |   |  |   |   | netls            | --\  |  |
  |      |  +--------------------+   |  |   |   +------------------+   |  |  |
  |      |  | next               | --/  |   |   | next             | --------/
  |      +-----------------------+      |   |   +------------------+   |  |
  |  /-- | size            bytes |      |   |                          |  |
  |  |   +-----------------------+      |   |                          |  |
  |  |   | nalloc            = n | --\  |   |                          |  |
  |  |   +-----------------------+   |  |   |                          |  |
  |  |   | pool                  |   |  |   |                          |  |
  |  |   +-----------------------+   |  |   |                          |  |
  |  |                               |  |   |                          |  |
  |  |                               |  |   |                          |  |
  |  |                           /------/   |                      /------/
  |  |                           |   |      |                      |   | 
  |  |                           V   |      |                      V   | 
  \----> +-----------------------+  -+-     \-> +------------------+  -+-
     |   | elem 0                |   A          | elem 5           |   A 
     |   /                       /   |          /                  /   | 
     |   /                       /   |          /                  /   | 
     |   |                       |   |          |                  |   | 
     |   +-----------------------+   |          +------------------+   | 
     |   | elem 1                |   |          | elem 6           |   | 
     |   /                       /   |          /                  /   | 
     |   /                       /   |          /                  /   | 
     |   |                       |   |          |                  |   | 
    -+-  +-----------------------+   |          +------------------+   | 
     A   | elem 2                |   |          | elem 7           |   | 
     |   /                       /   |          /                  /   | 
     |   /                       /   |          /                  /   | 
     V   |                       |   |          |                  |   V 
    ---  +-----------------------+   |          +------------------+  ---
         | elem 3                |   |          | unpushed         |
         /                       /   |          / elements         /
         /                       /   |          /                  /
         |                       |   |          /                  /
         +-----------------------+   |          /                  /
         / elem 4                /   |          /                  /
         /                       /   |          /                  /
         |                       |   V          |                  |
         +-----------------------+  ---         +------------------+

接口函数

ngx_list_create(pool, n, size)

ngx_list_create()负责动态创建一个列表,动作序列如下:

  1. 从pool中分配ngx_list_t结构体;
  2. 从pool中分配能容纳n个size大小的元素的储备元素区块;
  3. 适当地初始化ngx_list_t结构体。

ngx_list_init(pool, n, size)

ngx_list_create()负责在给定的内存块上创建一个列表,动作序列如下:

  1. 从pool中分配能容纳n个size大小的元素的储备元素区块;
  2. 适当地初始化ngx_list_t结构体。

ngx_list_push(list)

ngx_list_push()负责向数组中“压入”一个元素(实际为取得一个空元素的首址),动作序列如下:

  1. 若列表中还有空元素,直接取得其首址并返回;
  2. 分配新的ngx_list_part_t结构体和储备元素区块,将结构体追加到列表单向链表尾部后分配新的空元素并返回。