数据结构---nginx-1.7.12源码分析（双向链表）

清疚 2022-08-07 15:51 156阅读 0赞

//  完美分析 请见： [http://blog.csdn.net/chen19870707/article/details/40371047][http_blog.csdn.net_chen19870707_article_details_40371047]

**Ngx\_queue.h**

/*
    *  ngx-queue.h
     * Copyright (C) Igor Sysoev
     * Copyright (C) Nginx, Inc.
     */
    
    
    #include <ngx_config.h>
    #include <ngx_core.h>
    
    
    #ifndef _NGX_QUEUE_H_INCLUDED_
    #define _NGX_QUEUE_H_INCLUDED_
    
    // nginx 的所有的链表操作对象类型
    typedef struct ngx_queue_s  ngx_queue_t;
    
    struct ngx_queue_s {
        ngx_queue_t  *prev;
        ngx_queue_t  *next;
    };
    
    // 链表初始化
    #define ngx_queue_init(q)                                                     \
        (q)->prev = q;                                                            \
        (q)->next = q
    
    // 判断链表是否为空
    #define ngx_queue_empty(h)                                                    \
        (h == (h)->prev)
    
    //h 插入到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
    
    //将h 插入到x的后面
    #define ngx_queue_insert_tail(h, x)                                           \
        (x)->prev = (h)->prev;                                                    \
        (x)->prev->next = x;                                                      \
        (x)->next = h;                                                            \
        (h)->prev = x
    
    //下一个节点
    #define ngx_queue_head(h)                                                     \
        (h)->next
    
    // 上一个节点
    #define ngx_queue_last(h)                                                     \
        (h)->prev
    
    // 当前节点
    #define ngx_queue_sentinel(h)                                                 \
        (h)
    
    
    #define ngx_queue_next(q)                                                     \
        (q)->next
    
    
    #define ngx_queue_prev(q)                                                     \
        (q)->prev
    
    
    #if (NGX_DEBUG)
    //删除该节点 在链表中的位置
    #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
    
    // 分割队列
    // h为链表容器，q为链表h中的一个元素，这个方法可以将链表h以元素q为界拆分为两个链表h和n，其中h由原链表的前半部分组成（不包含q），而n由后半部分组成，q为首元素，操作也很简单
    #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;
    
    // 链接 队列:    将链表n 合并到链表h的尾部
    #define ngx_queue_add(h, n)                                                   \
        (h)->prev->next = (n)->next;                                              \
        (n)->next->prev = (h)->prev;                                              \
        (h)->prev = (n)->prev;                                                    \
        (h)->prev->next = h;
    
    //获取队列中的节点数据 
    // 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);
    
    //队列排序算法 只要更改cmp函数即可
    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_ */

ngx-queue.c

/*
     * 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
     */
    
    /*这里用到的技巧是每次middle向后移动一步，
    next向后移动两步，这样next指到队尾的时候，
    middle就指到了中间，时间复杂度就是O(N)，
    这是一道经典的面试题，
    今天在这里看到了源码，
    似成相识啊，果然经典面试题目都不是凭空而来*/
    ngx_queue_t *
    ngx_queue_middle(ngx_queue_t *queue)
    {
        ngx_queue_t  *middle, *next;
    
        middle = ngx_queue_head(queue);
    
        if (middle == ngx_queue_last(queue)) {
            return middle;
        }
    
        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 */
    /*这边 就是从第个元素开始向前遍历
    可以看到，这里采用的是插入排序算法，
    时间复杂度为O(n)，整个代码非常简洁。*/
    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;
        }
    
        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);
        }
    }

最后是我的 测试代码 现 贴上：

#include <iostream>
      #include <algorithm>
        #include <pthread.h>
        #include <time.h>
        #include <stdio.h>
        #include <errno.h>
        #include <string.h>
        #include "queue.h"
    #include <stddef.h>
       
       struct student_info
       {
          long stu_id;
          unsigned int age;
          unsigned int score;
          ngx_queue_t qEle;
       };
        
       int compareStudent(const ngx_queue_t *a, const ngx_queue_t *b)
       {
          //分别取得a b 对象指针
           student_info *ainfo = ngx_queue_data(a,student_info,qEle);
           student_info *binfo = ngx_queue_data(b,student_info,qEle);
        
           return ainfo->score <binfo->score;
       }
        
       void print_ngx_queue(ngx_queue_t *queue)
       {
           //遍历输出
           for(ngx_queue_t *q = ngx_queue_head(queue);q != ngx_queue_sentinel(queue);q = ngx_queue_next(q))
           {
               student_info *info = ngx_queue_data(q, student_info, qEle);
              if(info != NULL)
               {
                   std::cout <<info->score << "  ";
               }
           }
        
           std::cout << std::endl;
       }
        
       int main()
       {
        
           ngx_queue_t queue;
           ngx_queue_init(&queue);
        
           student_info info[5];
           for(int i = 0;i < 5;i++)
           {
               info[i].stu_id = i;
               info[i].age = i;
               info[i].score = i;
        
               if(i%2)
               {
                   ngx_queue_insert_tail(&queue,&info[i].qEle);
              }
               else
               {
                   ngx_queue_insert_head(&queue,&info[i].qEle);
               }
           }
        
           print_ngx_queue(&queue);
        
           ngx_queue_sort(&queue,compareStudent);
        
           print_ngx_queue(&queue);
        
           return 0;
       }

**关键点：**

## 根据ngx\_queue\_t 找到链表元素 ##

1: #define ngx_queue_data(q, type, link)                                         \

2:     (type *) ((u_char *) q - offsetof(type, link))

其中q为ngx\_queue\_t\* 类型，函数作用为根据q算出，算出链表元素的地址，其中linux接口offsetof是算出link在type中的偏移。

**总结：**

ngx\_queue设计非常精巧，基本涵盖了双链表的所有操作，建议需要面试的童鞋看一看，很多链表的题目都迎刃而解。此外，ngx\_queue与其它nginx 代码耦合度低，有需要这种双向链表的实现时不妨直接拿过来使用。

[http_blog.csdn.net_chen19870707_article_details_40371047]: http://blog.csdn.net/chen19870707/article/details/40371047