一、ngx_queue_t雙向鏈表

? 1.ngx_queue_t容器的優勢在于:

? ? ?1) 實現了排序功能;

? ? ?2) 它非常輕量級，是一個純粹的雙向鏈表。它不負責鏈表元素所占內存的分配，與Nginx封裝的ngx_pool_t內存池完全無關。

? ? ?3) 支持兩個鏈表間的合并。

typedef struct ngx_queue_s ngx_queue_t;struct ngx_queue_s {ngx_queue_t *prev;ngx_queue_t *next; };

? 2.ngx_queue_t容器提供的操作方式

? ? ?

? ?3.ngx_queue_t雙向鏈表容器所支持的方法

方法名	參數含義	執行意義
ngx_queue_init(h)	h為鏈表容器結構體ngx_queue_t的指針	將鏈表容器h初始化，這時會自動置為空鏈表
ngx_queue_empty(h)	h為鏈表容器結構體ngx_queue_t的指針	檢測鏈表容器中是否為空，即是否沒有一個元素存在。如果返回非0，表示鏈表h是空的。
ngx_queue_insert_head(h, x)	h為鏈表容器結構體ngx_queue_t的指針，x為插入元素結構體中ngx_queue_t成員的指針	將元素x插入到鏈表容器h的頭部
ngx_queue_insert_tail(h, x)	h為鏈表容器結構體ngx_queue_t的指針，x為插入元素結構體中ngx_queue_t成員的指針	將元素x添加到鏈表容器h的末尾
ngx_queue_head(h)	h為鏈表容器結構體ngx_queue_t的指針	返回鏈表容器h中的第一個元素的ngx_queue_t結構體指針
ngx_queue_last(h)	h為鏈表容器結構體ngx_queue_t的指針	返回鏈表容器中的最后一個元素的ngx_queue_t結構體指針
ngx_queue_sentinel(h)	h為鏈表容器結構體ngx_queue_t的指針	返回鏈表容器結構體的指針
ngx_queue_remove(x)	x為插入元素結構體中ngx_queue_t成員的指針	由容器中移除x元素
ngx_queue_split(h, q,n)	h為鏈表容器結構體ngx_queue_t的指針	ngx_queue_split用于拆分鏈表，h是鏈表容器，而q是鏈表h中的一個元素。這個方法將鏈表h以元素q為界拆分成兩個鏈表h和n，其中h由原鏈表的前半部分構成(不包括q),而n由原鏈表的后半部分構成，q是它的首元素。
ngx_queue_add(h, n)	h為鏈表容器結構體ngx_queue_t的指針,n為另一個鏈表容器結構體ngx_queue_t的指針	合并鏈表，將n鏈表添加到h鏈表的末尾
ngx_queue_middle(h)	h為鏈表容器結構體ngx_queue_t的指針	返回鏈表中心元素，如，鏈表共有N個元素，ng_queue_middle方法將返回第N/2+1個元素，例如，鏈表有4個元素，將會返回第3個元素(不是第2個元素)
ngx_queue_sort(h, cmpfunc)	h為鏈表容器結構體ngx_queue_t的指針,cmpfunc是兩個鏈表元素的比較方法，如果它返回正數，則表示以升序排序	使用插入排序法對鏈表進行排序，cmpfunc需要使用者自己實現，它的原型是這樣的:ngx_int_t (*cmpfunc)(const ngx_queue_t *, const ngx_queue_t *)

? ?4.? ngx_queue_t雙向鏈表中的元素所支持的方法

方法名	參數含義	執行意義
ngx_queue_next(q)	q為鏈表中某一個元素結構體的ngx_queue_t成員的指針	返回q元素的下一個元素
ngx_queue_prev(q)	q為鏈表中某一個元素結構體的ngx_queue_t成員的指針	返回q元素的上一個元素
ngx_queue_data(q, type, link)	q為鏈表中某一個元素結構體的ngx_queue_t成員的指針，type為鏈表元素的結構體類型名稱(該結構體中必須包含ngx_queue_t類型的成員),lin開始上面這個結構體中ngx_queue_t類型的成員名字	返回q元素(ngx_queue_t類型)所屬結構體(任何struct類型，其中可在任意位置包含ngx_queue_t類型的成員）的地址
ngx_queue_insert_after(q, x)	q為鏈表中某個元素結構體的ngx_queue_t成員的指針，x為插入元素結構體中ngx_queue_t成員的指針	將元素x插入到元素q之后

? ?5.空容器時ngx_queue_t結構體成員的值

? ? ??

? ? 6.當僅含1個元素時，容器、元素中的ngx_queue_t結構體成員的值

? ??

? ?7.當含有兩個或多個元素時，容器、元素中的ngx_queue_t結構體中prev、next成員的值

? ??

二、ngx_array_t動態數組

? ? ngx_array_t是一個順序容器，它在Nginx中大量使用。ngx_array_t容器以數組的形式存儲元素，并支持在達到數組容量的上限時動態改變數組的大小。

? ? ?優點:

? ? ? 1)訪問速度快

