nginx_圖解nginx關鍵資料結構_雙向連結清單ngx_queue_t
一、結構解析
ngx_queue_t是一種環形雙向連結清單的資料結構，這個連結清單不會負責配置設定記憶體來存放元素，ngx_queue_t隻是将已經配置設定好記憶體的元素用雙向連結清單連接配接起來。
連結清單的優勢在于，可以高效的執行插入、删除、合并等操作。移動連結清單元素的時候隻需要修改連結清單的指向，是以适合頻繁修改容器的情況。
nginx中，ngx_queue_t主要功能有
（1）實作了簡單的插入排序
（2）支援兩個連結清單的合并與拆分
（3）擷取連結清單的中心元素，假設連結清單有n個元素，傳回第n / 2 + 1個元素。
typedef struct ngx_queue_s ngx_queue_t;
//ngx_queue_t 結構體
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};
含有兩個元素的 ngx_queue_t 結構
二、主要函數實作
/*
* Copyright (C) Igor Sysoev
* Copyright (C) Nginx, Inc.
*/
//ngx_queue.h
#include <ngx_config.h>
#include <ngx_core.h>
#ifndef _NGX_QUEUE_H_INCLUDED_
#define _NGX_QUEUE_H_INCLUDED_
typedef struct ngx_queue_s ngx_queue_t;
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};
/*
func：初始化連結清單容器
arg: q為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_init(q) \
(q)->prev = q; \
(q)->next = q
/*
func：檢測連結清單容器是否為空
arg: h為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_empty(h) \
(h == (h)->prev)
/*
func：将元素x插到連結清單容器的頭部
arg: h為連結清單容器結構體ngx_queue_t的指針，x為插入元素結構體中元素的指針
*/
#define ngx_queue_insert_head(h, x) \
(x)->next = (h)->next; \
(x)->next->prev = x; \
(x)->prev = h; \
(h)->next = x
#define ngx_queue_insert_after ngx_queue_insert_head
/*
func：将元素x插到連結清單容器的尾部
arg: h為連結清單容器結構體ngx_queue_t的指針，x為插入元素結構體中ngx_queue_t元素的指針
*/
#define ngx_queue_insert_tail(h, x) \
(x)->prev = (h)->prev; \
(x)->prev->next = x; \
(x)->next = h; \
(h)->prev = x
/*
func：傳回容器中第一個元素的指針
arg: h為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_head(h) \
(h)->next
/*
func：傳回容器中最後一個元素的指針
arg: h為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_last(h) \
(h)->prev
/*
func：傳回容器的指針
arg: h為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_sentinel(h) \
(h)
/*
func：傳回連結清單元素q的下一個元素
arg: q為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_next(q) \
(q)->next
/*
func：傳回連結清單元素q的上一個元素
arg: q為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_prev(q) \
(q)->prev
#if (NGX_DEBUG)
/*
func：移除連結清單中的x元素
arg: x為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_remove(x) \
(x)->next->prev = (x)->prev; \
(x)->prev->next = (x)->next; \
(x)->prev = NULL; \
(x)->next = NULL
#else
#define ngx_queue_remove(x) \
(x)->next->prev = (x)->prev; \
(x)->prev->next = (x)->next
#endif
/*
func：拆分連結清單，h是連結清單容器（連結清單頭），而q是連結清單h中的一個元素，這個方法将連結清單以q為界限，
拆分為兩個連結清單h和n，其中q是後一部分的首元素。
arg: h為連結清單容器結構體ngx_queue_t的指針，q是連結清單h中的一個元素，n是後半部分的連結清單頭
*/
#define ngx_queue_split(h, q, n) \
(n)->prev = (h)->prev; \
(n)->prev->next = n; \
(n)->next = q; \
(h)->prev = (q)->prev; \
(h)->prev->next = h; \
(q)->prev = n;
/*
func：合并連結清單，将n連結清單添加到h連結清單的末尾
arg: h和n為連結清單容器結構體ngx_queue_t的指針
*/
#define ngx_queue_add(h, n) \
(h)->prev->next = (n)->next; \
(n)->next->prev = (h)->prev; \
(h)->prev = (n)->prev; \
(h)->prev->next = h;
/*
func：傳回q元素所屬結構體（任何類型的struct，其中包含ngx_queue_t）的位址
arg: q為連結清單中的元素，type為連結清單元素所在的結構體名稱，link是這個結構體中ngx_queue_t元素的的名字
*/
#define ngx_queue_data(q, type, link) \
(type *) ((u_char *) q - offsetof(type, link))
ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue);
void ngx_queue_sort(ngx_queue_t *queue,
ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));
#endif /* _NGX_QUEUE_H_INCLUDED_ */
/*
* Copyright (C) Igor Sysoev
* Copyright (C) Nginx, Inc.
*/
#include <ngx_config.h>
#include <ngx_core.h>
/*
* find the middle queue element if the queue has odd number of elements
* or the first element of the queue's second part otherwise
*/
/*
func：傳回連結清單中心元素
arg: queue是ngx_queue_t容器的指針
*/
ngx_queue_t *
ngx_queue_middle(ngx_queue_t *queue)
{
ngx_queue_t *middle, *next;
//用第一個元素初始化middle
middle = ngx_queue_head(queue);
//如果頭尾相等，直接傳回目前元素
if (middle == ngx_queue_last(queue)) {
return middle;
}
//用第一個元素初始化next
next = ngx_queue_head(queue);
//快慢指針法
for ( ;; ) {
middle = ngx_queue_next(middle);
next = ngx_queue_next(next);
if (next == ngx_queue_last(queue)) {
return middle;
}
next = ngx_queue_next(next);
if (next == ngx_queue_last(queue)) {
return middle;
}
}
}
/* the stable insertion sort */
/*
func：對連結清單進行插入排序，比較的方法通過cmp來确定
arg: queue是ngx_queue_t容器的指針，cmp是比較函數的指針
*/
void
ngx_queue_sort(ngx_queue_t *queue,
ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
{
ngx_queue_t *q, *prev, *next;
q = ngx_queue_head(queue);
//如果隻有一個元素直接傳回
if (q == ngx_queue_last(queue)) {
return;
}
//利用q周遊連結清單
for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
prev = ngx_queue_prev(q);
next = ngx_queue_next(q);
ngx_queue_remove(q);
//正常的插入排序
do {
//滿足比較條件則退出目前插入
if (cmp(prev, q) <= 0) {
break;
}
prev = ngx_queue_prev(prev);
} while (prev != ngx_queue_sentinel(queue));
ngx_queue_insert_after(prev, q);
}
}
三、如何使用
- 定義連結清單類型結構體
typedef struct {
ngx_queue_t qElem;
int num;
} Node
- 自定義比較函數
ngx_int_t cmp(const ngx_queue_t *a, const ngx_queue_t *b){
//先使用ngx_queue_data方法獲得連結清單元素所屬結構體的位址
Node* aNode = ngx_queue_data(a, Node, qElem);
Node* bNode = ngx_queue_data(b, Node, qElem);
return aNode->num > bNode->num;
}
- 定義雙向連結清單容器并初始化
ngx_queue_t qContainer;
ngx_queue_init(qContainer);
Node node[5];
for(int i = 0; i < 5; i++){
node[i].num = i;
}
//3 1 0 2 4
ngx_queue_insert_tail(&qContainer, &node[0].qElem);
ngx_queue_insert_head(&qContainer, &node[1].qElem);
ngx_queue_insert_tail(&qContainer, &node[2].qElem);
ngx_queue_insert_head(&qContainer, &node[3].qElem);
ngx_queue_insert_tail(&qContainer, &node[4].qElem);
- 調用排序函數
- 周遊連結清單擷取結果
ngx_queue_t* q;
for (q = ngx_queue_next(&qContainer); q != ngx_queue_sentinel(&qContainer); \
q = ngx_queue_next(q)){
Node* nowNode = ngx_queue_data(q, Node, qElem);
printf("val = %d \n", nowNode->num);//0 1 2 3 4
}