nginx的基本資料結構

ngx_str_t 源碼檔案:ngx_string.h|c 定義:

struct  ngx_str_s {
  size_t      len;//字元串長度
  u_char     *data;//字元串起始位址
} ngx_str_t;
           

說明: ngx_str_t是nginx使用的字元串類型，ngx_str_t用len成員來表示字元串的長度，c标準庫中的很多字元串函數不能用于ngx_str_t，是以nginx實作了很多用于ngx_str_t的函數

常用函數/宏: ngx_string(str):給一個ngx_str_t變量指派 ngx_null_string:用于初始化一個ngx_str_t變量 ngx_str_set(str, text):用text對str變量進行指派,這裡text隻能字元串字面值常量 ngx_str_null(str):重置str變量

ngx_buf_t,ngx_chain_t 源碼檔案:ngx_buf.h|c 定義:

struct ngx_buf_s {
  u_char *pos;//資料起始位址
  u_char *last;//資料結束位址
  off_t file_pos;//資料在檔案中的起始位置偏移量
  off_t file_last;//資料在檔案中的結束位置偏移量
  u_char *start;//buffer在記憶體中的起始位址
  u_char *end;//buffer在記憶體中的結束位址
  ngx_buf_tag_t tag;//可以是任何資料
  ngx_file_t *file;//如果buf内容在檔案中，那麼存儲的是檔案的資訊
  ngx_buf_t *shadow;//指向另外一個buf，該buf與這個buf實際指向同一個記憶體對象
  unsigned temporary:1;//1代表該buf的資料是可以更改的
  unsigned memory:1;//代表該buf資料在記憶體中，且不可修改
  unsigned mmap:1;//代表該buf是檔案通過記憶體映射到記憶體中，不可更改
  unsigned recycled:1;//代表是可重複利用的，即可以釋放的
  unsigned in_file:1;//代表該buf的内容在檔案中
  unsigned flush:1;
  unsigned sync:1;
  unsigned last_buf:1;//該buf在一系列鍊中是最後一個
  unsigned last_in_chain:1;//該buf是所在鍊的最後一個節點
  unsigned last_shadow:1;
  unsigned temp_file:1;
  int num;
}
           

說明:nginx中用作資料緩沖區的基本結構 常用函數/宏: ngx_buf_t *ngx_create_temp_buf(ngx_pool_t *pool, size_t size) 說明：從記憶體池中建立一個容量為size的臨時buf，該buf的内容是可以修改的

ngx_chain_t *ngx_alloc_chain_link(ngx_pool_t *pool) 說明:從記憶體池中建立一個連結清單。如果記憶體池中已經有可用連結清單對象，則直接傳回該對象，并且将記憶體池的chain成員指向下一個結點；如果沒有可用對象，則直接從記憶體池擷取一塊大小為ngx_chain_t的記憶體，并将首位址傳回。

ngx_chain_t *ngx_alloc_chain_of_bufs(ngx_pool_t *pool, ngx_bufs_t *bufs) 說明：建立包含若幹buf結點的chain,buf結點的數量和容量由bufs參數決定

ngx_int_t ngx_chain_add_copy(ngx_pool_t *pool, ngx_chain_t *chain, ngx_chain_t *in) 說明；連結清單添加。将in鍊的buf加在chain鍊的末尾

ngx_chain_t *ngx_chain_get_free_buf(ngx_pool_t *pool, ngx_chain_t **free) 說明:從buf鍊擷取空閑的buf。如果free所指向的鍊中有空閑的buf,就将該空閑buf的位址傳回，并且将free指向下一個空閑的buf；如果free中沒有空閑buf,則從記憶體池中申請新的chain并傳回。

void ngx_chain_update_chains(ngx_pool_t *pool, ngx_chain_t **free, ngx_chain_t **busy, ngx_chain_t **out, ngx_buf_tag_t tag) 說明:更新chain。 1.  如果out不為空，就将out加在busy的末尾，然後将out置空。 2.  周遊busy的所有節點，如果節點buf的大小不為0(即還未用完)就結束周遊，否則繼續下一步。 3.  如果節點buf的tag成員與tag參數不比對，就将busy指向下一個結點，并且将目前節點插入到pool的chain成員頭部，然後繼續周遊busy，否則進行下一步 4.  将節點的buf重置(pos,last都指向start),然後把節點插入到free連結清單的頭部

ngx_chain_t *ngx_chain_update_sent(ngx_chain_t *in, off_t sent) 說明:更新chain,依次把in的buf的可用記憶體區更新，如果sent大于可用記憶體，就将可用記憶體置為0,并把sent減去可用記憶體大小，然後跳到下一個結點，直到sent為0或者in的所有節點都被更新完

ngx_array_t 源碼檔案:ngx_array.h|c 定義:

