摘要：相關(guān)系列前面分析了數(shù)組，現(xiàn)在看一下隊(duì)列和哈希表的實(shí)現(xiàn)。隊(duì)列是一個(gè)雙向鏈表，實(shí)現(xiàn)了一個(gè)隊(duì)列的操作邏輯。它們都將鏈表節(jié)點(diǎn)塞入數(shù)據(jù)結(jié)構(gòu)。對(duì)于常用的解決沖突的方法有線性探測(cè)二次探測(cè)和開(kāi)鏈法等。

  
相關(guān)系列：http://www.codefrom.com/p/nginx

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

ngx_queue_t是一個(gè)雙向鏈表，實(shí)現(xiàn)了一個(gè)隊(duì)列的操作邏輯。但是它的結(jié)構(gòu)只行指針的操作，因而在定義自己的節(jié)點(diǎn)時(shí)，需要自己定義數(shù)據(jù)結(jié)構(gòu)和分配空間，并包含一個(gè)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é)點(diǎn)塞入數(shù)據(jù)結(jié)構(gòu)。Linux內(nèi)核的鏈表這樣定義：

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

使用的時(shí)候

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

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

所以它用fox.list.next指向下一個(gè)節(jié)點(diǎn)，用fox.list.prev指向上一個(gè)節(jié)點(diǎn)。那我們?nèi)绾螐膌ist_head找到fox的地址呢。內(nèi)核提供了一個(gè)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é)點(diǎn)等一系列操作。

用法如下：

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)建隊(duì)列
    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); //初始化queue

    for(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)入隊(duì)列
      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 
", guy->id, guy->name);
    }

    // 排序從頭部輸出
    ngx_queue_sort(&yahoo->queue, yahoo_no_cmp);
    printf("sorting....
");
    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 
", guy->id, guy->name);
    }

    ngx_destroy_pool(pool);
    return 0;
}

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

哈希表整個(gè)結(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;

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

然后對(duì)這個(gè)“對(duì)象”賦值。

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)存存儲(chǔ)如下hash結(jié)構(gòu)。

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

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

ngx_hash_key_t* arr_node; //存儲(chǔ)鍵值對(duì)+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形式存儲(chǔ)。

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

Linux Kernel Development. Page71~72

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

tuzhi / 2015-05-31