### 鏈表結構 ? ? ? 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節點指針指向鏈表最后一個節點 */ 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++; /* 實際存放元素加1 */ /* 返回新元素所在位置 */ 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 》 《[nginx源碼分析—鏈表結構ngx_list_t](http://blog.csdn.net/livelylittlefish/article/details/6599065)》