typedef struct {
  void *elts;//指向元素首位址
  ngx_uint_t nelts;//目前元素數量
  size_t size;//元素大小
  ngx_uint_t nalloc;//數組容量
  ngx_pool_t *pool;//記憶體池指針
};
           

說明: 常用函數/宏: ngx_array_t *ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size) 說明:建立包含n個元素，每個元素大小為size的數組

void ngx_array_destroy(ngx_array_t *a) 說明:銷毀數組。該函數隻在數組是從記憶體池配置設定出去的最後一塊記憶體時才會釋放數組及元素所在記憶體塊，否則将什麼也不做。釋放的方法就是把pool->d的last成員減去數組元素以及數組結構體本身所占記憶體的大小，以此擴大記憶體池可用空間大小。

void *ngx_array_push(ngx_array_t *a) 說明:向數組中追加一個元素。如果數組未滿，則直接從數組的資料記憶體塊中取。否則，如果數組的資料塊是記憶體池配置設定的最近一塊記憶體(即資料塊的最後一個位元組的位址等于pool->d.last)且記憶體池剩餘記憶體塊大于數組元素的大小，就直接從記憶體池中擷取，并将數組的nalloc加1，否則就從記憶體池中重新申請一塊大小為原數組大小兩倍的記憶體塊，将原數組記憶體塊拷貝到新數組中，并将數組的elts指向新的記憶體塊，nalloc翻倍。這裡需要注意的是，原來的記憶體塊此時并未釋放，這樣會造成記憶體的浪費，是以建立數組的時候盡量預估好數組的容量，避免浪費記憶體。

void *ngx_array_push_n(ngx_array_t *a) 說明:向數組中追加n個元素，傳回第一個元素的位址，步驟與ngx_array_push基本一緻

ngx_list_t 源碼檔案:ngx_list.h|c 定義:

struct ngx_list_part_s {
  void *elts;//資料塊首位址
  ngx_unit_t nelts;//元素個數
  ngx_list_part_s *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;
           

說明:ngx_list_t 實際上是一個連結清單，連結清單的每一個結點都是數組，數組的元素個數是nalloc, 大小是size

常用函數/宏: ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size)， 說明:建立一個新的list,并且為首結點配置設定記憶體，設定成員變量，并将last也指向首結點   void *ngx_list_push(ngx_list_t *l) 說明:向list中插入一個元素。 (1)如果list的last節點已經滿了(last->nelts == nalloc)，就申請一個新的節點，插入到list的末尾，成為新的last節點，否則跳到第二步 (2)傳回last節點的未配置設定記憶體塊的首位址  (3)将last節點的nelts加1

ngx_queue_t 源碼檔案:ngx_queue.h|c 定義:

struct ngx_queue_s {
  ngx_queue_t *prev;//上一個節點
  ngx_queue_t *next;//下一個節點
};
           

說明: 這是一個帶哨兵節點的雙向連結清單 常用函數/宏: #define Ngx_queue_init(q) 說明:初始化連結清單,q->prev和q->next都指向q   #define Ngx_queue_empty(h) 說明:判斷連結清單是否為空(h == (h)->prev)   #define Ngx_queue_insert_head(h, x) 說明:在連結清單頭部插入一個節點   #define ngx_queue_insert_tail(h, x) 說明:在連結清單尾部插入一個節點   #define ngx_queue_head(h) 說明：傳回第一個節點   #define ngx_queue_last(h) 說明: 傳回最後一個節點   #define ngx_queue_sentinel(h) 說明: 傳回哨兵節點   #define ngx_queue_next(q) 說明: 傳回q節點的下一個結點   #define ngx_queue_prev(q) 說明: 傳回q節點的上一個節點   #define ngx_queue_remove(x) 說明: 從連結清單中删除x節點   #define ngx_queue_split(h, q, n) 說明:分隔連結清單，将h連結清單以q為界分割成兩個連結清單，q之前的節點依舊屬于h清單，q以及q之後的節點屬于n連結清單(n為新的空節點)   #define ngx_queue_add(h, n) 說明:将n連結清單添加到h連結清單末尾

ngx_hash_t 源碼檔案:ngx_hash.h|c 定義:

哈希表元素結構
typedef struct {
  void *value;//資料位址
  u_short len;//資料長度
  u_char name[1];//元素名
} ngx_hash_elt_t;

哈希表結構
typedef struct {
  ngx_hash_elt_t **buckets;//元素數組指針
  ngx_uint_t size;//桶的個數
} ngx_hash_t;

帶通配符的key的hash表
typedef struct {
  ngx_hash_t hash;
  void *value;
} ngx_hash_wildcard_t;

哈希key
typedef struct {
  ngx_str_t key;//key名稱
  ngx_uint_t key_hash;//key的hash值
  void *value;//key對應的value 
} ngx_hash_key_t;

