Hi Jason
  • About
  • Keywords
    • keywords - 2021/01
    • Keywords - 2020/08
    • Keywords - 2020/07
  • Note
    • 2021
    • 2020
      • 伊拉克域名.IQ被美国删除的背后以及早期的根域名管理
      • 美国如果把根域名服务器封了,中国会从网络上消失?
      • The Technical Data Guidance
    • 缓慢收藏, 小心整理
      • 泰戈尔诗句节选
    • 金刚经 原文 | 抄经
  • Read
    • 符号
    • 段永平投资问答录
      • 符号的设计
      • 符号形式探寻
      • 作为符号的设计(上篇)
      • 作为符号的设计(下篇)
      • 符号化设计之符号形式探寻
    • Dark Mode
      • Dark Mode的设计要点
      • 一篇吃透 Dark Mode ,搞定“暗黑/深色”适配
    • Apple
      • Apple “无缝”设计之历程
      • Apple 那些“无关紧要”的设计改进
      • HomePod 的设计
      • 解决方案、设计、好设计,Apple UI 设计中的 Tuning
      • Apple 的 Logo 设计
      • J 的艺术,R 的艺术
      • 从圆角到圆角
      • Apple 颜色设计的历程
      • 欲望、逻辑和习惯
      • 反“建筑学”的 Apple Park 将刺激建筑的发展
      • 螺钉,还是胶水?
      • 关于苹果设计的书籍和文章推荐
      • 正面冲撞习惯
      • 从 iOS 7 的电话图标到 polyoxybenzyl…
      • Affordance(可供性)和设计
      • 美的感知力
      • 2010: A Design Odyssey
      • iPad,从 niche 到 mass
  • Source
    • Nginx
      • 前言
      • Nginx入门
      • Nginx 配置文件
      • Nginx 内存池管理
      • Nginx 基本数据结构
      • Nginx 数组结构 ngx_array_t
      • Nginx 链表结构 ngx_list_t
      • Nginx 队列双向链表结构 ngx_queue_t
      • Nginx 哈希表结构 ngx_hash_t
      • Nginx 红黑树结构 ngx_rbtree_t
      • Nginx 模块开发
      • Nginx 启动初始化过程
      • Nginx 配置解析
      • Nginx 中的 upstream 与 subrequest 机制
      • Nginx 源码结构分析
      • Nginx 事件模块
      • Nginx 的 epoll 事件驱动模块
      • Nginx 定时器事件
      • Nginx 事件驱动模块连接处理
      • Nginx 中 HTTP 模块初始化
      • Nginx 中处理 HTTP 请求
      • Untitled
      • Untitled
    • Part 1
      • curl
  • Google Dev
    • 重要概念
      • Google 搜索的工作方式
      • 什么是展示次数、排名和点击次数?
      • 关于我们的统计信息和数据
    • Search Console帮助
      • 指南概览
      • 网站站长指南
      • 常规指南
        • 搜索引擎优化 (SEO) 新手指南
        • 使用 HTTPS 确保网站安全
        • 保持简单的网址结构
        • 向 Google 说明您的出站链接的用意
        • 将网站标记为面向儿童的内容
        • 浏览器兼容性
        • 避免创建重复内容
        • 确保链接可供抓取
        • 借助 Google 搜索进行网站测试的最佳做法
      • 专门面向内容的指南
        • 与 Google 搜索中的 AMP 网页相关的准则
        • AJAX 增强网站
        • 图片和视频
          • Google 图片最佳做法
          • 图片站点地图
          • Google 图片中的图片权限元数据
          • 视频最佳做法
          • 视频 Sitemap 及其替代方案
          • 有关富媒体文件的最佳做法
        • 播客
        • Google 移动
          • 在功能手机上进行移动浏览
          • Web Light:在搜索结果中提供更快速且更精简的移动版网页
          • Google 搜索中的 Web Light 网页对广告网络的支持
          • Google 探索和您的网站
          • 实用资源:面向适合在移动设备上显示的网页的开发者
          • 将移动网络结算费用明确告知用户
          • 将 Android 应用与网站相关联
      • 质量指南
    • Google Cloud CDN
      • 使用拖管实例组设置 Cloud CDN
      • 使用后端存储分区设置 Cloud CDN
      • 使用缓存键
      • 查看日志
  • Guidebook
    • Color Guide
    • Material.io
  • Navigation
    • Google
    • Social & Study
    • Working Tools
Powered by GitBook
On this page
  • 链表结构
  • 链表操作
  • 创建链表
  • 添加元素

Was this helpful?

  1. Source
  2. Nginx

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 = l->last;

    
    if (last->nelts == l->nalloc) {

        

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

测试程序:

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

输出结果:

$ ./list_test 
--------------------------------
create a new pool:
--------------------------------
--------------------------------
alloc an list from the pool:
--------------------------------
list = 0x98ce048
  .last = 0x98ce04c
  .part = 160227404
  .size = 4
  .nalloc = 5
  .pool = 0x98ce020
elements: 
  .part = 0x98ce04c
    .elts = 0x98ce064  (0, 2, 4, 6, 8)
    .nelts = 5
    .next = 0x0 

参考资料:

《深入理解 Nginx 》

PreviousNginx 数组结构 ngx_array_tNextNginx 队列双向链表结构 ngx_queue_t

Last updated 4 years ago

Was this helpful?

《》

nginx源码分析—链表结构ngx_list_t