Nginx--单向链表分析

1.基本数据结构

1.1结点

struct ngx_list_part_s {
    void             *elts;
    ngx_uint_t        nelts;
    ngx_list_part_t  *next;
};

结构成员分析

void* elts                         :数组元素指针

ngx_uint_t                       :数组里面的元素数量

ngx_list_part_t*             :下一个结点的指针

它类似ngx_array_t，是一个简单的数组，也可以“泛型”存储数据，但少了一些成员，还有一个next指针指向链表里的下一个节点。

1.2链表

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;

结构成员分析

last:   链表的尾结点

part：链表的头结点

size:   链表储存元素的大小

nalloc：每一个结点能够储存元素大小 

pool : 使用的内存池

对比 ngx_array_t可以看到，ngx_list_t 的成员size、nalloc和pool的含义是相同的，确定了节点里数组的元信息。可以这么说，链表里的每个节点就是一个简化的ngx_array_t数组结构。

ngx_list_t 的 part成员是链表的头节点（注意不是指针)，part.next 指向链表里的第二个节点，而last则指向链表的尾节点。

1.3图形解释

2.操作函数

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

1. ngx_ok 是一个宏定义

2.初始化确保list已经存在

3.然后去初始化 第二个结点并且首尾相等

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

1. 分配内存

2.init函数

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;
        l->last->next = last;
        l->last = last;
    }
 
    elt = (char *) last->elts + l->size * last->nelts;
    last->nelts++;
 
    return elt;
}
 

1.记住这是一个“添加元素” 后面有测试解释怎么填加

2.是往尾结点上添加！！！

3.     l->last->next = last;
        l->last = last; 

改变尾结点

4.  elt = (char *) last->elts + l->size * last->nelts;
    last->nelts++;

类似与array数组！！！

 

note 没有销毁操作！！！

测试

理解并掌握开源软件的最好方式莫过于自己写一些测试代码，或者改写软件本身，并进行调试来进一步理解开源软件的原理和设计方法。本节给出一个创建内存池并从中分配一个链表的简单例子。在该例中，链表的每个节点(part)可存放5个元素，每个元素4字节大小，创建链表后，要向链表添加15个整型元素。

/**
 * ngx_list_t test, to test ngx_list_create, ngx_list_push
 */
 
#include 
#include "ngx_config.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_pool(ngx_pool_t* pool)
{
    while (pool)
    {
        printf("pool = 0x%x\n", pool);
        printf("  .d\n");
        printf("    .last = 0x%x\n", pool->d.last);
        printf("    .end = 0x%x\n", pool->d.end);
        printf("    .next = 0x%x\n", pool->d.next);
        printf("    .failed = %d\n", pool->d.failed);
        printf("  .max = %d\n", pool->max);
        printf("  .current = 0x%x\n", pool->current);
        printf("  .chain = 0x%x\n", pool->chain);
        printf("  .large = 0x%x\n", pool->large);
        printf("  .cleanup = 0x%x\n", pool->cleanup);
        printf("  .log = 0x%x\n", pool->log);
        printf("available pool memory = %d\n\n", pool->d.end - pool->d.last);
        pool = pool->d.next;
    }
}
 
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("0x%x, ", ptr[loop]);
    }
    printf("0x%x)\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 == NULL)
        return;
 
    printf("list = 0x%x\n", list);
    printf("  .last = 0x%x\n", list->last);
    printf("  .part = 0x%x\n", &(list->part));
    printf("  .size = %d\n", list->size);
    printf("  .nalloc = %d\n", list->nalloc);
    printf("  .pool = 0x%x\n\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);
    dump_pool(pool);
 
    printf("--------------------------------\n");
    printf("alloc an list from the pool:\n");
    printf("--------------------------------\n");
    ngx_list_t *list = ngx_list_create(pool, 5, sizeof(int));
    dump_pool(pool);
 
    for (i = 0; i < 15; i++)
    {
        int *ptr = ngx_list_push(list);
        *ptr = i + 1;
    }
 
    printf("--------------------------------\n");
    printf("the list information:\n");
    printf("--------------------------------\n");
    dump_list(list);
 
    printf("--------------------------------\n");
    printf("the pool at the end:\n");
    printf("--------------------------------\n");
    dump_pool(pool);
 
    ngx_destroy_pool(pool);
    return 0;
}

解析

1.

for (i = 0; i < 15; i++)
    {
        int *ptr = ngx_list_push(list);
        *ptr = i + 1;
    }

这是通过给指针赋值来实现添加元素

2.dump：(计算机内信息)转出，倾卸；转储；内容全部打印

所以dump_loop是打印所有的pool等！！！

结果

# ./ngx_list_t_test
-------------------------------- create a new pool:
-------------------------------- pool = 0x9208020 .d .last = 0x9208048
    .end = 0x9208420
    .next = 0x0
    .failed = 0 .max = 984
  .current = 0x9208020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0 available pool memory = 984
-------------------------------- alloc an list from the pool:
-------------------------------- pool = 0x9208020 .d .last = 0x9208078
    .end = 0x9208420
    .next = 0x0
    .failed = 0 .max = 984
  .current = 0x9208020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0 available pool memory = 936
-------------------------------- the list information:
-------------------------------- list = 0x9208048 .last = 0x9208098
  .part = 0x920804c
  .size = 4
  .nalloc = 5
  .pool = 0x9208020
elements: .part = 0x920804c .elts = 0x9208064  (0x1, 0x2, 0x3, 0x4, 0x5)
    .nelts = 5
    .next = 0x9208078 -->
  .part = 0x920804c .elts = 0x9208084  (0x6, 0x7, 0x8, 0x9, 0xa)
    .nelts = 5
    .next = 0x9208098 -->
  .part = 0x920804c .elts = 0x92080a4  (0xb, 0xc, 0xd, 0xe, 0xf)
    .nelts = 5
    .next = 0x0 
-------------------------------- the pool at the end:
-------------------------------- pool = 0x9208020 .d .last = 0x92080b8
    .end = 0x9208420
    .next = 0x0
    .failed = 0 .max = 984
  .current = 0x9208020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0 available pool memory = 872