混合哈希表
typedef struct {
  ngx_hash_t *hash;//不帶通配符的key的hash表
  ngx_hash_wildcard_t *wc_head;//前面帶通配符的key的hash表
  ngx_hash_wildcard_t *wc_tail;//後面帶通配符的key的hash表
} ngx_hash_combined_t;

哈希表初始化結構
typedef struct {
  ngx_hash_t *hash;//如果為NULL,初始化完成後指向新建立的hash表，如果不為NULL,所有資料将插入該字段指向的hash表
  ngx_hash_key_pt key;//生成hashkey的函數
  ngx_uint_t max_size;//哈希表中桶的最大個數
  ngx_uint_t bucket_size;//哈希表桶的最大大小，機關位元組
  char *name;//哈希表名
  ngx_pool_t *pool;//配置設定記憶體使用的pool
  ngx_pool_t *temp_pool;//臨時pool,初始化完成後可以釋放和銷毀
} ngx_hash_init_t;

用于構造組合hash表的結構體
typedef struct {
  ngx_uint_t hsize;
  ngx_pool_t *pool;
  ngx_pool_t *temp_pool;//臨時記憶體池，用于在建立hash表結構中臨時申請的記憶體，hash表構造完成後可以釋放
  ngx_array_t keys;//不帶通配符的key 的數組
  ngx_array_t *keys_hash;
  ngx_array_t dns_wc_head;//前部帶通配符的key的數組
  ngx_array_t *dns_wc_head_hash;
  ngx_array_t dns_wc_tail;
  ngx_array_t *dns_wc_tail_hash;//後部帶通配符的key的數組
} ngx_hash_keys_arrays_t;

typedef struct {
  ngx_uint_t hash;
  ngx_str_t key;
  ngx_str_t value;
  u_char *lowcase_key;
} ngx_table_elt_t;
           

說明: 常用函數/宏: ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) 說明:hash表初始化函數.該函數根據hinit結構體的max_size和bucket_size以及names數組元素的記憶體占用大小，計算出合适的桶數量，并為每個桶配置設定記憶體，然後對names數組裡的每一個元素的hash_key值進行二次哈希，将元素的值，長度以及小寫名儲存在對應的桶内。如果hinit的hash為NULL,就将hash指向新建立的哈希表,否則就将所有資料插入hash指向的哈希表中   void *ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len) 說明:元素查找函數。該函數對key進行哈希 找到對應的桶，并在桶内查找len成員等于len并且name成員與name參數相同的元素，如果找到 ，傳回元素的value，否則傳回NULL   #define ngx_hash(key, c) ((ngx_uint_t)key * 31 + c) 說明: 基礎hash值計算   ngx_uint_t ngx_hash_key(u_char *data, size_t len) 說明:nginx的哈希key生成算法。原理是将0作為key初始值，然後對data的每一個位元組都進行ngx_hash計算，将結果賦予key，将最後得到的key作為結果傳回   ngx_uint_t ngx_hash_key_lc(u_char *data, size_t len) 說明:nginx的哈希key生成算法，原理與ngx_hash_key類似，差別在于是用每個位元組的小寫值進行ngx_hash計算   ngx_uint_t ngx_hash_strlow(u_char *dst, u_char *src, size_t) 說明: 該算法是将src的每個位元組的小寫值賦予dst的對應位置，然後對dst使用ngx_hash計算key，本質上與ngx_hash_key_lc一樣，隻是 多了一個指派   ngx_int_t ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type) 說明:初始化ha，主要是根據type進行hash表桶數量的計算以及成員的記憶體配置設定   ngx_int_t ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key, void *value, ngx_uint_t flags) 說明:向ha中添加key，自動根據是否帶有通配符以及通配符的位置将key儲存到ha對應的成員中(keys, dns_wc_tail或者dns_wc_head)   ngx_int_t ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts) 說明:初始化帶通配符的key的hash表。不能同時用于前部帶通配符和後部帶通配符的key

ngx_rbtree_t 源碼檔案:ngx_rbtree.h|c 定義:

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;//節點鍵值
    ngx_rbtree_node_t     *left;//左子樹指針
    ngx_rbtree_node_t     *right;//右子樹指針
    ngx_rbtree_node_t     *parent;//父節點指針
    u_char                 color;//節點顔色
    u_char                 data;//資料，沒什麼用
};

struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;//紅黑樹根節點
    ngx_rbtree_node_t     *sentinel;//哨兵節點
    ngx_rbtree_insert_pt   insert;//插入結點函數
};

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
           

說明: nginx的紅黑樹是基于算法導論裡描述的紅黑樹實作的，在定時器的管理中使用。

常用函數/宏: ngx_rbtree_init(tree, s, i) 說明：初始化紅黑樹，s是哨兵節點，i是插入結點函數

void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) 說明：向紅黑樹中插入結點

void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) 說明：删除紅黑樹中node表示的節點

ngx_radix_tree_t 源碼檔案: 定義: 說明: 常用函數/宏: