Nginx 고급 데이터 구조 소스 코드 분석 (3) ----- 연결 목록

ngx_list_t는 Nginx로 캡슐화된 연결 목록 컨테이너로 자주 사용됩니다. 여기에는 두 가지 구조가 있습니다. ngx_list_t는 전체 연결 목록을 설명하고 ngx_list_part_t는 연결 목록의 한 요소만 설명합니다. 이해하기 쉽도록 배열의 연결 리스트라고 부를 수 있습니다. 즉, ngx_list_t는 연결리스트 컨테이너이고 연결리스트의 요소는 배열입니다. 실제로 ngx_list_part_t 배열의 요소는 사용자가 저장해야 하는 요소입니다.

이러한 구조적 표현의 이점은 무엇입니까?

(1) 연결된 목록에 저장된 요소 유연하므로 모든 종류의 데이터 구조가 가능합니다.

(2) 연결 목록 요소가 차지하는 메모리는 배열을 통해 할당된 ngx_list_t에 의해 관리됩니다. >

(3) 연결된 목록을 사용하여 작은 메모리 블록에 액세스하는 것은 비효율적이지만 배열을 사용하여 오프셋을 통해 메모리에 액세스하는 것이 훨씬 효율적입니다.

ngx_list_t 구조 정의:

typedef struct {
    ngx_list_part_t  *last;     //指向链表的最后一个数组元素

ngx_list_part_t 구조 정의:

    ngx_list_part_t   part;     //链表的首个数组元素
    size_t            size;     //每一个用户要存储的一个数据必须小于或等于size
    ngx_uint_t        nalloc;   //表示数组元素的个数还是每个数组元素中的元素个数？？？问徐
    ngx_pool_t       *pool;     //内存池对象
} ngx_list_t;

배열 연결 리스트 초기화:

struct ngx_list_part_s {
    void             *elts;     //指向数组的起始地址
    ngx_uint_t        nelts;    //表示数组中已经用了多少个元素
    ngx_list_part_t  *next;     //下一个链表元素的地址
};

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;    //开始数组元素中只有0个元素
    list->part.next = NULL;
    list->last = &list->part;//指向第一个节点
    list->size = size;
    list->nalloc = n;
    list->pool = pool;//内存池对象

    return NGX_OK;
}

배열 연결 리스트 생성:

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));//申请ngx_list_t的内存
    if (list == NULL) {
        return NULL;
    }

    if (ngx_list_init(list, pool, n, size) != NGX_OK) {//调用初始化函数对ngx_list_t初始化
        return NULL;
    }

    return list;
}

새 요소 추가:

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 고급 데이터 구조 소스 코드 분석(3) - 링크드 리스트 내용을 포함하여 PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.