Nginx 高度なデータ構造ソースコード解析 (3) ----- リンクリスト

ngx_list_t は、Nginx によってカプセル化されたリンク リスト コンテナであり、頻繁に使用されます。これには 2 つの構造があり、ngx_list_t はリンク リスト全体を記述し、ngx_list_part_t はリンク リストの 1 つの要素のみを記述します。理解しやすいように、これを配列のリンクされたリストと呼ぶことができます。つまり、ngx_list_t はリンク リスト コンテナであり、リンク リストの要素は配列です。実際、ngx_list_part_t 配列内の要素は、ユーザーが保存する必要があるものです。

このような構造式の利点は次のとおりです:

(1) リンクされたリストに格納される要素は柔軟であり、どのような種類のデータ構造でも可能です

(2) リンクされています。 list 要素が占有する必要があるメモリは、配列を通じて割り当てられた ngx_list_t によって管理されます

(3) リンクされたリストを使用して小さなメモリにアクセスするのは非効率ですが、配列を使用してオフセットを介してメモリにアクセスするのは効率的です。はるかに効率的です。

ngx_list_t 構造の定義:

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

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

ngx_list_part_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 チュートリアルに興味のある友人の参考になれば幸いです。