Nginx源码初探之数据结构 - 链表数据结构
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Nginx源码初探之数据结构 - 链表数据结构,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2500字,纯文字阅读大概需要4分钟。
内容图文
![Nginx源码初探之数据结构 - 链表数据结构](/upload/InfoBanner/zyjiaocheng/944/ad90b05609d44537af377434cd35e096.jpg)
ngx_list_t 介绍
ngx_list_t是Nginx中使用的较为频繁的数据结构,数据内容基于指针获取,内存分配基于内存池进行。由于数据内容存放的是指针,所以理论上ngx_list_t可以用来构建多维链表甚至是网络结构,只是Nginx原始代码封装的函数中并不涉及这些数据结构的操作(实际上也不需要)。
1.数据结构
Nginx链表的数据结构包含两个部分ngx_list_part_s和ngx_list_t。ngx_list_part_s为数据节点,每个数据节点都包含数据指针和链表数据已存入数据个数和下一节点的位置。
struct ngx_list_part_s {
void *elts;
ngx_uint_t nelts;/*已存储元素个数*/
ngx_list_part_t *next;
};
ngx_list_t负责链表的管理和操作,表头结构如下。
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;
2.基本操作
2.1初始化链表
初始化逻辑很简单,先在内存池中分配第一个节点,然后将最后一个节点指向第一个节点,最后更新链表的管理信息就可以了。
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;
}
2.2创建链表
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;
}
2.3添加元素
添加元素时返回最后一个元素之争,然后在外部逻辑中添加元素内容。
void *
ngx_list_push(ngx_list_t *l)
{
void *elt;
ngx_list_part_t *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++;
return elt;
}
Nginx链表结构可以根据需要动态分配内存,从而有效的避免的内存的过度分配,这点对于节约内存很有好处,需要注意的一点是在大量数据的push操作时会带来内存申请频率增大的问题。
北海宇微 发布了8 篇原创文章 · 获赞 0 · 访问量 85 私信 关注内容总结
以上是互联网集市为您收集整理的Nginx源码初探之数据结构 - 链表数据结构全部内容,希望文章能够帮你解决Nginx源码初探之数据结构 - 链表数据结构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。