首页 > 代码库 > Nginx 链表结构 ngx_list_t
Nginx 链表结构 ngx_list_t
链表结构
ngx_list_t 是 Nginx 封装的链表容器,链表容器内存分配是基于内存池进行的,操作方便,效率高。Nginx 链表容器和普通链表类似,均有链表表头和链表节点,通过节点指针组成链表。其结构定义如下:
/* 链表结构 */ 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 链表的操作只有两个:创建链表 和 添加元素。
创建链表
创建新的链表时,首先分配链表表头,再对该链表进行初始化,在初始化过程中分配头节点数据区内存。
/* 创建链表 */ 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; } /* 初始化链表 */ if (ngx_list_init(list, pool, n, size) != NGX_OK) { return NULL; } return list; } /* 初始化链表 */ static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size) { /* 分配节点数据区内存,并返回该节点数据区的首地址 */ list->part.elts = ngx_palloc(pool, n * size); if (list->part.elts == NULL) { return NGX_ERROR; } /* 初始化节点成员 */ list->part.nelts = 0; list->part.next = NULL; list->last = &list->part; list->size = size; list->nalloc = n; list->pool = pool; return NGX_OK; }
添加元素
添加元素到链表时,都是从最后一个节点开始,首先判断最后一个节点的数据区是否由内存存放新增加的元素,若足以存储该新元素,则返回存储新元素内存的位置,若没有足够的内存存储新增加的元素,则分配一个新的节点,再把该新的节点连接到现有链表中,并返回存储新元素内存的位置。注意:添加的元素可以是整数,也可以是一个结构。
/* 添加一个元素 */ 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; last->nelts++; /* 实际存放元素加1 */ /* 返回新元素所在位置 */ return elt; }
参考资料:
《深入理解 Nginx 》
Nginx 链表结构 ngx_list_t
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。