闲不下来-nginx 链表结构（七） 闲不下来-nginx

发表于

闲不下来-nginx 链表结构

ngx_list_t 是 Nginx 封装的链表容器，链表容器内存分配是基于内存池进行的，操作方便，效率高。Nginx 链表容器和普通链表类似，均有链表表头和链表节点，通过节点指针组成链表。其在文件core/ngx_list.h中结构定义如下：

链表结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码typedef struct ngx_list_part_s  ngx_list_part_t;

struct ngx_list_part_s {
    void             *elts; // 指向该节点数据区的首地址
    ngx_uint_t        nelts; // 该节点数据区实际存放的元素个数
    ngx_list_part_t  *next; // 指向链表的下一个节点
};


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;

nginx-链表结构-ZYedu2

所以，了解 nginx 再次封装的基本结构，可以画个示意图，这样会方便理解。

链表方法

Nginx 链表的操作只有两个：创建链表 和 添加元素。由于链表的内存分配是基于内存池，所有内存的销毁由内存池进行，即链表没有销毁操作。

创建链表

关于源文件可去core/ngx_list.c中，本文源文件的版本是 0.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
c复制代码ngx_list_t *
ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    ngx_list_t  *list;

    // 分配链表表头的内存
    list = ngx_palloc(pool, sizeof(ngx_list_t));
    if (list == NULL) {
        return NULL;
    }

    // 分配节点数据区内存，并返回该节点数据区的首地址
    list->part.elts = ngx_palloc(pool, n * size);
    if (list->part.elts == NULL) {
        return NULL;
    }

    // 初始化节点属性
    list->part.nelts = 0;
    list->part.next = NULL;
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;

    return list;
}

添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
c复制代码void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;

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

    // 计算存储新元素的位置
    elt = (char *) last->elts + l->size * last->nelts;

    // 实际存放元素加1
    last->nelts++;

    // 返回新元素所在位置
    return elt;
}

添加元素到链表时，都是从最后一个节点开始，其过程：

  1. 首先判断最后一个节点的数据区是否由内存存放新增加的元素；
  2. 若足以存储该新元素，则返回存储新元素内存的位置；
  3. 若没有足够的内存存储新增加的元素，则分配一个新的节点，再把该新的节点连接到现有链表中，并返回存储新元素内存的位置。

此处链表与数组的区别：

  1. 数组数据区满时要扩充数据区空间；而链表每次要分配节点及其数据区。
  2. 添加的元素可以是整数，也可以是一个结构。

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
c复制代码#include "ngx_config.h"
#include <stdio.h>
#include "ngx_conf_file.h"
#include "nginx.h"
#include "ngx_core.h"
#include "ngx_string.h"
#include "ngx_palloc.h"
#include "ngx_list.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, ...)
{
}
void dump_list_part(ngx_list_t* list, ngx_list_part_t* part)
{
    int *ptr = (int*)(part->elts);
    int loop = 0;

    printf("  .part = 0x%x\n", &(list->part));
    printf("    .elts = 0x%x  ", part->elts);
    printf("(");
    for (; loop < list->nalloc - 1; loop++)
    {
        printf("%d, ", ptr[loop]);
    }
    printf("%d)\n", ptr[loop]);
    printf("    .nelts = %d\n", part->nelts);
    printf("    .next = 0x%x", part->next);
    if (part->next)
        printf(" -->\n");
    printf(" \n");
}
void dump_list(ngx_list_t* list)
{
    if (list)
    {
        printf("list = 0x%x\n", list);
        printf("  .last = 0x%x\n", list->last);
        printf("  .part = %d\n", &(list->part));
        printf("  .size = %d\n", list->size);
        printf("  .nalloc = %d\n", list->nalloc);
        printf("  .pool = 0x%x\n", list->pool);

        printf("elements: \n");
        ngx_list_part_t *part = &(list->part);
        while(part)
        {
            dump_list_part(list, part);
            part = part->next;
        }
        printf("\n");
    }
}

int main()
{
    ngx_pool_t *pool;
    int i;

    printf("--------------------------------\n");
    printf("create a new pool:\n");
    printf("--------------------------------\n");
    pool = ngx_create_pool(1024, NULL);

    printf("--------------------------------\n");
    printf("alloc an list from the pool:\n");
    printf("--------------------------------\n");
    ngx_list_t *list = ngx_list_create(pool, 5, sizeof(int));

    if(NULL == list)
    {
        return -1;
    }
    for (i = 0; i < 5; i++)
    {
        int *ptr = ngx_list_push(list);
        *ptr = 2*i;
    }

    dump_list(list);

    ngx_destroy_pool(pool);
    return 0;
}

编写本例子的 Makefile：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bash复制代码CXX = gcc
CXXFLAGS +=-g -Wall -Wextra

NGX_ROOT =/Users/mf/Documents/mysource/nginx-0.5

TARGETS =ngx_list_t_test
TARGETS_C_FILE= $(TARGETS).c

CLEANUP = rm-f $(TARGETS) *.o

all:$(TARGETS)

clean:
	$(CLEANUP)

CORE_INCS =-I. \
-I$(NGX_ROOT)/src/core \
-I$(NGX_ROOT)/src/event \
-I$(NGX_ROOT)/src/event/modules \
-I$(NGX_ROOT)/src/os/unix \
-I$(NGX_ROOT)/objs \

NGX_PALLOC =$(NGX_ROOT)/objs/src/core/ngx_palloc.o
NGX_STRING =$(NGX_ROOT)/objs/src/core/ngx_string.o
NGX_ALLOC =$(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o
NGX_LIST =$(NGX_ROOT)/objs/src/core/ngx_list.o

$(TARGETS):$(TARGETS_C_FILE)
	$(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING) $(NGX_ALLOC) $(NGX_LIST) $^ -o $@

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bash复制代码↳ ./ngx_list_t_test                                                                                                                                 00:24:13 
--------------------------------
create a new pool:
--------------------------------
--------------------------------
alloc an list from the pool:
--------------------------------
list = 0xa2009840
  .last = 0xa2009848
  .part = -1577019320
  .size = 4
  .nalloc = 5
  .pool = 0xa2009800
elements:
  .part = 0xa2009848
    .elts = 0xa2009878  (0, 2, 4, 6, 8)
    .nelts = 5
    .next = 0x0

参考

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%