08Nginx源碼分析之單向連結清單結構(ngx_list.c)

一 單向連結清單結構

Nginx的list單向連結清單的結構和Nginx的數組結構Array有點類似，總體來說，資料結構也是非常簡單清晰的。

1 ngx_list_t 連結清單結構

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 ngx_list_part_t 節點結構

其中真正的連結清單節點ngx_list_part_t結構如下。

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;  	/* 指向下一個連結清單節點 */
};
           

二 資料結構圖

這幅圖可以粗略看一下即可，具體要了解上面成員的含義還需要看下面的幾個函數，不過也是非常簡單。

三 函數實作

1 ngx_list_init函數

ngx_list_init函數的作用就是為首個節點開辟n*size大小的記憶體，然後初始化管理連結清單的結構的大小，容量等成員。總的來說，還是針對ngx_list_t連結清單結構進行初始化。

static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
	//1 為管理連結清單結構的首節點part初始化指派
    list->part.elts = ngx_palloc(pool, n * size);
    if (list->part.elts == NULL) {
        return NGX_ERROR;
    }
    list->part.nelts = 0;
    list->part.next = NULL;

	//2 初始化管理連結清單的結構
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;

    return NGX_OK;
}
           

2 ngx_list_create函數

從上面的ngx_list_init函數看完後，ngx_list_create函數首先調用palloc開辟連結清單結構的記憶體，然後調用ngx_list_init函數進行初始化，此時連結清單結構的首節點part(對象非指針)開辟了n*size的記憶體。

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

3 ngx_list_push函數

使用ngx_list_push方法可以使用一個元素，并且傳回元素的指針位址(是以這個函數名感覺怪怪的)。如果節點中用于存儲元素的記憶體已經用完，則會建立一個新的連結清單用于傳回。

void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;
 
    last = l->last;
 
    /* 1 如果最後一個連結清單節點用于存儲元素的記憶體已經用完，則需要建立一個新的連結清單*/
    if (last->nelts == l->nalloc) {
 
        /* the last part is full, allocate a new list part */
 
    	/* 配置設定一塊記憶體，存儲ngx_list_part_t資料結構 */
        last = ngx_palloc(l->pool, sizeof(ngx_list_part_t));
        if (last == NULL) {
            return NULL;
        }
 		
 		// 對節點進行初始化，與ngx_list_init函數類似
        /* 配置設定一個連結清單節點的記憶體塊，大小為n*size。*/
        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;//更新連結清單結構的尾部節點
    }
 
 
    /* 2 傳回元素首位址(下面兩句建議畫圖了解非常簡單) */
    elt = (char *) last->elts + l->size * last->nelts;//擷取記憶體中未使用的記憶體。l->size為元素大小，last->nelts為已使用的個數。有人會問為啥是l->size，而不是last，因為nginx為了設計友善，直接将元素的size放在管理連結清單，這樣就不用在每個節點都存放一個size，大量節省記憶體。
    last->nelts++;//更新該節點已使用記憶體的個數。
 
    return elt;
}
           

通過上面3個函數的分析，nginx的單向連結清單的每個節點都可以存放n個size大小的元素，當一個節點的記憶體被使用完時，調用push擷取記憶體會自動開辟新的節點，以使節點裡面有新的記憶體可以傳回。