為什么80%的碼農(nóng)都做不了架構(gòu)師？>>> ??

前面分析了ngx_array_t數(shù)組，現(xiàn)在看一下ngx_queue隊列和ngx_hash哈希表的實現(xiàn)。

ngx_queue隊列

ngx_queue_t是一個雙向鏈表，實現(xiàn)了一個隊列的操作邏輯。但是它的結(jié)構(gòu)只進(jìn)行指針的操作，因而在定義自己的節(jié)點時，需要自己定義數(shù)據(jù)結(jié)構(gòu)和分配空間，并包含一個ngx_queue_t類型的成員。

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

這和Linux內(nèi)核的數(shù)據(jù)結(jié)構(gòu)很像。它們都將鏈表節(jié)點塞入數(shù)據(jù)結(jié)構(gòu)。Linux內(nèi)核的鏈表這樣定義：

struct list_head {struct list_head *next;struct list_head *prev; }

使用的時候

struct fox {unsigned long tail_length;unsigned long weight;bool is_fantastic;struct list_head list; }

結(jié)構(gòu)如圖所示：

所以它用fox.list.next指向下一個節(jié)點，用fox.list.prev指向上一個節(jié)點。那我們?nèi)绾螐膌ist_head找到fox的地址呢。內(nèi)核提供了一個container_of()宏可以從鏈表指針找到父結(jié)構(gòu)中包含的任何變量。

#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr);\ (type *)( (char *)__mptr - offsetof(type,member) );)

而在Nginx也是效仿采用一樣的宏獲取父結(jié)構(gòu)地址。

#define ngx_queue_data(q, type, link) \(type *) ((u_char *) q - offsetof(type, link))

##用法

它的API定義了初始化，插入，排序，找中位節(jié)點等一系列操作。

用法如下：

typedef struct yahoo_s {ngx_queue_t queue; } yahoo_t;typedef struct yahoo_guy_s {ngx_uint_t id;u_char* name;ngx_queue_t queue; } yahoo_guy_t;ngx_int_t yahoo_no_cmp(const ngx_queue_t* p, const ngx_queue_t* n) {yahoo_guy_t *pre, *next;pre = (yahoo_guy_t*) ngx_queue_data(p, yahoo_guy_t, queue);next = (yahoo_guy_t*) ngx_queue_data(n, yahoo_guy_t, queue);return ((pre->id > next->id) ? 1:0); }int main() {ngx_pool_t* pool;yahoo_guy_t* guy;ngx_queue_t* q;yahoo_t* yahoo;pool= ngx_create_pool(1024*10, NULL); //初始化內(nèi)存池int i;// 構(gòu)建隊列const ngx_str_tnames[] = { ngx_string("rainx"), ngx_string("xiaozhe"), ngx_string("zhoujian")} ;const in ids[] = {4611, 8322, 6111};yahoo = ngx_palloc(pool, sizeof(yahoo_t));ngx_queue_init(&yahoo->queue); //初始化queuefor(i = 0; i < 3; i++){guy = (yahoo_guy_t*) ngx_palloc(pool, sizeof(yahoo_guy_t));guy->id = ids[i];guy->name = (u_char*) ngx_pstrdup(pool, (ngx_str_t*) &(names[i]) );ngx_queue_init(&guy->queue);// 從頭部進(jìn)入隊列ngx_queue_insert_head(&yahoo->queue, &guy->queue);}// 從尾部遍歷輸出for(q = ngx_queue_last(&yahoo->queue);q != ngx_queue_sentinel(&yahoo->queue);q = ngx_queue_prev(q) ) {guy = ngx_queue_data(q, yahoo_guy_t, queue);printf("No. %d guy in yahoo is %s \n", guy->id, guy->name);}// 排序從頭部輸出ngx_queue_sort(&yahoo->queue, yahoo_no_cmp);printf("sorting....\n");for(q = ngx_queue_prev(&yahoo->queue);q != ngx_queue_sentinel(&yahoo->queue);q = ngx_queue_last(q) ) {guy = ngx_queue_data(q, yahoo_guy_t, queue);printf("No. %d guy in yahoo is %s \n", guy->id, guy->name);}ngx_destroy_pool(pool);return 0; }

ngx_hash哈希表

ngx_hash表所用的hash算法為分桶后線性查找法，因而查找效率同key-value對成反比。對于常用的解決沖突的方法有線性探測、二次探測和開鏈法等。這里使用的是最常用的開鏈法(也是STL中使用的方法)。

哈希表整個結(jié)構(gòu)如圖所示：

哈希表用下列數(shù)據(jù)結(jié)構(gòu)進(jìn)行管理

typedef struct {ngx_hash_t *hash;ngx_hash_key_pt key;ngx_uint_t max_size;ngx_uint_t bucket_size;char *name;ngx_pool_t *pool;ngx_pool_t *temp_pool; } ngx_hash_init_t;

在使用過程中，先會用ngx_hash_init_t實例化(類似于OOP思想，和內(nèi)核驅(qū)動的用法相同)一個hash_init。

然后對這個“對象”賦值。

hash = (ngx_hash_t*)ngx_pcalloc(pool, sizeof(hash)); hash_init.hash = hash; // hash結(jié)構(gòu) hash_init.key = &ngx_hash_key_lc; // hash算法函數(shù) hash_init.max_size = 1024*10; // max_size hash_init.bucket_size = 64; //桶的大小 hash_init.name = "yahoo_guy_hash"; hash_init.pool = pool; // 用到的內(nèi)存池 hash_init.temp_pool = NULL;

第一行分配了ngx_hash_t大小的內(nèi)存存儲如下hash結(jié)構(gòu)。

typedef struct {ngx_hash_elt_t **buckets;ngx_uint_t size; } ngx_hash_t;

然后創(chuàng)建一個需要加到hash table中的數(shù)組。

ngx_hash_key_t* arr_node; //存儲鍵值對+hash值 elements = ngx_array_create(pool, 32, sizeof(ngx_hash_key_t)); for(i = 0; i < 3; i++) {arr_node = (ngx_hash_key_t*) ngx_array_push(elements);arr_node->key = (names[i]);arr_node->key_hash = ngx_hash_key_lc(arr_node->key.data, arr_node->key.len);arr_node->value = (void*)descs[i]; }ngx_hash_init(&hash_init, (ngx_hash_key_t*) elements->elts, elements->nelts)

最后將elements數(shù)組放到hash_init結(jié)構(gòu)中，即將數(shù)組以hash table形式存儲。

這就是整個hash結(jié)構(gòu)的存儲過程，查找相對簡單，這里不再詳述。

##參考 Linux Kernel Development. Page71~72

http://www.embedu.org/Column/Column433.htm

轉(zhuǎn)載于:https://my.oschina.net/lvyi/blog/422823

總結(jié)

以上是生活随笔為你收集整理的Nginx源码分析(3)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。