? ? ? ?2)允許元素個數具備不確定性;

? ? ? ?3)負責元素占用內存的分配，這些內存將由內存池統一管理。

? ? 1.ngx_array_t動態數組的實現僅使用1個結構體，如下:

typedef struct ngx_array_s ngx_array_t; struct ngx_array_s {//elts指向數組的首地址void *elts;//nelts是數組中已經使用的元素個數ngx_uint_t nelts;//每個數組元素占用的內存大小size_t size;//當前數組中能夠容納元素個數的總大小ngx_uint_t nalloc;//內存池對象ngx_pool_t *pool; };

? ? ?2.ngx_array_t動態數組結構體中的成員及其提供的方法

? ? ? ?

? ? ?3.ngx_array_t動態數組提供的方法

? ? ? ??

三、ngx_list_t單向鏈表

? ? ?相當于動態數組與單向鏈表的結合體。

四、ngx_rbtree_t紅黑樹

? ? ngx_rbtree_t是使用紅黑樹實現的一種關聯容器，Nginx的核心模塊(如定時器管理、文件緩存模塊等)在需要快速檢索、查找的場合下都使用了ngx_rbtree_t容器。

? ? 順序容器的檢索效率通常情況下都比較差，一般只能遍歷檢索指定元素。當需要容器的檢索速度很快，或者需要支持范圍查詢時，ngx_rbtree_t紅黑樹容器是一個非常好的選擇。

? ? 什么是自平衡二叉查找樹?在不斷地向二叉查找樹中添加、刪除節點時，二叉查找樹自身通過形態的變換，始終保持著一定程度上的平衡，即為自平衡二叉查找樹。自平衡二叉查找樹有許多種不同的實現方式，如AVL樹和紅黑樹。紅黑樹是一種自平衡性較好的二叉查找樹，它在Linux內核、C++的STL庫等許多場合下都作為核心數據結構使用。

? ? ngx_rbtree_t紅黑樹容器中的元素都是有序的，它支持快速的檢索、插入、刪除操作，也支持范圍查詢、遍歷等操作，是一種應用場景非常廣泛的高級數據結構。

? ? 紅黑樹是指每個節點都帶有顏色屬性的二叉查找樹，其中顏色為紅色或黑色。除了二叉查找樹的一般要求以外，對于紅黑樹還有如下的額外的特性。

? ? ?特性1:節點時紅色或黑色。

? ? ?特性2:根節點是黑色。

? ? ?特性3:所有葉子節點都是黑色(葉子是NIL節點，也叫“哨兵”)。

? ? ?特性4:每個紅色節點的兩個子節點都是黑色(每個葉子節點到根節點的所有路徑上不能有兩個連續的紅色節點)>

? ? ?特性5:從任一節點到其每個葉子節點的所有簡單路徑都包含相同數目的黑色節點。

? 1.ngx_rbtree_t紅黑樹的典型圖示

? ? ??

? ?2.紅黑樹節點的結構體及其提供的方法

? ? ?

? ? 3.ngx_rbtree_node_t結構體的定義

typedef struct ngx_rbtree_s ngx_rbtree_t;/*為解決不同節點含有相同關鍵字的元素沖突問題，紅黑樹設置了ngx_rbtree_insert_pt指針，這樣可靈活地添加沖突元素 */ typedef void (*ngx_rbtree_insert_pt)(ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);struct ngx_rbtree_s {//指向樹的根節點。注意，根節點也是數據元素ngx_rbtree_node_t *root;//指向NIL哨兵節點ngx_rbtree_node_t *sentinel;//表示紅黑樹添加元素的函數指針，它決定在添加新節點時的行為究竟是替換還是新增ngx_rbtree_insert_pt insert; };

? ? ? ngx_rbtree_t結構體的root成員指向根節點，而sentinel成員指向哨兵節點。

? ? ? 4.Nginx為紅黑樹已經實現好的3種數據添加方法

? ? ? ??

? ? ? ??

? ? ? ? ?

? ? 5.ngx_str_rbtree_insert_value的實現

? ? ? ?

五、ngx_radix_tree_t基數樹

? ?詳見資料

六、支持通配符的散列表

? 6.1 ngx_hash_t基本散列表

? ? 詳見資料

? 6.2 支持通配符的散列表

? ? 詳見資料

?

總結

以上是生活随笔為你收集整理的《深入理解Nginx 模块开发与架构解析》之高级数据结构摘录的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。